一直以来对于排序算法总有些熟悉又陌生的感觉，这几天看到一篇挺不错的博客讲排序的，http://blog.csdn.net/xiazdong/article/details/8462393 于是学习参考他的思路自己动手用php实现了一下。并且结合每个算法的特性思路写了这篇博客。
源码可以直接在github上down，也欢迎修改 https://github.com/fangkehang/php_sort 最好是结合代码看思路，会比较清楚。
· In-place sort（不占用额外内存或占用常数的内存）：插入排序、选择排序、冒泡排序、堆排序、快速排序。 · Out-place sort：归并排序、计数排序、基数排序、桶排序。 当需要对大量数据进行排序时，In-place sort就显示出优点，因为只需要占用常数的内存。 · 设想一下，如果要对10000个数据排序，如果使用了Out-place sort， 则假设需要用200G的额外空间，则一台老式电脑会吃不消，但是如果使用In-place sort，则不需花费额外内存。
· stable sort：插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序。 · unstable sort：选择排序(5 8 5 2 9)、快速排序、堆排序。 稳定性是指两个一样的元素排位是否稳定，这对于基数排序特别重要
答：插入执行时间至少比冒泡排序快，插入排序的速度直接是逆序对的个数，而冒泡排序中执行“交换“的次数是逆序对的个数，因此冒泡排序执行的时间至少是逆序对的个数, 下面在算法中会更加清楚的解释说明。
介绍：选择排序是所有排序中最简单的，相信很多没有接触排序算法的程序员都可以自己想出这个排序。 思路：思路很清晰，每一次内层遍历找出最小的数，然后进行n-1次，找出n-1个最小的依次排好即可。
递归版：递归版也是相当直观，因为每次照最小的步骤都是一样的，所以可以用一个function表示，然后每一次递归调用这个function即可。 算法特性：In-place sort，unstable sort 时间复杂度分析：无论正序逆序乱序，总之两层循环必不可少，所以它的最佳最差复杂度都是O(n^2)。虽然这个算法从思路到实现都很容易，但性能是最差的，所以学过的算法的程序猿们就不能再用这个方法了。
/** * 选择排序 **/ void select(int a[], int num) { for(int i = 0; i<num; i++) { for(int j = i+1; j<num ; j++) { if(a[i] > a[j]) { exchange(&a[i], &a[j]); } } } }介绍：顾名思义，这个算法是仿照现实生活中水中气泡，小气泡先冒出，大气泡后冒出的思想产生的。 思路：每一次都浮出一个最小的数，所以外层需要n-1次，内层从后往前，每相邻两个进行比较，当后面的小于前面时，就交换，这样就可以把最小的数一直排到前方去了。
递归版：递归版的思路跟选择排序是一样的，每一次的冒泡实际上是同样的操作，所以递归调用function即可。 改进版：这个算法还有个改进之处，观察上图，你是不是发现从3到n实际上是排好序了的。对，结合这个思路，只要你在某一趟冒泡中，发现不需要进行任何一次交换，这就说明其实这个数列就已经是有序了，可以提前结束算法。这个用程序来实现可以通过一个flag变量来标识，单有交换把flag设为true，每一趟遍历结束要是发现flag为false，就可以提前结束程序了。 算法特性：stable sort、In-place sort 时间复杂度分析未改进时候：无论正序逆序乱序，两趟遍历是必不可少的，所以最佳最差复杂度也是O(n^2). 然而，改进之后，当正序时，外层就不用遍历了，在内层遍历一次就可以发现不需要交换，所以已经是有序就提前结束算法，所以最佳的复杂度是O(n)，这种情况就会跟插入排序是一个效率的。
/** * 冒泡排序 * @param flag: 当一趟跑完，发现不需要任何冒泡交换，说明已经有序，提前结束算法。 **/ void bubble(int a[], int num) { int i ,flag = 1; for(i = 0; i<num; i++) { if(flag == 0) { return; } flag = 0; for(int j = num;j > i;j--) { cout << j ; if(a[j] < a[j-1]) { exchange(&a[j],&a[j-1]); flag = 1; } } var_dump(a,5); } }介绍： 插入排序实际上我们在生活中就经常运用，大多数人扑克牌的洗牌就是采用这种方法。 思路：从第二个数往后开始遍历，遍历到的这个数之前的数列是已经排好序了的，所以把遍历到的这个数和之前最后一个数比较，比他小就跟他交换，比他大就停止。
/** * 插入排序 */ void insert(int a[],int num) { int i,j; for(i = 1; i<=num; i++) { for(j = i; j>=0 ; j--) { if(a[j] < a[j-1]) { exchange(&a[j],&a[j-1]); }else { break; } } } }递归版：递归版中我们要先假设之前的n-1个数列已经采用这个插入法排好序，所以现在只需把第n个插入过去即可。 算法特性：stable sort、In-place sort 时间复杂度分析当数组是正序的话，我们发现每一次的外层遍历，遍历到的数与前一个数比较之后不需要交换就进入下一个数了，所以内层循环不需要执行，所以最佳复杂度是O(n)；而最差的是逆序，每一个内层循环都要走到底。为O(n^2)，所以它和冒泡改进版的效率相当。
介绍：归并排序是个非常有效率的排序，但它的思想和实现不是特别直观，这个算法的地位也是特别的重要。 思路：采用的是分治的思想,实现则考虑用递归实现比较快捷方便。 归并就是把两个已有序的数组，并成一个，思路就是用两个temp的数组来存放左右两个有序数组，并使得它们最后一个数MAX_INT，然后再重新整合到原来的数组中去。
/** * 将两个有序的数列归并，采用的思路是用两个temp的数组来存放左右两个有序数组，并使得它们最后一个数MAX_INT，然后再重新整合到原来的数组中去。 * **/ void merge(int a[], int start, int middle, int end) { int i,j,k; int l[middle - start + 1 + 1],r[end - middle + 1]; //多出一位来放一个INT_MAX for(i = start,k = 0; i <= middle; i++,k++) { l[k] = a[i]; } l[k] = INT_MAX; for(j = middle+1,k = 0; j <= end; j++,k++) { r[k] = a[j]; } r[k] = INT_MAX; for(i = start,k = 0,j = 0;i<=end;i++) { if(r[k]<l[j]) { a[i] = r[k]; k++; }else{ a[i] = l[j]; j++; } } } /** * 归并排序 */ void merge_sort(int a[], int start, int end) { if(start < end) { //这步递归退出条件要记得 int middle = (end - start) / 2 + start; merge_sort(a,start,middle); merge_sort(a,middle+1,end); merge(a,start,middle,end); } }递归的思想就是 先把数列分两个，然后假设左右两边都用归并排好序了，这时候只需要把这两个归并，归并的思想从上图可知。 算法特性：stable sort、Out-place sort 时间复杂度分析 首先先看merge 归并两个有序数列的算法的时间复杂度，可见这个时间复杂度是O(n)，两个数列实际上是同时一起遍历的。 再假设归并一个n位的数列需要T(n)的时间，那么归并一个n/2，则需要T(n/2)的时间。OK，根据归并的递归式： T(n) = 2T(n/2)+O(n)，这里套用别人非常详尽的一个解释：来源于http://blog.csdn.net/yuzhihui_no1/article/details/44198701#t2
因此，这个算法的时间复杂度是相当低的。
介绍：快速排序是和归并同等级别的重要算法。 思路：思想也是分治法，每次选定左边的数做基准，从右往左找比基准小的数，再从左往右找比基准大的数，注意顺序不能颠倒。然后交换这两个。依次下去直到最后一个跟基准交换。就形成基准左边比它小，右边比它大。
这个算法采用递归来做更加快捷，只需先parition，分成左边比基准小，右边比基准大，再把左边右边递归去解决。 算法特性：unstable sort、In-place sort 时间复杂度分析 最优的情况就是刚好选到中分的点，这个时候partition只要找一次，换一下就可以了。 T[n] = 2T[n/2] +O(n) 所以O( nlogn ) 最差的情况就是当正序或者倒序的时候，这个时候就相当于冒泡排序，O(n^2) 如图这个树，左右两边是对称的，所以深度是4，但如果树顶是20，可想而知，深度将不再是4。就是这个道理。
/** * 快排 **/ int partition(int a[], int start, int end) { //random 随机化降低最坏情况出现的频率 int randNum = rand()%(end - start); exchange(&a[start],&a[randNum + start]); int i = start, j = end, temp = a[start]; while(i<j) { //一定要先从后面开始 while(i < j && a[j] > temp) { j--; } if(i < j) { a[i] = a[j]; i++; } while(i < j && a[i] < temp) { i++; } if(i < j) { a[j] = a[i]; j--; } } a[i] = temp; return i; } void quick_sort(int a[], int start,int end) { if(start < end) { int r = partition(a,start,end); quick_sort(a,start,r-1); quick_sort(a,r+1,end); } }介绍：堆排序是选择排序的一种，堆排序有大根堆和小根堆之分，原理则是一样的。 思路：
算法特性：unstable sort、In-place sort 时间复杂度分析最优时间：O(nlgn) 最差时间：O(nlgn)。这个算法性能是相当好的，但是代码量也相对较大。
首先是建立大根堆的演示和思路：
即从最后一个叶子结点开始，到第一个结点。每次调整这些非叶子结点和自己的子孙（是子孙，不仅仅是儿子）的大小关系。
void BuildMaxHeap(ElemType A[], int len) { for(int i=len/2;i>0;i--) //从叶子结点开始 AdjustDown(A,i,len); } void AdjustDown(ElemType A[],int k, int len) { A[0] = A[k]; for(i = 2* k;i<=len;i*=2){ //遍历它的子孙结点 if(i<len&&A[i]<A[i+1]) i++; if(A[0]>=A[j]) break; else{ A[k] = A[i]; k = i; } } A[k] = A[0]; }实际上只要把建立的过程给理解清楚了，后面排序的操作就会变得简单易懂
void HeapSort(ElemType A[],int len) { BuildMaxHeap(A,len); for(i=len;i>1;i--) { Swap(A[i],A[1]); //把最大的值栈顶调到最后一个去，相当于输出，因为下一步会把len缩小i-1; AdjustDown(A,1,i-1); } }此外堆还可以进行插入和删除操作。 对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点执行向上调整操作
void AdjuestUp(ElemType A[],int k) { A[0] = A[k]; int i=k/2; while(i>0&&A[i]<A[0]) { A[k] = A[i]; k = i; i = k/2; } A[k] = A[o]; }未完待续
