【排序算法】数据结构排序详解

前言：
今天我们将讲解我们数据结构初阶的最后一部分知识的学习，也是最为“炸裂”的知识---------排序算法的讲解！！！！

1.排序的概念及其运用

1.1排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。常见的内部排序算法有：【插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、计数排序等】

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2排序运用

要说起排序，在我们日常生活的方方面面可以说都能看到。就拿我们平时网上买东西举例，当我们挑选时我们总会按照个人的需求进行排序分类，例如当我们买电脑时，会看到下图：

我们可以从很多的角度去选择我们心仪的，可以根据价格，销量等等，看榜单的排名一定层度上能反映出大众都认可的东西！！！

2.常见排序算法的实现

插入排序是一种非常直观的排序算法。其基本思想就是将一个待排序的记录按其关键字的大小插入前面以及排好序的子序列中，直到全部记录插入完成。 由插入排序的思想可以引申出三个最重要的排序算法：【直接插入排序，折半插入排序和希尔排序】

2.1 插入排序

2.1.1直接插入排序

根据上面的插入排序思想，不难得出一种最简单也是最直观的直接插入排序算法。假设在排序过程中，待排序表L【1…n】在某次排序过程中的某一时刻状态如下：

要将元素L[i]插入已有序的子序列L[1…i-1],需要执行以下操作：
1）查找出L[i] 在L[1…i-1]中的插入位置k。
2）将L[k…i-1]中的所有元素依次向后移动一个位置。
3）将L[i] 赋值到L[k].

为了实现对 L [1… n ]的排序，可以将 L (2)~ L ( n ）依次插入前面已排好序的子序列，初始 L [1]可以视为是一个已排好序的子序列。上述操作执行 n -1次就能得到一个有序的表。插入排序在实现上通常采用就地排序（空间复杂度为 O (1))，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

---

我们通过举例来具体解释一哈步奏。假定初始序列为14, 33, 27, 10, 35, 19, 42, 44

（1）第一步：将第一个元素 14 看作是一个有序的子序列 {14}，将剩余元素逐个插入到此序列的适当位置：

（2）第二步： 将 33 插入到 {14} 中，由于 33 > 14，所以 33 应该插入到 14 的后面，新的有序序列变为 {14,33}；

（3）第三步：将 27 插入到 {14, 33} 中，由于 27 < 33 同时 27 > 14，所以 27 应该插入到 14 和 33 的中间，新的有序序列变为 {14, 27, 33}；

（4）第四步：将 10 插入到 {14, 27, 33} 中，经过依次和 33、27、14 比较，最终断定 10 应该插入到 14之前，新的有序序列变为 {10, 14, 27, 33}；

（5）第五步：将 35 插入到 {10, 14, 27, 33} 中，由于 35 > 33，所以 35 应该插入到 33之后，新的有序序列变为 {10, 14, 27, 33, 35}

（6）第六步： 将 19 插入到 {10, 14, 27, 33, 35} 中，经过依次和 35、33、27、14 比较，最终断定 19应该插入到 14 和 27 之间，新的有序序列变为 {10, 14, 19, 27, 33, 35}；

（7）第七步：将 42 插入到 {10, 14, 19, 27, 33, 35} 中，由于 42 > 35，所以 42 应插入到 35之后，新的有序序列变为 {10, 14, 19, 27, 33, 35, 42}；

（8）第八步： 将 44 插入到 {10, 14, 19, 27, 33, 35, 42} 中，由于 44 > 42，所以 44 应插入到 42 之后，新的有序序列变为 {10, 14, 19, 27, 33, 35, 42, 44}。

经过将各个待排序的元素插入到有序序列的适当位置，最终得到的就是一个包含所有元素的有序序列。

接下来我们通过动画形象的演示：

解释：

1.从第一个元素开始，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后；
6.重复步骤2~5。

---

代码如下：

void InsertSort(int* a, int n)
{for (int i = 0; i < n-1; ++i){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

---

性能分析：

直接插入排序算法的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O (1)。
时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了 n -1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态

在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为 O ( n )。

在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大,总的移动次数也达到最大.

平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为N^2／4。

因此，直接插入排序算法的时间复杂度为 O（N^2）

---

稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法。

适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

注意：大部分排序算法都仅适用于顺序存储的线性表

2.1.2希尔排序( 缩小增量排序 )

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

从前面的分析可知，直接插入排序算法的时间复杂度为O(n^2)，但若待排序序列为“正序”时，其时间复杂度可以提升为O(n)。由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于以上两点分析对直接插入排序进行改造得来的！！！

---

希尔排序法的基本思想是：
先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

---

我们通过举例来说明次算法的结题思路：

算法步骤：

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动画展示：

---

代码如下：

void ShellSort(int* a, int n)
{// gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){// gap = gap / 2; // gap = gap / 3;  // 9  8 不能保证最后一次一定是1gap = gap / 3 + 1;  // 9  8for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

---

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
   会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
4. 《数据结构(C语言版)》— 严蔚敏
   《数据结构-用面相对象方法与C++描述》— 殷人昆
   

---

稳定性：当相同关键字的记录被划分到不同的字表时，可能会改变它们之前的相对排序，因此希尔排序是一种不稳定的排序算法。

适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

2.2 选择排序

选择排序的基本思想是：

每一趟（如第 i 趟）在后面 n - i + l ( i =1,2,…, n -1）个待排序元素中选取关键字最小的元素，作为有序子序列的第 i 个元素，直到第 n - l 趟做完，待排序元素只剩下1个，就不用再选了。

2.2.1直接选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²)的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想：
假设排序表为 L [1… n ]，第 i 趟排序即从 L [ i … n ］中选择关键字最小的元素与 L ( i ）交换，每一趟排序可以确定一个元素的最终位置，这样经过 n -1趟排序就可使得整个排序表有序。

算法步骤:

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

---

动态图展示：

---

代码如下：

// 任何情况都是O(N^2)  包括有序或接近有序
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);if (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);++begin;--end;}
}

---

直接选择排序的特性总结：

空间效率：仅使用常数个辅助单元，故空间效率为 O (1)。
时间效率：从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过3( n -1）次，最好的情况是移动0次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是 n ( n -1)/2次，因此时间复杂度始终是 O ( n^2)。

---

稳定性：在第 i 趟找到最小元素后，和第 i 个元素交换，可能会导致第1个元素与其含有相同关键字元素的相对位置发生改变。因此，简单选择排序是一种不稳定的排序方法。

2.2.2堆排序

在之前的博客中，我们已经详细了解了堆排序的概念以及运用。具体大家可以阅读：堆排序的详解

2.3交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

---

冒泡排序的基本思想是：

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 A [ i -1]> A [ i ])，则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置（或将最大的元素交换到待排序列的最后一个位置），关键字最小的元素如气泡一般逐渐往上"漂浮"直至"水面"（或关键字最大的元素如石头一般下沉至水底）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素（或最大元素）放到了序列的最终位置．…．这样最多做 n -1趟冒泡就能把所有元素排好序。

---

所示为冒泡排序的过程，第一趟冒泡时：27<49，不交换：13<27，不交换：76>13,交换：97>13，交换：65>13，交换；38>13，交换；49>13，交换。通过第一趟冒泡后，最小元素已交换到第一个位置，也是它的最终位置。第二趟冒泡时对剩余子序列采用同样方法进行排序，以此类推，到第五趟结束后没有发生交换，说明表已有序，冒泡排序结束。

---

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动态图展示如下：

---

代码如下：

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; ++j){int exchange = 0;for (int i = 1; i < n-j; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}// 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理if (exchange == 0){break;}}
}

---

冒泡排序的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为 O (1)。

时间效率：当初始序列有序时，显然第一趟冒泡后 flag 依然为 false （本趟冒泡没有元素交换），从而直接跳出循环，比较次数为 n -1，移动次数为0，从而最好情况下的时间复杂度为 O ( n )：当初始序列为逆序时，需要进行 n - l 趟排序，第 i 趟排序要进行 n - i 次关键字的比较，而且每次比较后都必须移动元素3次来交换元素位置。这种情况下:

冒泡排序总的比较次数为n(n-1)/2，移动次数为n(n-1)/2次；

从而，最坏情况下的时间复杂度为 O ( n^2)，其平均时间复杂度也为 O(n^2）。

---

稳定性：冒泡排序是一种稳定的排序方法。

注意：冒泡排序中所产生的有序子序列一定是全局有序的（不同于直接插入排序），也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

2.3.2 快速排序(重点）

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

---

其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

---

1. hoare版本（即左右指针法）

思想：

一趟排序过程就是一个交替搜索和替换的过程。任取待排序元素序列中的某元素作为基准值（一般是两边的元素，我们这里选择最左边），然后我们把key放到合适的位置，使得（左边比key小，右边比key大【升序】），让最右边的元素先移动找比key小的，左边找比key大的，然后交换left和right的值，直到left和right相遇即止，相遇后交换key和left（right）任意一个位置的值。

我们通过画图来进行了解：

当第一次左右指针相遇后的位置时，基准值就被交换到了中间，接着呢继续对左右区间进行重复的操作，首先直至左区间有序后，会进行回调；此时再去递归右区间，当右区间也有序之后，那整体也就有序了

注意：

左边做key,可以让左边先走吗？

不可以左边做key必须让右边先走，右边(right)是找比key小的，找到小的停下来，即使相遇也能保证right位置的值小于key的

动图展示：

代码如下：

// Hoare
int PartSort1(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int keyi = left;while (left < right){// 右边先走，找小while (left < right && a[right] >= a[keyi]){--right;}// 左边再走，找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;return keyi;
}

大家分析上述代码，会发现有缺陷的地方？

1.待排序列呈现有序的情况，如果key后面的每个数都比key小或大的话，那left向后面找或right向前面找，就会产生越界访问的问题，为了防止这样情况的产生，我们选择在if语句的判断部分加个逻辑与&&保证left小于right，以免产生越界访问的问题。

2.快速排序除了对【有序序列】进行排序会退化之外，还有一点就是它需要进行层层递归，那既然是递归，就需要调用函数；既然要调用函数，那就需要建立栈帧，一旦建立栈帧会出现栈溢出的情况。

第一种方法就是三数取中，三数取中就是为了让我们选取的key在序列中的位置尽量靠中间. 三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码如下：

// 三数取中
// begin  mid  end
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin] > a[end]){return begin;}else{return end;}}else // a[begin] > a[mid]{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}

注意：
当大小居中的数不在序列的最左或是最右端时，我们不是就以居中数的位置作为key的位置，而是将key的值与最左端的值进行交换，这样key就还是位于最左端了，所写代码就无需改变，而只需在单趟排序代码开头加上以下两句代码即可：

int midIndex = GetMidIndex(a, begin, end);//获取大小居中的数的下标Swap(&a[begin], &a[midIndex]);//将该数与序列最左端的数据交换//以下代码保持不变...

对于三数取中法，是在开头优化；
而第二种小区间优化法，则是在结尾优化

小区间优化是为了让递归深度不要太深，因为数据量过大以后，我们递归的深度就会增加，递归建立的栈帧数量会随着递归深度的增加而增加，又因为栈空间本身就小，很容易造成栈溢出的问题。当递归区间的数据量较小时，我们不采用递归解决他们，而是换成直接插入的方法来解决较小数据量的排序。

//小区间优化
if ((end - begin + 1) < 15)
{//在数据量少的时候改用直接插入排序InsertSort(a + begin, end - begin + 1);
}

2.挖坑法

思想：

1、选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑。
2、还是定义一个left和一个right，left从左向右走，right从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）。
3、在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时left再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）

经过一次单趟排序，最终也使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后也是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

动态展示：

代码如下：

// 挖坑法
int PartSort2(int* a, int begin, int end)
{int mid = GetMidIndex(a, begin, end);Swap(&a[begin], &a[mid]);int left = begin, right = end;int key = a[left];int hole = left;while (left < right){// 右边找小，填到左边坑里面while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边找大，填到右边坑里面while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

3.前后指针法

思想：

前后指针法的单趟排序的基本步骤如下：  
1、选出一个key，一般是最左边或是最右边的。
2、起始时，prev指针指向序列开头，cur指针指向prev+1。
3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur指针越界，此时将key和prev指针指向的内容交换即可。

经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

单趟的动图演示：

---

上述递归实现的局限性可能在于：
当数据量特别大时，可能会导致栈溢出(栈涨的速度为logn，也可能是我多虑了，涨地其实挺慢的)。
为了解决上面可能出现的问题，我们可以将递归实现转换为非递归实现，我们知道任何递归的过程都可以转化为一个迭代的过程，而转化的关键在于如何使用迭代来模拟整个递归的处理。

观察上面的递归处理过程，我们可以看到：每一次排序函数的调用都会再次重新调用两次新的排序函数，然后系统会按照调用顺序一步一步地进行处理和返回，而调用排序函数的关键在于必须将排序的范围告诉函数。

这个过程很像一个排队处理的过程，于是我们可以使用队列进行递归的模拟，而队列中的信息存储要处理的范围即可。当队列不为空时，表示还有范围未处理；队列为空时，表示所有的范围都已经处理完毕，也即确定了所有元素的位置，完成了排序工作。

我们利用栈的相关思想来进行实现：

void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (StackEmpty(&st) != 0)
{right = StackTop(&st);StackPop(&st);left = StackTop(&st);StackPop(&st);if(right - left <= 1)continue;int div = PartSort1(a, left, right);// 以基准值为分割点，形成左右两部分：[left, div) 和 [div+1, right)StackPush(&st, div+1);StackPush(&st, right);StackPush(&st, left);StackPush(&st, div);
}StackDestroy(&s);
}

---

快速排序算法的性能分析如下：

空间效率：由于快速排序是递归的，需要借助一个递归工作找来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致。最好情况下为 O ( logzn )；最坏情况下，因为要进行 n - l 次递归调用，所以栈的深度为 O ( n )：平均情况下，栈的深度为 O ( logn)。

时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含 n -1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 O ( n^2)。

有很多方法可以提高算法的效率：

一种方法是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素：

或者随机地从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；有随机吧从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即 Partition (）可能做到最平衡的划分，得到的两个子问题的大小都不可能大于 n /2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 O (nlog2n)。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。

---

稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。例如，表 L =(3,2,2)，经过一趟排序后 L =(2,2,3)，最终排序序列也是 L =(2,2,3)，显然，2与2的相对次序已发生了变化。

注意：在快速排序算法中，并不产生有序子序列，但每趟排序后会将枢轴（基准）元素放到其最终的位置上。

2.4 归并排序

归并排序与上述基于交换、选择等排序的思想不一样，"归并"的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有 n 个记录，则可将其视为 n 个有序的子表，每个子表的长度为1，然后两两归并，得到「 n /27个长度为2或」的有序表；继续两两归并．…．如此重复，直到合并成一个长度为 n 的有序表为止，这种排序方法称为2路归并排序。

两路归并核心步奏：

---

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；

以下为一个两路归并的例子：

---

算法步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

递归版本：

// 时间复杂度：O(N*logN)
// 空间复杂度：O(N)
// [begin, end]
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid] [mid+1, end] 递归让子区间有序_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);// 归并[begin, mid] [mid+1, end]//...int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

非递归版本：

归并排序的非递归算法并不需要借助栈来完成，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：
 
当然，以上例子是一个待排序列长度比较特殊的例子，我们若是想写出一个广泛适用的程序，必定需要考虑到某些极端情况：
情况一：
 当最后一个小组进行合并时，第二个小区间存在，但是该区间元素个数不够gap个，这时我们需要在合并序列时，对第二个小区间的边界进行控制。
 
情况二：
 当最后一个小组进行合并时，第二个小区间不存在，此时便不需要对该小组进行合并。
 
情况三：
 当最后一个小组进行合并时，第二个小区间不存在，并且第一个小区间的元素个数不够gap个，此时也不需要对该小组进行合并。
 
只要把控好这三种特殊情况，写出归并排序的非递归算法便轻而易举了。

代码如下：

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);if (tmp == NULL){perror("malloc fail");exit(-1);}// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并int rangeN = 1;while (rangeN < n){for (int i = 0; i < n; i += 2 * rangeN){// [begin1,end1][begin2,end2] 归并int begin1 = i, end1 = i + rangeN - 1;int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);int j = i;// end1 begin2 end2 越界// 修正区间  ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝if (end1 >= n){end1 = n - 1;// 不存在区间begin2 = n;end2 = n - 1;}else if (begin2 >= n){// 不存在区间begin2 = n;end2 = n - 1;}else if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}}// 也可以整体归并完了再拷贝memcpy(a, tmp, sizeof(int)*(n));rangeN *= 2;}free(tmp);tmp = NULL;
}

---

动态图展示：

---

2路归并排序算法的性能分析如下：

空间效率： Merge (）操作中，辅助空间刚好为 n 个单元，所以算法的空间复杂度为 O ( n )。
时间效率：每趟归并的时间复杂度为 O ( n )，共需进行「 logznl 趟归并，所以算法的时间复杂度为 O ( nlogn ).

---

稳定性：由于 Merge (）操作不会改变相同关键字记录的相对次序，所以2路归并排序算法是一种稳定的排序方法。

2.5 计数排序

思想：
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 顾名思义，该算法不是通过比较数据的大小来进行排序的，而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

---

计数排序的特征

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

注：计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费，并且计数排序只适用于整型排序，不适用与浮点型排序。

---

算法的步骤如下：
（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

动态展示：

代码如下：

//计数排序
void CountSort(int* a, int n)
{int min = a[0];//记录数组中的最小值int max = a[0];//记录数组中的最大值for (int i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0if (count == NULL){printf("malloc fail\n");exit(-1);}//统计相同元素出现次数（相对映射）for (int i = 0; i < n; i++){count[a[i] - min]++;}int i = 0;//根据统计结果将序列回收到原来的序列中for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}free(count);//释放空间
}

---

计数排序算法的性能分析如下：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

3.各种内部排序算法比较及运用

3.1内部排序算法的比较

前面讨论的排序算法很多，对各算法的比较也是爱考的内容。一般基于三个因素进行对比：时空复杂度、算法的稳定性、算法的过程特征。

从时间复杂度看：

简单选择排序、直接插入排序和冒泡排序平均情况下的时间复杂度都为 O ( n^2)，且实现过程也较简单.

直接插入排序和冒泡排序最好情况下的时间复杂度可以达到 O ( n )

而简单选择排序则与序列的初始状态无关。
希尔排序作为插入排序的拓展，对较大规模的排序都可以达到很高的效率，但目前未得出其精确的渐近时间。
堆排序利用了一种称为堆的数据结构，可在线性时间内完成建堆，且在 O ( nlogn ）内完成排序过程。

快速排序基于分治的思想，虽然最坏情况下快速排序时间会达到 O ( n )，但快速排序平均性能可以达到 O ( nlogn )，在实际应用中常常优于其他排序算法。

归并排序同样基于分治的思想，但由于其分割子序列与初始序列的排列无关，因此它的最好、最坏和平均时间复杂度均为 O ( nlogn )。

---

从空间复杂度看：

简单选择排序、插入排序、冒泡排序、希尔排序和堆排序都仅需要借助常数个辅助空间。

快速排序在空间上只使用一个小的辅助栈，用于实现递归，平均情况下大小为 O ( logn )，当然在最坏情况下可能会增长到 O ( n )。

2路归并排序在合并操作中需要借助较多的辅助空间用于元素复制，大小为 O ( n )，虽然有方法能克服这个缺点，但其代价是算法会很复杂而且时间复杂度会增加。

---

从稳定性看：插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而简单选择排序、快速排序、希尔排序和堆排序都是不稳定的排序方法。平均时间复杂度为 O ( nlogn ）的稳定排序算法只有归并排序，对于不稳定的排序方法，只要举出一个不稳定的实例即可。对于排序方法的稳定性，小伙伴们应能从算法本身的原理上去理解，而不应拘泥于死记硬背。

排序算法复杂度及稳定性分析：

3.2内部排序算法的运用

通常情况，对排序算法的比较和应用应考虑以下情况。

1）选取排序方法需要考虑的因素

①待排序的元素数目 n
②元素本身信息量的大小。
③关键字的结构及其分布情况。
④稳定性的要求。
⑤语言工具的条件，存储结构及辅助空间的大小等。

2）排序算法小结

①若 n 较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。

②若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

③若 n 较大，则应采用时间复杂度为 O ( nlogn ）的排序方法：【快速排序、堆排序或归并排序】。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为 O ( nlogn )，则可选用归并排序。

④在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的 n 个关键字随机分布时，任何借助于"比较"的排序算法，至少需要 O ( nlogn / n ）的时间。

⑥若 n 很大，记录的关键字位数较少所可以分解时，采用基数排序较好。

⑥当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。

4 选择题讲解

1.有字符序列 FBJGEAIDCH，现在打算对它按字母的字典顺序用希尔排序进行排序，那么在第一趟后（步长为5）的序列为（ ）
A.CAEBFDIGJH
B.AIDCHFBJGE
C.ABDCEFIJGH
D.BFJGEAIDCH

解答：

希尔排序按照步长把元素进行小组划分，每个小组元素进行插入排序。

所以如果步长为5，则整个数组被会划分成5组数据：

FA BI JD GC EH

所以一趟排序之后的结果为：

ABDCEFIJGH
所以选C

2.下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）

① 选择排序
② 归并排序
③ 快速排序
④ 堆排序

A.①④
B.①②④
C.①③④
D.①②③④

解析：

选择排序每次选一个最值，放在最终的位置

快速排序每次基准值的位置也可以确定

堆排序每次堆顶元素的位置也可以确定

所以这三种方法都可以每次至少确定一个元素的位置

而归并排序每次都需要对n个元素重新确定位置，所以不能保证每次都能确定一个元素位置，有可能每次排序所有元素的位置都为发生变化。

所以选C

3.以下哪种排序算法对[1, 3, 2, 4, 5, 6, 7, 8, 9]进行排序最快（ ）
A.直接插入排序
B.快速排序
C.归并排序
D.堆排序

解析：

次序列接近有序，所以如果是插入排序，时间复杂度逼近O(n)

快排： 逼近O(n^2)

归并和堆排仍然是nlogn

所以选A

4.对数字序列28 16 32 12 60 2 5 72进行升序的快速排序（以第一个关键码为基准的方法），一次划分后的结果为（ ）
A.2 5 12 16 28 60 32 72
B.2 16 5 12 28 60 32 72
C.2 16 12 5 28 60 32 72
D.5 16 2 12 28 32 60 72

解析：

快速排序以基准值为中心，对元素进行划分，这里以28为基准值，则小于28的和大于28的进行交换，完成一次划分

首先：32和5交换： 28 16 5 12 60 2 32 72

然后60和2交换： 28 16 5 12 2 60 32 72

最后28和最后一个小于28的元素进行交换：

    2 16 5 12 28 60 32 72

5.使用选择排序对长度为100的数组进行排序，则比较的次数为（ ）
A.5050
B.4950
C.4851
D.2475

解析：

选择排序，每次都要在未排序的所有元素中找到最值，

如果有n个元素，则

第一次比较次数： n - 1

第二次比较次数： n - 2

…

第n - 1次比较次数： 1

所有如果n = 100

则比较次数的总和：99 + 98 + … + 1

共4950次。

好了，小伙伴们，以上就是排序的全部知识内容了。如果对大家有帮助希望多多支持哟！！！