算法--排序

关于排序的一点代码

#include <stdio.h>
void  exch(int *a, int i, int j){
    int tmp;
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;

}
void select(int *array, int len){
    int j = 0;
    int tmp, i;
    for(; j < len; j++){
        for(i = j+1, tmp = j; i < len; i++){
            if(array[i] < array[tmp])
                tmp = i;
        }

        i = array[j];
        array[j] = array[tmp];
        array[tmp] = i;
    }
}

void insert(int *a, int len){
    int i, pos,tmp, dd;
    i = 1;
    for(; i < len; i++){ //因为要把每一个位置的数据放在它前面中最小的地方，所以要遍历每一个数据

        tmp = i;
        while(tmp-1 >= 0 && a[tmp-1] > a[tmp]){     //这里就是把一个数据不断跟前面的一位比较，如果小于前面的一位就一直交换
            exch(a, tmp, tmp-1);
            tmp--;
            dd++;
        }
    }
    printf("%d\n", dd);
    for(dd = 0; dd < len; dd++)
    printf("%d ", a[dd]);
printf("\n");
}

void shellsort(int * a, int len){
    int h = 1, i, j, dd = 0;
    while(h < len / 3) h = 3*h + 1;  //这里是选key的一种方式，也可以直接len/2

    for (; h >= 1; h /= 3){
        if(h == 1) printf("dds");
        for(i = h; i < len; i++ ) {    //如果使用i = 0; i < h;i++；这种方式是对每一个组排序，而这种是对每一个数据直接位移，也就是对相应的每一个组
            for(j = i; j-h >= 0 && a[j] < a[j - h]; j -= h){
                exch(a, j, j - h);
                dd++;
            }   
        }
    }
    printf("%d\n", dd);
    for(dd = 0; dd < len; dd++)
        printf("%d ", a[dd]);
    printf("\n");
}
void _merge(int *a, int *tmp, int lo, int hi){
    if(lo >= hi) return;
    if(hi - lo == 1) {
        if(a[lo] > a[hi])
            exch(a, lo, hi);
        return;
    }
    int mid = (lo + hi) / 2;
    _merge(a, tmp, lo,  mid);       //把范围一直缩小到左半部最小范围，先排序小的再进行合并
    _merge(a, tmp, mid, hi);        //同理
    int i = lo, j = mid;
    int k = lo;
    for(; k <= hi; k++ ) {          //把3个及以上的数组进行合并排序，这里是先把它们拷贝到tmp数组
        tmp[k] = a[k];
    }

    for(k = lo; k <= hi; k++) {     //把tmp数组分为两部分，从0-mid, mod-len, 不断把最小的数拷贝进原数组，左半部拷贝完就一直拷贝右半部，左面的数小于右面就拷贝右面
        if(i >= mid) a[k] = tmp[j++];
        else if(j > hi) a[k] = tmp[i++];
        else if(tmp[i] > tmp[j]) a[k] = tmp[j++];
        else a[k] = tmp[i++];
    }
}
void merge(int *a, int len){
    int tmp[len];
    _merge(a, tmp, 0, len-1);
}

void _quicksort(int *a, int lo, int hi){
    if (lo >= hi)
        return;
    
    int i = lo, j = hi, k = i, dd = 0;
    int key = a[i];
    i++;
    while(i < j){
        while(i < j && a[i] < key)
            i++;
        while(i < j && a[j] > key)
            j--;
        exch(a, i, j);
    }
    exch(a, lo, i);

    _quicksort(a, lo, i-1);
    _quicksort(a, i+1, hi);
}

void quicksort(int *a, int len){
    _quicksort(a, 0, len-1);
}


int main(){
    int a[] = {234,22,23443,53,434,32,3,0,2341,33,3};
    int i = 0;
    int len = sizeof(a)/sizeof(int);
    quicksort(a, len);

    for(; i< len; i++){
        printf("%d ", a[i]);
    }
    printf("\n");
}