排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便，通常希望计算机中的表是按关键字有序的。排序的确切定义如下： 输入： n n n个记录 R 1 , R 2 , . . . , R n R_1,R_2,...,R_n R1​,R2​,...,Rn​，对应的关键字为 k 1 , k 2 , . . . , k n k_1,k_2,...,k_n k1​,k2​,...,kn​。 输出：输入序列的一个重排 R 1 ′ , R 2 ′ , . . . , R n ′ {R_1}^{'},{R_2}^{'},...,{R_n}^{'} R1​′,R2​′,...,Rn​′，使得 k 1 ′ ≤ k 2 ′ ≤ . . . ≤ k n ′ {k_1}^{'}≤{k_2}^{'}≤...≤{k_n}^{'} k1​′≤k2​′≤...≤kn​′（其中“ ≤ ≤ ≤”可以换成其他比较大小的符号）

排序的稳定性。假设 k i = k j ( 1 ≤ i ≤ n , 1 ≤ j ≤ n , i ! = j ) k_i=k_j(1≤i≤n,1≤j≤n,i!=j) ki​=kj​(1≤i≤n,1≤j≤n,i!=j)，且在排序前的序列中 R i R_i Ri​领先于 R j R_j Rj​(即 i < j i int temp = L->R[i]; L->R[i] = L->R[j]; L->R[j] = temp; } 常见的排序算法 一、冒泡排序（交换排序） 1、算法

冒泡排序的基本思想是：从后往前(或从前往后)两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置)，关键字最小的元素如气泡一般逐渐往上“漂浮”直至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素(或最大元素)放到了序列的最终位置…这样最多做 n − 1 n-1 n−1趟冒泡就能把所有元素排好序。 如下图所示，我们对序列 { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 } \{49,38,65,97,76,13,27,49\} {49,38,65,97,76,13,27,49}进行冒泡排序： 冒泡排序算法的代码如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O ( 1 ) O(1) O(1)。 时间效率：当初始序列有序时，显然第一趟冒泡后flag依然为false (本趟冒泡没有元素交换)，从而直接跳出循环，比较次数为 n − 1 n-1 n−1，移动次数为 0 0 0，从而最好情况下的时间复杂度为 O ( n ) O(n) O(n)；当初始序列为逆序时，需要进行 n − 1 n- 1 n−1趟排序，第 i i i趟排序要进行 n − i n -i n−i次关键字的比较，而且每次比较后都必须移动元素 3 3 3次来交换元素位置。这种情况下， 比 较 次 数 = ∑ i = 1 n ( n − i ) = n ( n − 1 ) / 2 比较次数=\displaystyle\sum_{i=1}^{n}(n-i)=n(n-1)/2 比较次数=i=1∑n​(n−i)=n(n−1)/2 移 动 次 数 = ∑ i = 1 n 3 ( n − i ) = 3 n ( n − 1 ) / 2 移动次数=\displaystyle\sum_{i=1}^{n}3(n-i)=3n(n-1)/2 移动次数=i=1∑n​3(n−i)=3n(n−1)/2从而，最坏情况下的时间复杂度为 O ( n 2 ) O(n^2) O(n2),其平均时间复杂度也为 O ( n 2 ) O(n^2) O(n2)。

简单选择排序法(Simple Selection Sort) 就是通过 n − i n-i n−i次关键字间的比较，从 n − i + 1 n-i+1 n−i+1个记录中选出关键字最小的记录，并和第 i ( 1 < i < n ) i (1 //一共进行n-1趟 min = i; //记录最小元素位置 for(j=i+i; jlength; j++){ if(L->R[j] R[min]){ //在R[i...n-1]中选择最小的元素 min = j; //更新最小元素位置 } } if(min !=i){ swap(L->R[i], L->R[min]); //swap函数移动元素3次 } } } 2、性能分析

空间效率：仅使用常数个辅助单元，故空间效率为 O ( 1 ) O(1) O(1)。 时间效率：从上述代码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过 3 ( n − 1 ) 3(n-1) 3(n−1)次，最好的情况是移动 0 0 0次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是 n ( n − 1 ) / 2 n(n- 1)/2 n(n−1)/2次，因此时间复杂度始终是 O ( n 2 ) O(n^2) O(n2)。 稳定性：在第 i i i趟找到最小元素后，和第 i i i个元素交换，可能会导致第 i i i个元素与其含有相同关键字元素的相对位置发生改变。例如，表 L = { 2 , 2 , 1 } L= \{2,2, 1\} L={2,2,1}，经过一趟排序后 L = { 1 , 2 , 2 } L= \{1, 2,2\} L={1,2,2}，最终排序序列也是 L = { 1 , 2 , 2 } L=\{1,2,2\} L={1,2,2}，显然， 2 2 2与 2 2 2的相对次序已发生变化。因此，简单选择排序是一种不稳定的排序方法。

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

假定初始序列为 { 49 , 38 , 65 , 97 , 76 , 13 , 27 , 49 } \{49, 38, 65, 97 ,76, 13, 27, 49\} {49,38,65,97,76,13,27,49}，初始时 49 49 49可以视为一个已排好序的子序列，按照上述算法进行直接插入排序的过程如下图所示，括号内是已排好序的子序列。

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O ( 1 ) O(1) O(1)。 时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了 n − 1 n-1 n−1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。 在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为 O ( n ) O(n) O(n)。 在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反(逆序)，总的比较次数达到最大，为 ∑ i = 2 n i \displaystyle\sum_{i=2}^{n}i i=2∑n​i，总的移动次数也达到最大，为 ∑ i = 2 n ( i + 1 ) 。 \displaystyle\sum_{i=2}^{n}(i+1)。 i=2∑n​(i+1)。 平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 n 2 / 4 n^2/4 n2/4。 因此，直接插入排序算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。 适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

从直接插入排序算法中，每趟插入的过程中都进行了两项工作：①从前面的有序子表中查找出待插入元素应该被插入的位置；②给插入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。

从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 n n n；而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为 O ( n 2 ) O(n^2) O(n2)，但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。

希尔排序是对直接插入排序进行改进而得来的，又称缩小增量排序。 希尔排序的基本思想是：先将待排序表分割成若干形如 L [ i , i + d , i + 2 d , . . . , i + k d ] L[i,i+d,i+ 2d,...,i+ kd] L[i,i+d,i+2d,...,i+kd]的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。 希尔排序的过程如下：先取一个小于 n n n的步长 d 1 d_1 d1​，把表中的全部记录分成 d 1 d_1 d1​组，所有距离为 d 1 d_1 d1​的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个步长 d 2 < d 1 d_2 increment = increment/3 + 1; //增量序列 for(i = increment+1; i length; i++){ if(L-R[i] R[i-increment]){ /*需将L->R[i]插入有序增量子表*/ L->R[0] = L->R[i]; //暂存R[0] for(j = i-increment; j>0 && L->R[0]R[j]; j-=increment){ L->R[j+increment] = L->R[j]; //记录后移，查找插入位置 } L->R[j+increment] = L->R[0]; //插入 } } }while(increment > 1); }

例如，当传入的SqList的的 l e n g t h = 9 length=9 length=9， R [ 10 ] = { 0 , 9 , 1 , 5 , 8 , 3 , 7 , 4 , 6 , 2 } R[10]=\{0,9,1,5,8,3,7,4,6,2\} R[10]={0,9,1,5,8,3,7,4,6,2}。排序的大致过程下图所示。

第一轮increment=4： 第二轮increment=2： 第三轮increment=1： 最终结果：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O ( 1 ) O(1) O(1)。 时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当 n n n在某个特定范围时，希尔排序的时间复杂度约为 O ( n 3 / 2 ) O(n^{3/2}) O(n3/2)。要好于直接排序的 O ( n 2 ) O(n^2) O(n2)。 稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。 适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

堆排序(Heap Sort)是对简单选择排序进行的一种改进。

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆(如下图所示)；或者每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。

堆排序的思路很简单：首先将存放在 L [ 1... n ] L[1...n] L[1...n]中的 n n n个元素建成初始堆，由于堆本身的特点(以大顶堆为例)，堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。可见堆排序需要解决两个问题：①如何将无序序列构造成初始堆?②输出堆顶元素后，如何将剩余元素调整成新的堆?

堆排序的关键是构造初始堆。 n n n个结点的完全二叉树，最后一个结点是第 ⌊ n / 2 ⌋ ⌊n/2⌋ ⌊n/2⌋个结点的孩子。对第 ⌊ n / 2 ⌋ ⌊n/2⌋ ⌊n/2⌋个结点为根的子树筛选(对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换)，使该子树成为堆。之后向前依次对各结点( ⌊ n / 2 ⌋ − 1 ⌊n/2⌋ -1 ⌊n/2⌋−1~ 1 1 1)为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。 举例自上往下逐步调整为大根堆，如下图所示。 继续已上图为例： 输出堆顶元素后，将堆的最后一个元素与堆顶元素交换，此时堆的性质被破坏，需要向下进行筛选。将 09 09 09和左右孩子的较大者 78 78 78交换，交换后破坏了子树的堆，继续对子树向下筛选，将 09 09 09和左右孩子的较大者 65 65 65交换，交换后得到了新堆，调整过程如下图所示。

下面是建立大根堆的算法：

函数HeadAdjust将元素k为根的子树进行调整。

调整的时间与树高有关，为 O ( h ) O(h) O(h)。在建含 n n n个元素的堆时，关键字的比较总次数不超过 4 n 4n 4n，时间复杂度为 O ( n ) O(n) O(n)，这说明可以在线性时间内将一个无序数组建成一个堆。 下面是堆排序算法：

同时，堆也支持插入操作。对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点向上执行调整操作。大根堆的插入操作示例如下图所示。

堆排序适合关键字较多的情况(如n>1000)。例如，在1亿个数中选出前100个最大值？首先使用一个大小为100的数组，读入前100个数，建立小顶堆，而后依次读入余下的数，若小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆，待数据读取完毕，堆中100个数即为所求。

空间效率：仅使用了常数个辅助单元，所以空间复杂度为 O ( 1 ) O(1) O(1)。 时间效率：建堆时间为 O ( n ) O(n) O(n)，之后有 n − 1 n-1 n−1次向下调整操作，每次调整的时间复杂度为 O ( h ) O(h) O(h)，故在最好、最坏和平均情况下，堆排序的时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)。 稳定性：进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序算法是一种不稳定的排序方法。

归并排序与上述基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有 n n n个记录，则可将其视为 n n n个有序的子表，每个子表的长度为 1 1 1，然后两两归并，得到 ⌈ n / 2 ⌉ ⌈n/2⌉ ⌈n/2⌉个长度为 2 2 2或 1 1 1的有序表；继续两两…如此重复，直到合并成一个长度为 n n n的有序表为止，这种排序方法称为 2 2 2路归并排序。 下图所示为 2 2 2路归并排序的一个例子，经过三趟归并后合并成了有序序列。 Merge()的功能是将前后相邻的两个有序表归并为一个有序表。设两段有序表 A [ l o w . . . m i d ] A[low...mid] A[low...mid]、 A [ m i d + 1... h i g h ] A [mid+1...high] A[mid+1...high]存放在同一顺序表中的相邻位置，先将它们复制到辅助数组 B B B中。每次从对应 B B B中的两个段取出一个记录进行关键字的比较，将较小者放入 A A A中，当数组 B B B中有一段的下标超出其对应的表长(即该段的所有元素都已复制到 A A A中)时，将另一段中的剩余部分直接复制到 A A A中。算法如下：

一趟归并排序的操作是，调用 ⌈ n / 2 h ⌉ ⌈n/2h⌉ ⌈n/2h⌉次算法 m e r g e ( ) merge() merge()，将 L [ 1... n ] L[1...n] L[1...n]中前后相邻且长度为 h h h的有序段进行两两归并，得到前后相邻、长度为 2 h 2h 2h的有序段，整个归并排序需要进行 ⌈ l o g 2 n ⌉ ⌈log_2n⌉ ⌈log2​n⌉趟。递归形式的 2 2 2路归并排序算法是基于分治的，其过程如下。 分解：将含有 n n n个元素的待排序表分成各含 n / 2 n/2 n/2个元素的子表，采用 2 2 2路归并排序算法对两个子表递归地进行排序。 合并：合并两个已排序的子表得到排序结果。

快速排序的基本思想是基于分治法的：在待排序表 L [ 1... n ] L[1...n] L[1...n]中任取一个元素 p i v o t pivot pivot作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 L [ 1... k − 1 ] L[1...k-1] L[1...k−1]和 L [ k + 1... n ] L[k+1...n] L[k+1...n]，使得 L [ 1... k − 1 ] L[1...k-1] L[1...k−1]中的所有元素小于 p i v o t pivot pivot， L [ k + 1... n ] L[k+1...n] L[k+1...n]中的所有元素大于等于 p i v o t pivot pivot，则 p i v o t pivot pivot放在了其最终位置 L ( k ) L(k) L(k)上，这个过程称为一趟快速排序(或一次划分)。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。 一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针 i i i和 j j j，初值分别为 l o w low low和 h i g h high high，取第一个元素 49 49 49为枢轴赋值到变量 p i v o t pivot pivot。 指针j从 h i g h high high往前搜索找到第一个小于枢轴的元素 27 27 27，将 27 27 27交换到 i i i所指位置。 指针 i i i从 l o w low low往后搜索找到第一个大于枢轴的元素 65 65 65，将 65 65 65交换到 i i i所指位置。 指针 j j j继续往前搜索找到小于枢轴的元素 13 13 13，将 13 13 13交换到i所指位置。 指针 i i i继续往后搜索找到大于枢轴的元素 97 97 97，将 97 97 97交换到j所指位置。 指针j继续往前搜索小于枢轴的元素，直至 i = = j i==j i==j。 此时 i = = j i==j i==j，指针 i i i之前的元素均小于 49 49 49，指针 i i i之后的元素均大于等于 49 49 49，将 49 49 49放在 i i i所指位置即其最终位置，经过一趟划分， 将原序列分割成了前后两个子序列。 按照同样的方法对各子序列进行快速排序，若待排序列中只有一个元素，显然已有序。 代码实现大致如下：