学步园

稳定性：

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

复杂度

冒泡法：  复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。不说了。

直接插入排序：O(n*n)

希尔排序：算法的复杂度为n的1.2次幂

选择排序：O(n*n)

快速排序：不稳定，平均时间复杂度O(nlogn)，最坏情况时间复杂度为O(n2)。所有内部排序方法中最高好的，大多数情况下总是最好的。空间复杂度主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)

归并排序：log2(n)*n

堆排序：log2(n)*n

1. 建立最大堆（堆顶的元素大于其两个儿子，两个儿子又分别大于它们各自下属的两个儿子… 以此类推）

2. 将堆顶的元素和最后一个元素对调（相当于将堆顶元素（最大值）拿走，然后将堆底的那个元素补上它的空缺），然后让那最后一个元素从顶上往下滑到恰当的位置（重新使堆最大化）。

3. 重复第2步。

（表来源：http://blog.csdn.net/ns_code/article/details/20540069）

算法实现：

首先是快速排序的实现

void quickSort(int A[], int low, int high){
      if(low < high){
        int i = low, j = high, key = A[i];   //A[i]挖一个坑
        while(i < j){
           while(i < j && A[j] > key) // 从右向左找第一个小于key的数
              --j;
            if(i < j)
              A[i++] = A[j];
            while(i < j && A[i] < key) // 从左向右找第一个大于等于key的数
              ++i;
            if(i < j)
              A[j--] = A[i];    
        }
        A[i] = key;                              //mid
        quickSort(A,low,i-1);
        quickSort(A,i+1,high);
      }
}

堆排序

画图理解更佳，每次把最大的移到堆顶，然后放回最底输出，如此循环，得到排序

    #include <iostream>  
    using namespace std;  
    void maxHeap(int a[], int no, int last){  //O(n), 要筛选的节点编号为no  
        int mi= no;  
        int l = mi<< 1;    // 编号为no的节点的左孩子  
        int r = (mi<< 1)+1;
          if(l <= last && a[l] > a[mi])  
              mi= l;
          if(r <= last && a[r] > a[mi])
              mi= r;  
         if(mi != no)
         swap(a[mi],a[no]);     //将较大的节点移到根上。  
          
    }  
    void makeHeap(int a[], int root, int last){  
        int n  = last;  
        for(int i = n/2; i > 0; i--)  //i逆序递减的原因：任何时候对结点i调用maxheap，该i的两个子树都是最大堆  
            maxHeap(a,i,n);  
        swap(a[1],a[last]);   
    }  
    void heapSort(int a[], int lenght){  //O(nlgn),调用heapsort(a, n)对数组a排序  
      for(int i = 1; i <= lenght; i++)  
         makeHeap(a,1,lenght-i+1);  
    }  
    int main(){  
        int r[] = {0,15,28,32,25,18,16,2222,-2};  
        heapSort(r, 8);  
        for(int i = 1; i < 9; i++)  
            cout << r[i] << endl;  
        return 0;  
    }