#include<iostream>
#include<string>
#include<cstring>
#include<stdlib.h>
using namespace std;
void swap(int *a,int *b){
    int k = *a;
    *a = *b;
    *b = k;
}
//直接插入排序
void insertSort(int *a,int len){
    for(int i=1;i<len;i++){
        int temp = a[i];
        int j = i-1;
        for(;j>=0;j--){
            if(temp<a[j])
                a[j+1] = a[j];
            else 
                break;
        }
        a[j+1] = temp;
    }
} 
//選擇排序 
void selectSort(int *a,int len){
    for(int i=0;i<len-1;i++){
        int k = i;
        for(int j=i+1;j<len;j++){
            if(a[j]<a[k])
                k = j;
        }
        swap(&a[i],&a[k]);
    }
}
//冒泡排序
void bubbleSort(int *a,int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if(a[j]>a[j+1])
                swap(&a[j],&a[j+1]);
        }
    }
}
//歸并排序
//遞歸
void merge(int *a,int left,int mid,int right,int *b){
    int i = left;
    int j = mid +1 ;
    int k = 0;
    while(i<=mid&&j<=right){
        if(a[i]<a[j]){
            b[k++] = a[i++];
        }else{
            b[k++] = a[j++];
        }
    }
    while(i<=mid){
        b[k++] = a[i++];
    }
    while(j<=right){
        b[k++] = a[j++];
    }
    k = 0;
    while(left <= right){
        a[left++] = b[k++];
    }
}
void mergeSort(int *a,int left,int right,int *b){
    if(left<right){
        int mid = left + (right - left)/2;
        mergeSort(a,left,mid,b);
        mergeSort(a,mid+1,right,b);
        merge(a,left,mid,right,b);
    }
}

//歸并排序
//迭代
void mergeSort(int *a,int len,int *b){
    int r,rm,l,lm,t;
    for(int i=1;i<len;i*=2){
        for(l=0;l<len-1;l=rm){
            t = 0;
            lm = l + i;
            r = lm;
            rm = r + i;
            if(rm>len)
                rm = len;
            while(r<rm&&l<lm){
                if(a[l]>a[r]){
                    b [t++] = a[r++];
                }else{
                    b[t++] = a[l++];
                }
            }
            while(r<rm){
                b [t++] = a[r++];
            }
            while(l<lm){
                b[t++] = a[l++];
            }
            while(t>0){
                a[--r] = b[--t];
            }
        }
    }
}

//快速排序
//遞歸 
void quickSort(int *a,int left,int right){
    if(left>=right)
        return;
    int i,j,temp;
    i = left;
    j = right;
    temp = a[left];
    while(i<j){
        while(a[j]>=temp&&i<j)
            j--;
        while(a[i]<=temp&&i<j)
            i++;
        if(i<j)
            swap(&a[i],&a[j]);
    }
    a[left] = a[i];
    a[i] = temp;
    quickSort(a,left,i-1);
    quickSort(a,i+1,right);
} 
//快速排序
//迭代
void quickSort2(int *a,int len){
    int *stack  = (int*)malloc(len*sizeof(int));
    int top = -1;
    stack[++top] = 0;
    stack[++top] = len-1;
    while(top!=-1){
        int high = stack[top--];
        int low = stack[top--];
        while(low<high){
            int i = low;
            int j = high;
            int temp = a[i];
            while(i<j){
                while(a[j]>=temp&&i<j)
                    j--;
                while(a[i]<=temp&&i<j)
                    i++;
                    if(i<j)
                        swap(&a[i],&a[j]);
            }
            a[low] = a[i];
            a[i] = temp;
            if(i-low<high-i){
                stack[++top] = i +1;
                stack[++top] = high;
                high = i - 1;
            }else{
                stack[++top] = low;
                stack[++top] = i -1;
                low = i + 1;
            }
        }
    }
} 
void mergeSort(int *a,int len,int flag){
    int *b = (int*)malloc(len*sizeof(int));
    switch(flag){
        case 0:
            mergeSort(a,0,len-1,b);
            break;
        case 1:
            mergeSort(a,len,b);
            break;  
    }
}