关于各种排序的一些见解

众所周知，排序是一种基础算法。新手在入门时几乎都会接触到这类问题，这些问题可以练习对基础语言的掌握能力，如对数组的处理。 排序常见的有冒泡、桶、归并、快排（甚至可以利用优先队列或者是红-黑树）。但是常用的就是归并和快排。 还有一种是一本通上讲的插入排序，复杂度为 ，做法基本和下面冒泡的算法一样。 冒泡的话时间开销有点大，效率也是 ，但有时求数组中的最大值也会用到冒泡的思想，例如 ```cpp for(int i=1;i<=n;i++) { if(a[i]>Max) Max=a[i]; } ``` ----- 桶排也就是开一个数据范围非常大的数组，空间开销非常大，在函数里面一维数组只能开500,000左右，全局数组的话可以开到400,000,000（4亿），但这样的话，在函数里面能排的数据有限，但是排多了又会使空间超限。从另一个角度，在输出结果时，桶排序需要从头到尾遍历，时间复杂度是 。在联赛这种既卡时间又卡空间的情况下，以上两种都不能选。 归并排序的用途比较广，它可以用来求逆序对。和快速排序一样时间复杂度是 用作一般的排序不失为一种很明智的选择。那么现在进入正题，谈一谈常见的快速排序。 快速排序(quicksort)是20世纪60年代提出的一种算法，类似于归并，也有分治的一种思想，即找到一个基准数，将比它大的放在它的右边，比它小的放在它的左边。 1. 基准数位置。 基准数的位置在教科书中一般选为最左边或最右边，我一般习惯于选最左边。不同选择对执行没有较大的影响。 2. 左右移动的方式 目前我所见到的移动的方式，主要有两种， 一是j（从右）找到一个比基准数（记作k）小的数，然后让i（从左）找到一个比k大的数，然后进行交换。直到i，j相遇开始分治处理； ```cpp void quick_sort(int x,int y) { int i=x,j=y,t;//t用于稍后的交换 int k=a[x]; if(i>=j) return; while (i<j) { while((i<j)&&a[j]>=k) j--; t=a[i]; a[i]=a[j]; a[j]=t; while((i<j)&&(a[i]<k)) i++; t=a[i]; a[i]=a[j]; a[j]=t; } quick_sort(x,i-1); quick_sort(i+1,y); return; } ``` 另一种是 基准数记作k，基准数下标记作x ① i（从左）找到一个比k大的数,a[x]=a[i]； ② j（从右）找到一个比k小的数,a[i]=a[j]； ③ i（从左）找到一个比k大的数,a[j]=a[i]； ④ 重复②③直到i==j； ⑤ 将a[i]赋值为基准数k； 第一种是快排的原始思想，交换->分治，但是借用了t来交换a[i]和a[j]； 第二种的思想巧妙一些，没有用一次三句话操作，而是每次交换，都可以保证a[i]>a[j]。 ```cpp void quicksort(int x,int y) { int i=x,j=y; int k=a[x]; if(i>=j) return; while(i<j) { while(i<j&&a[j]>k) j--; if(i<j) { a[i]=a[j]; i++; } while(i<j&&a[i]<=k) i++; if(i<j) { a[j]=a[i]; j--; } } a[i]=k; quicksort(x,i-1); quicksort(i+1,y); } ``` 以上谈的快速排序两种方法，大致上没有较大区别，只不过在处理交换操作时，一个老老实实用了交换，另一个用了较巧妙的“赋值”，总体上看复杂度不相上下，但是我想当数据较大的时候可能会还是会有所区别。 如有不对的地方，敬请指正。