各种内排序有各自的优缺点，再次总结一下。
| 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
| 冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 交换 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数(0-9)， R是基数(个十百) |
| Shell | O(nlogn) O(n^1.25) ??? | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
| 堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
1、快速排序
选择数组的其中一个元素(一般为第一个)作为分界pivot，用两个游标分别从后往前和从前往后扫描数组。先从后游标开始，当后游标所指的值比pivot小，则与pivot交换，后游标交换后才扫描前游标；当前游标所指值比pivot大，则与pivot交换。一次分组的结果是pivot前面的元素全部比pivot小，后面的全部比pivot大。既然对前后两部分继续调用分组函数即可完成排序。
下面的程序对上述过程做了优化，交换的时候直接把游标所指的值覆盖到pivot的位置上，覆盖后，原来游标所指的位置作为下一次的pivot位置，准备被下一次调换时被覆盖。当前后两个游标相遇时，此位置就是pivot值在有序数组中的位置了。此优化其实就是利用了pivot的位置进行元素交换，避免了使用多余的空间。
int partition(int *p,int begin,int end){ int ipivot=begin; int pivot=p[begin]; begin++; while(begin<=end){ while(begin<=end && p[end]>=pivot){ end--; } if(begin<=end){ p[ipivot]=p[end]; ipivot=end; end--;//这里不用忘记了 } while(begin<=end && p[begin]<=pivot){ begin++; } if(begin<=end){ p[ipivot]=p[begin]; ipivot=begin; begin++;//这里不用忘记了 } } p[ipivot]=pivot; return ipivot;}void myqs(int *p,int begin,int end){ if(begin>=end){ return; } int ipivot=partition(p,begin,end); myqs(p,begin,ipivot-1); myqs(p,ipivot+1,end);} 2、堆排序
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。//插入堆数据网上调整 //对堆插入数据的时候用，插入的数据放在数组最后/*void adjust_minheap_up(int *heap,int i){ int father=(i-1)/2; int cur=i; while(father>=0){ if(heap[cur] tmp){ //左右儿子都比tmp小，调整结束 break; } heap[i]=heap[target];//把较小的移到父节点 i=target;//更新下一个处理节点 target=2*i+1;//更新target为目标节点的左儿子 } heap[i]=tmp;//找到合适位置后，放回目标节点}//由数组创建最小堆void make_min_heap(int *data,int len){ int i; for(i=len/2-1;i>=0;i--){ //叶子节点不需调整，从最后一个非叶节点开始（最后一个节点的父节点((n-1)-1)/2） adjust_minheap_down(data,len,i); }}//堆排序：先把数组构成一个最小堆。把堆顶最小的数与堆末的数对调//然后整理0到len-1的堆。这样，最小的数就累积到数组后段，并不再调整//因此，使用最小堆的堆排序是降序排序。升序排序需要使用最大堆。void heap_sort(int *heap,int len){ make_min_heap(heap,len); int i; for(i=len-1;i>=1;--i){ heap[0]^=heap[i]; heap[i]^=heap[0]; heap[0]^=heap[i]; adjust_minheap_down(heap,i,0); }}
平时的时候想要使用堆，或者面试的时候，马上写出个堆够麻烦的，其实STL的优先队列就是用堆实现的，完全可以用优先队列简单实现一个堆，下面就是使用优先队列进行堆排序的例子。
注意：优先队列默认是最大的在top，如要构造最小堆，需加入堆的基础数据结构类型（vector<int>）和greater<int>
//flag=0 is ascend,1 is descendvoid heap_sort_STL(int *p,int len,int flag){ int i; if(!flag){ //descend use min heap priority_queue ,greater > min_heap(p,p+len); for(i=0;i