排序算法总结

给出含有n个元素的数组array[n]，对其进行排序(排列成从小到大)。
对于每一个算法，需要给出  代码、算法复杂度、空间复杂度、是否稳定。

1.插入排序
void insert_sort(int *array, int n){
    for(int j=1;j<n;j++){
        int i=j-1;
        int key=a[j];
        while(i>=0 && a[i]>key){
            a[i+1]=a[i];
            i--;
        }
        a[i+1]=key;
    }
}
复杂度、稳定性 自己从代码看吧
空间复杂度为O(1),因为程序只需要额外的几个变量就可以了。

2.归并排序
void merge(int *A, int p, int q, int r){
    int n1=q-p+1;
    int n2=r-q;
    int *array1 = (int *)malloc( n1*sizeof(int));  
    int *array2 = (int *)malloc( n2*sizeof(int));
    for(int i=0;i<n1;i++)
        array1[i] = A[p+i];
    for(int i=0;i<n2;i++)
        array2[i] = A[q+i+1];

    int i=0,j=0;
    for(int k=p;k<=r;k++){
        if( i<n1 && array1[i]>array2[j]){
            A[k] = array1[i];
            i++;
        }else if( j<n2){
            A[k] = array2[j];
            j++;
        }
    }
}
void merge_sort(int *array, int p, int r){
    if(p<r){
        q=(p+r)/2;
        merge_sort(array, p, q);
        merge_sort(array, q+1, r);
        merge(array, p, q, r);
    }
}

排序的时候只需调用merge_sort(array, 0, n-1)即可。
使用了递归，看起来很复杂，不过算法时间复杂度降为O(nlgn), 稳定倒还是稳定的.
同时时间复杂度增加，需要空间为O(n)。
在本程序中每次调用merge都重新申请，对效率会有影响，改为程序全局申请一个长度为n数组会更好些。

3.堆排序
引入了二叉堆这个数据结构，二叉堆跟完全二叉树很像。
int heap_size;  //全局变量
void max_heapify(int *array, int i){
    int left = 2*i +1;
    int right = 2*i +2;
    int largest;
    if(left < heap_size && array[left] > array[i])
        largest = left;
    else
        largest = i;
    if(right < heap_size && array[right] > array[largest])
        largest = right;
 
    if(largest != i){
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;

        max_heapify(array,largest);
    }
}

void build_max_heap(int *array, int n){  //要把数据从小到大排序，就要构建大顶堆，
    heap_size = n;
    for(int i=n/2; i>=0; i--)
        max_heapify(array, i);
}

void heap_sort(int *array, int n){
    build_max_heap(array, n);
    for(int i=n-1; i>0; i--){
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        heap_size--;
        max_heapify(array, 0);
    }
}
堆排序中，max_heapify时间复杂度O(lgn), build_max_heap时间复杂度O(n),
heap_sort时间复杂度为O(nlogn).
空间复杂度：不需要额外的数组，故空间复杂度为O(1)。
稳定性：不稳定。原因呢？两个相等的元素A、B，原来的时候A在B前面，可在max_heapify过程中比较largest时，A在自己的分支中较小而没有动，B在自己分支中较大就上去了，这时B就排在A前面了。

顺便说一句，堆排序虽然性能不错，但还是比不上下面要讲的快排，但这里讲的堆结构还是有很多应用的，比如用于实现优先队列。max priority queue 和 min priority queue。

4.快速排序
快排在最坏情况下时间复杂度为O(n^2)，平均时间复杂度为O(nlgn), 但实际应用中，该算法往往效率很高。
void quick_sort(int *array, int p, int r){
    if(p<r){
        int q = partition(array, p, r);
        quick_sort(array, p, q-1);
        quick_sort(array, q+1, r);
    }
}
int partition(int *array, int p, int r){
    int x = array[r];
    int i = p-1;
    for(int j=p; j<r; j++){
        if(array[j] <= x){
            i++;
            int temp= a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    int temp = array[i+1];
    array[i+1] = x;
    array[r] = temp;

    return (i+1);
}
空间复杂度：需要程序员搞定的空间还是常数O(1).  但是由于使用了递归，递归栈上会使用一些空间，递归栈上的空间复杂度 最坏O(n)，平均O(lgn)。 快速排序是不稳定的。

以下为线性时间排序，这些排序都对数据有一定的限制，因为只要是使用比较来进行排序的算法，都不可能打破O(nlgn)的下限。
5.counting sort 计数排序
计数排序要求输入的含有n个元素的数组中，每个元素的大小都在0~k之间，而且k=O(n)。
void count_sort(int *array, int n, int k){
    int *B = (int *)malloc(n*sizeof(int));
    int *C = (int *)malloc( (k+1)*sizeof(int));
    for(int i=0; i<=k; i++)
        C[i] = 0;
    for(int i=0; i<n; i++)
        C[array[i]]++;
    for(int i=1; i<=k; i++)
        C[i] = C[i] + C[i-1];
    for(int i=n-1; i>=0; i--){
        B[ C[A[i]] - 1 ] = A[i];
        C[A[i]]--;
    }
}
这个计数排序需要O(n+k)的额外空间，并且它是稳定的。

若是不要求稳定性，我们可以改写上述算法，改为原地排序，即不需要上面程序中的B数组了。

6.radix sort 基数排序
卡片排序机使用的就是基数排序。基数排序一般用于含有多个域的数据排序。比如一个日期含有年、月、日三个域，对日期进行排序。
radix sort要调用其他的一个稳定排序算法。
void radix_sort(int *array, int d) {   //d表示的是数据所划分的域的个数
    for(int i=0; i<d; i++)
        use a stable sort to sort arrya on digit i。
}
给出一个有n个元素的数组，数组中全是d位的数，每个数的每一位都可用k个可能的值（对于十进制整数就是0-9），针对d位中每一位的排序使用计数排序，那么基数排序的时间复杂度为O(d(n+k))。

7.bucket sort 桶排序


还有一些排序方法 在算法导论中没有提到：
冒泡排序 O(n^2),稳定
希尔排序 O(n^2) 不稳定
选择排序 O(n^2)  不稳定