本文转载： https://www.cnblogs.com/zhaoshuai1215/p/3448154.html
排序算法可以说是一项基本功，解决实际问题中经常遇到，针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率，有时候排序的稳定性还是实际问题中必须考虑的。这篇文章对常见的排序算法进行整理，包括比较排序（插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、希尔排序、二叉树排序），非比较排序（计数排序、桶排序、基数排序）。
比较排序和非比较排序： 常见的排序算法都是比较排序，非比较排序包括计数排序、桶排序和基数排序，非比较排序对数据有要求，因为数据本身包含了定位特征，所以才能不通过比较来确定元素的位置。比较排序的时间复杂度通常为O(n2)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。
比较排序时间复杂度为O(nlogn)的证明：
a1,a2,a3……an序列的所有排序有n!种，所以满足要求的排序a1',a2',a3'……an'（其中a1'<=a2'<=a3'……<=an'）的概率为1/n!。基于输入元素的比较排序，每一次比较的返回不是0就是1，这恰好可以作为决策树的一个决策将一个事件分成两个分支。比如冒泡排序时通过比较a1和a2两个数的大小可以把序列分成a1,a2……an与a2,a1……an（气泡a2上升一个身位）两种不同的结果，因此比较排序也可以构造决策树。根节点代表原始序列a1,a2,a3……an，所有叶子节点都是这个序列的重排（共有n!个，其中有一个就是我们排序的结果a1',a2',a3'……an'）。如果每次比较的结果都是等概率的话（恰好划分为概率空间相等的两个事件），那么二叉树就是高度平衡的，深度至少是log(n!)。
又因为 1. n! < nn ,两边取对数就得到log(n!)<nlog(n)，所以log(n!) = O(nlogn).
2. n!=n(n-1)(n-2)(n-3)…1 > (n/2)^(n/2) 两边取对数得到 log(n!) > (n/2)log(n/2) = Ω(nlogn)，所以 log(n!) = Ω(nlogn)。
因此log(n!)的增长速度与 nlogn 相同,即 log(n!)=Θ(nlogn)，这就是通用排序算法的最低时间复杂度O(nlogn)的依据。
每种排序算法的原理和实现（以下所有实现都是实现从小到大排序）
1）插入排序（把a[i]插入到a[0]...a[i-1]的合适位置）
原理：遍历数组，遍历到a[i]时，a0,a1...ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前的比较，如果不小于，在放在正在比较的元素之后。可见相等元素比较是原来靠后的还是排在后边，所以插入排序是稳定的。
当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。
1 function insertion_sort(int a[],int n){ 2 int i,j,v; 3 for(i=1;i<n;i++){ 4 //比较处理a[i] 5 for(v=a[i],j=i-1;v<a[j];j--){ 6 a[j+1]=a[j]; 7 } 8 a[j+1]=v; 9 } 10 }
2）选择排序（从a[i-1]后续元素中选择最小的放到a[i]位置）
原理：遍历数组，遍历到i时，a0,a1...ai-1是已经排好序的，然后从i到n选择出最小的，记录下位置，如果不是第i个，则和第i个元素交换。此时第i个元素可能会排到相等元素之后，所以选择排序是不稳定的。
function selection_sort(int a[],int n){ int i,j,pos,temp; for(i=0;i<n-1;i++){ //查询最小值的下标,记录在pos中 for(pos=i;j=i+1;j<n;j++){ if(a[pos]>a[j]){ pos=j; } } if(pos!=i){ temp = a[i]; a[i] = a[pos]; a[pos] = temp; } } }
3）冒泡排序
冒泡排序名字很形象，实际实现是相邻两个节点做比较，大的向后移一个，经过第一轮两两比较和移动，最大的元素就移动到了最后，第二轮次大的元素移动到了倒数第二个，依次进行。冒泡排序相等元素位置不会发生交换，是稳定的。这是最基本的冒泡排序，可以进行优化。
优化一：如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个Flag做标记，默认为false，如果发生交换则置为true，每轮结束时检查Flag，如果为true则继续，如果为false则返回。
优化二：某一轮结束位置为i，但是这一轮的最后发生交换位置为lastSwap，则lastSwap到i之间是排好序的，下一轮结束点就不必是i--了，而直接到lastSwap即可，代码如下：
1 function bubble_sort(int a[],int n){ 2 int i,j,lastSwap,temp; 3 for (i=n-1;i>0&&flag;i=lastSwap){
flag = false; 4 for(j=0;j<i;j++){ 5 if(a[j]>a[j+1]){ 6 temp = a[j+1]; 7 a[j+1] = a[j]; 8 a[j] = temp;
flag = true; 9 //最后一次交换位置的坐标 10 lastSwap = j;
11 } 12 } 13 } 14 }
4）快速排序
原理：快速排序首先找到一个基准存储到pivot中，用（L）标识数组查询左端，用（R）标识数组查询右端，一般以第一个元素作为基准（pivot）。 然后先从最右边（R）向左搜索，如果发现比pivot小的，则把改元素放到a[L]中，L++，然后再从左（L）向右搜索，如果发现比pivot大的，则将其放到a[R]中（注意此时a[R]的值早就放到左端了，此时a[R]的值早就没用了，这也是为什么右一个左一个查找的原因）。经过一轮比较后pivot的值就正好排在了排好序后应该在的位置，而pivot左端的都是小于等于他的值，右端的都是大于等于它的值。之后对左右两端递归调用该方法，最后就完成了排序。快速排序是一种不稳定的排序。
1 //划分定位基准值 2 int mPartition(int a[],int L,int R){ 3 int pivot = a[L]; 4 while(L<R){ 5 while(L<R && a[R]>pivot){//正常，继续往左查找 6 R--; 7 } 8 if(L<R){//将小值放到左端 9 a[L]=a[R]; 10 L++; 11 } 12 while(L<R && a[L]<pivot){ 13 L++; 14 } 15 if(L<R){//将大值放到右端 16 a[R]=a[L]; 17 R--; 18 } 19 } 20 //将基准值放到正确位置L,返回改位置作为下次查找定界 21 a[L] = pivot; 22 return L; 23 } 24 25 //快速查找 26 void quick_sort(int a[],int L,int R){ 27 int q; 28 if(L<R){ 29 q = mPartition(a,L,R); 30 //递归调用 31 quick_sort(a,L,q-1); 32 quick_sort(a,q+1,R); 33 } 34 }
5）堆排序
原理：堆排序是把数组看成堆，第i个节点的孩子为2*i+1和2*i+2个结点（不超出数组长度前提下）。第一步：将无序数组建成一个堆（升序建大顶堆，降序建小顶堆）；第二步：将堆顶元素与末尾交换，最大元素“沉”到数组末端；第三步：重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整和交换步骤，直到整个序列有序。
下述代码使用大顶堆（从小到大排序）。堆排序的过程是自左向右，自底向上的，这样在调整某个节点时，其左节点和右节点已经是满足条件的，两个节点不需要动，整个子树也不需要动了。堆排序的主要时间花在初始建堆期间，堆排序是一种不稳定排序。堆排序不适宜记录数较少的排序。
1 //建堆 2 void headAdjust(int a[],int i,int nLength){ 3 int nChild,nTemp; 4 for(nTemp = a[i];2*i+1 < nLength;i = nChild){ 5 //子节点位置 = 2*（父节点位置）+1; 6 nChild = 2 * i + 1; 7 //获取子节点中较大的节点 8 if(nChild < nLength-1 && a[nChild +1] > a[nChild]){ 9 nChild ++; 10 } 11 //如果较大的子节点大于父节点那么把子节点往上移，替换父节点 12 if(nTemp < a[nChild]){ 13 a[i] = a[nChild]; 14 a[nChild] = nTemp; 15 }else{//子节点不需要动，则整个子树不需要动 16 break; 17 } 18 } 19 } 20 21 //堆排序 22 void heap_sort(int a[],int length){ 23 int temp; 24 //堆排序从左到右从底向上排序，所以从最后一个非叶节点开始（length/2-1）;不要错误思考，数组变成堆的过程是a[0]为堆定，依次往下推的，而是不前边说的从左到右，从底向上，这个是指遍历顺序 25 for(int i = length/2-1; i>=0;i--){ //先把a[0]元素搞成最大值，用于下面for循环的第一次交换 26 headAdjust(a,i,length) 27 } 28 //交换堆顶和最后一个子元素，重新执行建堆操作 29 for(int i = length-1;i>0;i--){ 30 temp = a[0]; 31 a[0] = a[i]; 32 a[i] = temp; 33 headAdjust(a,0,i); //此时除了堆顶元素不符合大顶堆要求，其他已经都符合了，所以这时就不像第一次for循环中那样需要先从左到右从底向上了，只需要调整a[0]这个堆顶即可。 34 } 35 }
6）归并排序
原理：归并排序是分之策略的典型应用。其基本思想是：首先考虑将两个有序数列合并时，这个非常简单，只要比较两个数列的第一个数，然后谁小取谁，取了之后在对应数列中删除这个数，然后继续比较。如果有数列为空，那将另一个数列中剩余的数取出来即可。归并排序首先将数列采用递归方式分成两两有序数列，然后按照上述方式归并生成新数列，然后再一步步向上回归，最终归并成完整有序数列。
有的地方可以看到在mergeArray中合并有序数列是分配临时数组，即每一步在mergeArray的结果都存放在一个新的临时数组中，每次在mergeArray中新建一个数组在递归中会消耗大量的空间。这里做一个小小的变化，只需要在merge_sort中新建一个数组，并传入mergeArray中，后面的操作都会公用这个临时数组，合并完后将临时数组中的数据写会原数组中。这样仅需要与原始数据同样数量的存储空间存放归并数据，因此空间复杂度为O(n)。
归并排序中数据两两比较，不存在跳跃，因此归并排序是一种稳定排序。
1 //合并连个有序数组 2 void mergeArray(int a[],int first ,int mid,int last,int temp){ 3 int i=first,j=mid+1; 4 int m = mid,n=last; 5 int k=0; 6 while(i<=m && j<=n){ 7 if(a[i]<=a[j]){ 8 temp[k++] = a[i++]; 9 }else{ 10 temp[k++] = a[j++]; 11 } 12 } 13 //如果第一个数组还有剩余数据，直接取出插入 14 while(i<=m){ 15 temp[k++] = a[i++]; 16 } 17 //如果第二个数组还有剩余数据，直接取出插入 18 while(j<=n){ 19 temp[k++] = a[j++]; 20 } 21 //存回原数组 22 for(i=0;i<k;i++){ 23 a[first+i] = temp[i]; 24 } 25 } 26 27 //归并排序 28 void merge_sort(int a[],int first,int last,int temp[]){ 29 if(first<last){ 30 int mid = (first+last)/2; 31 merge_sort(a,first,mid,temp);//使左边有序 32 merge_sort(a,mid+1,last,temp);//使右边有序 33 mergeArray(a,first,mid,last,temp);//将左右两边合并 34 } 35 }
7）希尔排序（改进的插入排序）
原理：希尔排序是对 插入排序的优化，其基于以下两个认识：1.数据量较小时插入排序速度较快，因为n和n2差距很小；2.数据基本有序时插入排序效率很高，因为比较和移动的数据量小。
因此，希尔排序的基本思想是将需要排序的序列划分成为若干个较小的序列，对子序列进行插入排序，然后对较小的有序数列再进行插入排序，这样能够提高排序算法的效率。
希尔排序划分子序列不是像归并排序那样的二分，而是采用的叫做增量的技术，列如对有10个元素的数组进行希尔排序，首先增量设为10/2=5,此时第一个元素和第（1+5）个元素配对成子序列使用插入排序进行排序，第2和第（2+5）个元素组成子序列……，完成后增量继续减半为2，此时第一个元素和第（1+2）、（1+4）、（1+6）、（1+8）个元素组成子序列进行插入排序。这种增量选择方法的好处是可以使数组整体均匀有序，尽可能的减少比较和移动的次数。而二分法中即使前一半有序，后一半中如果有较小的数据，还是会造成大量的比较和移动，因此这用增量的方法和插入排序的配合更加。
希尔排序的时间复杂度和增量的选择策略有关，希尔排序是一种不稳定排序。
1 void shell_sort(int a[],int length){ 2 int step,i,j,temp; 3 for(step = length/2;step>=1;step = step/2){//增量每次减半，减到1时完成排序 4 for(i = step;i<length;i++){ 5 temp = a[i];//temp为插入排序中本轮待插入的元素a【i】，此时a[i-step]...已有序 6 for(j = i-step;j>=0&&a[j]>temp;j = j-step){//a[i]寻找和自己同组的元素进行比较 7 a[j+step] = a[j];//大的元素往后移 8 } 9 a[j+step] = temp;//将temp放在最终位置 10 } 11 } 12 }
8）二叉树排序
原理：二叉树排序借助了数据结构中二叉排序数，二叉排序树满足三个条件：（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3）左、右子树也分别为二叉排序树。根据这三个特点，用中序遍历二叉树得到的结果就是排序的结果。
二叉树排序法需要首先根据数据构建二叉排序树，然后中序遍历，排序时间复杂度为O(nlogn)，构建二叉树需要额外的O(n)的存储空间，二叉树排序是稳定的。
在实现此算法的过程中遇到不小的困难，指正参数在函数中无法通过new赋值，后来采取指针地址，然后函数设置BST** tree的方式解决。
1 int arr[] = {7, 8, 8, 9, 5, 16, 5, 3,56,21,34,15,42}; 2 3 struct BST{ 4 int number;//保存数组元素的值 5 struct BST * left; 6 struct BST * right; 7 8 }; 9 10 void insertBST(BST**tree,int v){ 11 if(*tree == NULL){ 12 *tree = new BST; 13 (*tree)->left = (*tree)->right = NULL; 14 (*tree)->number = v; 15 return; 16 } 17 if(v<(*tree)->left){ 18 insertBST(&((*tree)->left), v); 19 }else{ 20 insertBST(&((*tree)->right), v); 21 } 22 23 } 24 25 void printResult(BST * tree){ 26 if(tree == NULL){ 27 return; 28 } 29 if(tree->left!=NULL){ 30 printResult(tree->left); 31 } 32 cout << tree->number << " "; 33 if(tree->right !=NULL){ 34 printResult(tree->right); 35 } 36 } 37 38 void createBST(BST ** tree,int a[],int n){ 39 *tree = NULL; 40 for(int i =0;i<n;i++){ 41 insertBST(tree,a[i]); 42 } 43 } 44 45 int main(){ 46 int n = sizeof(arr)/sizeof(int);//计算数组元素个数，因为数组元素为int型，所以/sizeof(int) 47 BST * root; 48 creatBST(&root,arr,n); 49 printResult(root); 50 }