第八章 排序（上）【基本概念和交换插入选择排序】

排序（Sort），就是按关键字重新排列表中的元素，使表中的元素满⾜按关键字有序的过程

注：关键字是数据元素的某个或某几个数据项，而不是整个元素 

• 按在排序过程中是否涉及数据的内、外存交换来分类，排序大致分为两类：和。
• 按照是否通过比较来决定元素间的相对次序，排序可以分为和。

1. 时间复杂度 空间复杂度

查找效率最低的数据结构：堆

堆排序：建堆O(n),排序(nlogn),总的O(nlogn)

基数排序：分配O(n),收集O(r)

计数排序：计数O(n),收集O(k),k为元素取值范围

3.外部排序：还要关注如何使读/ 写磁盘次数更少，内存比机械硬盘读写速度快600倍

1.元素的移动次数与关键字的初始排列次序无关的是：基数排序，二路归并排序

2.比较次数 与序列初态 无关 的算法是：折半插入排序、简单选择排序、基数排序

3.比较次数 与序列初态 有关 的算法是：快速排序、二路归并排序、直接插入排序、冒泡排序、堆排序、希尔排序

4.排序趟数 与序列初态 无关 的算法是：直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序

5.排序趟数 与序列初态 有关 的算法是：冒泡排序、快速排序

6.时间复杂度与初始状态无关的是选择排序堆排序，归并排序

7.如果想得到前k大的元素：堆排序

8.不能在一趟排序结束后至少确定一个一个元素最终位置的是：插入，二路归并，希尔

2.1.1 概念

冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

2.1.2 基本思想

从前往后（或从后往前）两两比较相邻元素的值，若为逆序（即A[j]>A[j+1]）,则交换它们，直到序列比较完。我们称这样的过程为一趟冒泡排序。结果是将最大的元素交换到待排序列的最后一个位置（或将最小的元素交换到待排序列的第一个位置），关键字最大（小）的元素如气泡一样逐渐向上“漂浮”。最终一个一个排好了位置。总共需进⾏ n-1 趟冒泡

2.1.3 代码实现

在该示例中，我们使用了vector作为存储数组的容器，并通过冒泡排序算法对其进行排序。算法实现过程中，我们通过两个嵌套的循环遍历整个数组，每次比较相邻的两个元素，如果它们的顺序不对，就交换它们的位置。经过多轮遍历，数组中的元素会逐渐按照从小到大的顺序排列。

该示例代码可以对任意大小的数组进行冒泡排序，时间复杂度为O(n^2)。虽然冒泡排序的时间复杂度较高，但是其代码实现简单，容易理解，适合对小规模数据进行排序。顺序表链表都可以用。

2.1.4 算法优化

冒泡排序算法的时间复杂度为O(n^2)，因此对于大规模的数据集合，它的效率较低。可以通过一些优化手段提高冒泡排序的效率，以下是一些可能的优化方法：

1. 增加一个标志位，表示本轮排序是否进行了交换。如果本轮排序中没有发生任何交换，说明数组已经有序，可以直接退出排序。

2. 优化循环范围，每一轮排序只需要比较到上一轮最后发生交换的位置即可，因为在该位置之后的元素已经有序。

3. 对于已经有序的子数组，可以记录最后一次交换的位置，下一轮排序时只需要比较到该位置即可。

4. 如果待排序数组的大小比较小，可以使用插入排序或者选择排序等复杂度较低的算法进行排序。

下面是对冒泡排序进行第一种优化的示例代码： 

 在该示例中，我们增加了一个标志位flag，用于记录本轮排序是否进行了交换。如果本轮排序中没有发生任何交换，说明数组已经有序，可以直接退出排序。这样就能够减少排序的轮数，提高效率。

2.1.5 冒泡排序性能分析

时间复杂度

最好的情况：正序:O(n)

⽐较次数=n-1；交换次数=0 最好时间复杂度=O(n)

最坏情况（逆序）: O(n^2)

每次交换都需要 移动元素3次,总的移动次数

平均时间复杂度=O(n^2)

空间复杂度：O(1)

大小相同的元素没有交换位置，所以冒泡排序是稳定的

2.2.1 概念

快速排序是一种二叉树结构的交换排序方法。相当于是冒泡排序的一种升级，都是属于交换排序类，基于分治思想通过不断比较和移动交换来实现排序。也是一般笔试面试最高频的排序算法，不仅要掌握快排的写法，背后思想也要掌握。

特点

• 快速排序是所有内部排序算法中平均性能最优的排序算法。
• 对所有尚未确定最终位置的所有元素进⾏⼀遍处理
• 快速排序可以看作数组中n个元素组织成二叉树，每趟处理的枢轴是二叉树的根节点，递归调用的层数是二叉树的层数。

一趟的概念：对所有尚未确定最终位置的所有元素进⾏⼀遍处理

例如第二趟，左右两部分都处理完一次才叫一趟

2.2.2 基本思想

• 在待排序表选出一个基准数，基准值一般取序列最左边的元素pivot 作为枢轴

• 通过一趟排序将待排序表分为独立的两部分 ，比基准值小的放在基准值左边，比基准值大的放在基准值右边，这就是所谓的分区，然后分别递归地对各个分区重复上述过程，直⾄ 每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

注：对所有尚未确定最终位置的所有元素进⾏⼀遍处理称为“⼀趟”排序，因此⼀次“划分”≠⼀趟排序。 ⼀次划分可以确定⼀个元素的最终位置，⽽⼀趟排序也许可以确定多个元素的最终位置。即第二趟是指对左右两边都划分一次

2.2.3 代码实现

方法一：单边扫描快速排序

选择一个数作为基准数pivot，同时设定一个标记 mark 代表左边序列（小于基准数pivot的序列）最右侧的下标位置，接下来遍历数组，如果元素大于等于基准值，无操作，继续遍历，如果元素小于基准值，则把 mark + 1 （此时指向数据肯定大于等于基准数pivot），再将 mark  所在位置的元素和遍历到的元素交换位置（把大于等于基准数pivot的数换到了后面，把小于基准数的数放到了左边序列最右边），此时mark 这个位置存储的是比基准值小的数据，再次成为左边序列最右侧的下标位置，当遍历结束后，将基准值与 mark 所在元素交换位置，完成一轮快排。递归处理左右两个分区，完成排序。

方法二：双边扫描快速排序

选择一个数作为基准值（一般选则最左边的元素，初始化left指针指向最左边元素下标（基准值下标），right指针指向最后一个元素下标，然后从数组右左两边依次进行扫描，先从右往左找到一个小于于基准值的元素，将它填入到left指针位置，然后转到从左往右扫描，找到一个大于基准值的元素，将他填入到right指针位置。循环往复，直到左右指针相遇。

方法三：用栈实现非递归

在非递归实现中，我们使用了栈来保存每个待排序数组的左右端点。在栈不为空的情况下，弹出当前待排序数组的左右端点，进行分区，并将分区后的左右子数组的端点入栈。当栈为空时，排序结束。

在具体实现中，我们仍然选择第一个元素作为pivot，并使用双指针的方式进行分区。需要注意的是，每次分区后，需要判断左右子数组的长度是否大于1，若大于1，则将其端点入栈，以便进行下一次分区。

与递归实现相比，非递归实现的优势在于可以避免递归过程中的函数调用开销，从而提高效率。

2.1.4 优化

1. 随机选择基准元素

快速排序最坏情况下的时间复杂度为 ，这种情况通常发生在每次选择的基准元素都是当前子数组的最大或最小值时。为了避免这种情况，我们可以随机选择一个元素作为基准元素，这样每个元素都有相同的概率成为基准元素，从而避免了最坏情况的发生。

主元的选取有很多种方式，这里我们采用随机的方式，对当前划分区间 [l,r] 里的数等概率随机一个作为我们的主元，再将主元放到区间末尾，进行划分。

时间复杂度：基于随机选取主元的快速排序时间复杂度为期望)O(nlogn)，其中 n 为数组的长度。详细证明过程可以见《算法导论》第七章

空间复杂度：O(h)，其中 h 为快速排序递归调用的层数。我们需要额外的 O(h) 的递归调用的栈空间，由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 O(n) 的空间，最优情况下每次都平衡，此时整个递归树高度为 logn，空间复杂度为 O(logn)。

2.三数取中法选择基准元素

在确定基准元素时，我们可以选择当前子数组的第一个元素、最后一个元素、中间元素中的中位数作为基准元素。这种方式称为三数取中法，可以使得基准元素更加均衡，从而提高排序效率。

3.小数组使用插入排序

对于长度较小的子数组，快速排序的效率并不一定比插入排序更高。因此，我们可以设置一个阈值 ，当子数组长度小于 时，使用插入排序而不是快速排序。

4.双轴快排

双轴快排是一种基于快速排序的改进算法，它使用两个基准元素而不是一个基准元素进行分区。具体来说，我们先选择两个基准元素p和q，其中p < q，然后将数组分成三部分：小于p的部分、大于q的部分和介于p和q之间的部分。接下来，我们对小于p和大于q的两部分递归进行双轴快排，对介于p和 q之间的部分进行普通的快速排序。双轴快排相比于普通的快速排序，在某些情况下可以提高排序效率。

上述代码中，使用了三数取中法选择基准元素、插入排序阈值、递归排序左右子数组等优化方式，从而提高了快速排序的效率。

综上所述，快速排序是一种高效的排序算法，并且具有很多优化的空间。通过选择合适的基准元素、使用插入排序等方法，我们可以进一步提高快速排序的效率。

2.1.5  快速排序算法效率分析

1.时间空间复杂度

时间复杂度=O(n*递归层数)， 空间复杂度=O(递归层数)

2. 最坏的情况 

• 若每⼀次选中的“枢轴”将待排序序列 划分为很不均匀的两个部分，则会导 致递归深度增加，算法效率变低。
• 若初始序列有序或逆序，则快速排序 的性能最差（因为每次选择的都是最 靠边的元素）

3.比较好的情况：

若每⼀次选中的“枢轴”将待排序序列 划分为均匀的两个部分，则递归深度 最⼩，算法效率最⾼ 

快速排序算法优化思路：尽量选择可以把 数据中分的枢轴元素。 eg：①选头、中、尾三个位置的元素，取 中间值作为枢轴元素；②随机选⼀个元素 作为枢轴元素

4.最好的情况：

每次选的枢轴元素都 能将序列划分成均匀 的两部分

5.稳定性——不稳定！

快排的比较和交换是跳跃进行的，所以快排是一种不稳定的排序算法。

插入排序(InsertionSort)，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。

将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素进行遍历，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

插入排序的核心思想是将一个元素插入到已经排好序的部分中，使得插入后仍然是有序的。

3.3.1 简单插入排序（直接插入排序）

该算法从第二个元素开始，将当前元素插入到已经排好序的部分中，使得插入后仍然是有序的。具体实现是：外层从第二个元素开始遍历到最后一个元素，内层将当前遍历到的元素保存到 key 中，定义指针j从当前元素的前一个元素开始向前遍历已经排好序的部分，将大于 key 的元素向右移动一个位置，直到找到一个小于等于 key 的元素，将 key 插入到该位置后面。由于插入排序的时间复杂度为 ，因此当序列规模较小时，插入排序可以比较高效。

代码实现（带哨兵）：

对于插入排序算法的优化，主要有以下几个方面：

3.4.1 使用二分查找优化内部循环

在内部循环中，对于已经排好序的部分可以使用二分查找定位插入位置，而不是逐个比较。这样可以将内部循环的时间复杂度从O(n)优化到 O(logn)，从而提高整个算法的性能。以下是使用二分查找优化内部循环的代码实现：

• 注意：一直到low>high 时才停止折半查找。当mid所指元秦等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终left指向第一个大于key的元素（right指向不大于key的最大值），应将当前元素插入到low 所指位置 (即 high+1),将 [low, i-1] 内的元素全部右移,并将key 复制到 low 所指位置
• 与直接插入排序相比，比较关键字的次数减少了，但是移动元素的次数没有变。时间复杂度仍为 O(n²)。
• 拓展，若该成nums[mid]>=key,则最终left指向第一个大于等于key的，right指向小于key的元素中的最大值。

 3.4.2 缩小常数因子

插入排序算法的常数因子比较大，可以通过减少赋值操作来缩小常数因子。在实现中，可以将需要插入的元素保存到临时变量中，然后在找到插入位置后再进行一次赋值操作。以下是缩小常数因子的代码实现：

时间复杂度：主要来⾃对⽐关键字、移动元素 若有 n 个元素，则需要 n-1 趟处理.平均时间复杂度：O(n^2)

3.5.1 最好情况：原本就有序

共n-1趟处理，每⼀趟只需要对⽐关键字1次， 不⽤移动元素

最好情况时间复杂度是O(n)。

3.5.2 最坏情况：原本为逆序

第 i 趟：对⽐关键字 i+1次，移动元素 i+2 次

最坏时间复杂度——O(n^2)

3.5.3 空间复杂度：O(1)

3.5.4 算法稳定性：稳定

插入排序只会移动比插入元素大的元素，所以相同元素相对位置不变，是稳定的。

适用于顺序存储和链式存储的线性表。

插入排序：最好情况——原本就有序，⽐较好的情况——基本有序

希尔排序：先追求表中元素部分 有序，再逐渐逼近全局有序

希尔排序（Shell Sort）是一种基于插入排序的快速排序算法，由Donald Shell在1959年提出。希尔排序是将整个序列分割成若干个子序列，对每个子序列进行插入排序，使得子序列基本有序，然后再对全体元素进行一次插入排序。

4.2.1 算法思想

将待排序的元素分成若干个小组，对每个小组进行插入排序，随着排序过程的进行，每个小组的元素个数逐渐增多，但仍然保持有序。最后将所有元素分成一个组，进行插入排序。

4.2.2 希尔排序的具体步骤：

1. 选择一个逐渐缩小的增量序列d1，d2，...di...dj...，dk，其中di > dj，dk = 1；

2. 对于每个增量di，将序列分成di个形如 L[i, i + d, i + 2d,…, i + kd]的子序列，分别对每个子序列进行插入排序；

3. 增量逐渐缩小，重复步骤2，直到增量为1。

在实际应用中，希尔排序常常使用一些常见的增量序列，如希尔增量（n/2，n/4，...，1）、Hibbard增量（1，3，7，...，2^k-1）、Sedgewick增量等，以提高排序的效率。

希尔本⼈建议：每次 将增量缩⼩⼀半

4.2.4 实例：

1.初始序列

2. 第⼀趟：d1=n/2=4

3.对子表进行插入排序

3. 第一趟结束，第二趟初始

 4. 第⼆趟：d2=d1/2=2

5.对子表进行插入排序

7.第三趟：d3=d2/2=1

8. 整个表已呈现出“基本有序”，对整体再进⾏⼀次“直接插⼊排序”

4.3.1 从0开始存，申请临时变量保存

在这个代码中，我们使用了一个变量d来表示增量，初始化为n/2。然后每次循环时，我们将d缩小一半，直到它变成1为止。在每次循环中，我们将原序列分成d个子序列，对每个子序列进行插入排序。具体地，对于第i个子序列，它的第一个元素是第i个元素，第二个元素是第i+d个元素，第三个元素是第i+2*d个元素，以此类推。对于每个子序列，我们使用插入排序的思想，将它们变成基本有序的序列。最后，当d变成1时，我们对整个序列进行一次插入排序，使得整个序列变得有序。

注：i = d; i < nums.size(); ++i并非一个子序列处理完了才处理下一个子序列，而是交替处理各个子序列

若一个个子序列单独处理的话            

4.3.2 从1开始存数据，0空着，用来暂存

希尔排序的优化方法比较多，下面介绍其中两种。

4.4.1 增量序列选择

希尔排序的性能与增量序列的选择有很大关系。常见的增量序列有希尔增量、Hibbard增量、Sedgewick增量等。一般来说，增量序列的最后一个元素应该是1，而其他元素的选择会影响算法的性能。在实际应用中，可以通过试验不同的增量序列，选择最优的增量序列。

4.4.2 插入排序的优化

在希尔排序的每个子序列中，我们使用插入排序的思想，将子序列变成基本有序的序列。但是，插入排序在对近乎有序的序列进行排序时，效率非常高。因此，我们可以使用一种优化方式，即在插入排序中，将查找插入位置的过程改为二分查找。这样，当子序列基本有序时，插入排序的效率将大大提高。

4.5.1 时间复杂度：

• 希尔排序的时间复杂度跟增量序列的选择有关，范围为 O(n^(1.3-2)) 在此之前的排序算法时间复杂度基本都是 O(n²)，希尔排序是突破这个时间复杂度的第一批算法之一。

4.5.2 空间复杂度：O(1)

4.5.3 算法稳定性：不稳定。

希尔排序是直接插入排序的变形，但是和直接插入排序不同，它进行了分组，所以不同组的相同元素的相对位置可能会发生改变，所以它是不稳定的。

适⽤性：仅适⽤于顺序表，不适⽤于链表

选择排序：每⼀趟在待排序元素中选取关键字最⼩（或最⼤）的元素加⼊有序⼦序列

 简单选择排序：是一种简单直观的排序算法，每次在剩余区间遍历查找最小值（最大值）放到最前面（后面）。

每次从待排序序列中选择最小的元素，与序列的第一个元素交换位置。这样，序列的第一个位置就是最小的元素。然后在剩下的元素中继续执行上述操作，直到整个序列排序完成。

n个元素的简单选择排 序需要 n-1 趟处理

对链表进行简单选择排序：

时间复杂度为 O(n^2)，稳定性为不稳定。

选择排序的时间复杂度为 ，无法避免的比较次数较多。因此，常常需要对选择排序进行优化以提高排序的效率。

5.4.1 双向选择排序

该算法将待排序序列分成两部分，分别维护当前未排序序列中的最小值和最大值。具体实现是：每次在未排序序列的左边和右边分别找到最小值和最大值，将它们分别和未排序序列的左端点和右端点进行交换。由于每次交换会减少一个元素的比较次数，因此双向选择排序的平均时间复杂度为O(n^2)，但比选择排序的时间复杂度要略低一些。

5.5.1 时间复杂度= 

 ⽆论有序、逆序、还是乱序，⼀定需要 n-1 趟处理.

5.5.2 空间复杂度：O(1)

5.5.3 稳定性：不稳定

在未排序序列中找到最小值之后，和排序序列的末尾元素交换。

适⽤性：既可以⽤于顺序表，也可⽤于链表

6.1.1堆的定义

• 必须是完全二叉树

• 任一节点的值必须是其子树的最大值或最小值

最大值时，称为“最大堆”，也称大根堆或者大顶堆；根≥左、右，堆顶元素关 键字最⼤

最小值时，称为“最小堆”，也称小根堆或者小顶堆。根左、右，堆顶元素关 键字最小

6.1.2 堆的存储

因为堆是完全二叉树，所以堆可以用数组存储。按层来将元素存储到数组对应位置，从下标1开始存储，可以省略一些计算。

 完全二叉树顺序存储的重要性质

6.1.3 堆排序（Heapsort）

是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序是简单选择排序的一种升级版。每⼀趟将堆顶元素加⼊有序⼦序列 （与待排序序列中的最后⼀个元素交换）并将待排序元素序列再次调整为⼤根堆 （⼩元素不断“下坠”）

基于“⼤根堆”的堆排序得到“递增序列”

将待排序的元素构造成一个堆，然后依次将堆顶元素与堆底元素交换，再对堆顶元素进行下沉操作，使得交换后的堆仍然保持最大堆或最小堆的性质，重复上述过程直到排序完成。

在堆排序中，首先要构建一个堆，可以使用从下往上的建堆方法，或者使用堆插入的方法。建堆完成后，将堆顶元素与堆底元素交换，然后对堆顶元素进行下沉操作，使得堆顶元素重新满足最大堆或最小堆的性质。交换后的堆除堆顶元素外，仍然满足最大堆或最小堆的性质，继续进行相同的操作，直到排序完成。

6.3.1 建立大根堆

思路：把所有⾮终端结点都检查⼀遍，是否满 ⾜⼤根堆的要求，如果不满⾜，则进⾏调整，（在顺序存储的完全⼆叉树中，⾮终端结点编号 i≤⌊n/2⌋），检查当前结点是否满⾜ 根≥左、右 若不满⾜，将当前结点与更⼤的⼀个孩⼦互换。

更⼩的元素“下坠”，可能导致下⼀ 层的⼦树不符合⼤根堆的要求，若元素互换破坏了下⼀级的堆，则采⽤相同的⽅ 法继续往下调整（⼩元素不断“下坠”）

6.3.2  堆排序 

每⼀趟将堆顶元素加⼊有序⼦序列 （与待排序序列中的最后⼀个元素交换）并将待排序元素序列再次调整为⼤根堆 （⼩元素不断“下坠”）,n-1趟 处理之后只剩下最后⼀个待排 序元素，不⽤再调整。

6.3.4 基于“⼩根堆”建堆、排序

基于“⼩根堆”的堆排序得到“递减序列”

堆排序的优化主要是通过优化建堆的过程和减少交换操作来提高排序的效率。

1、优化建堆过程

• 1. 从最后一个非叶子节点开始向下进行调整，减少不必要的交换次数。

  2. 建堆过程中，可以将每个非叶子节点看作是一个小堆，然后对这些小堆进行合并。

2、减少交换操作

• 1. 在删除堆顶元素时，为了保证堆的性质，需要将堆尾元素移动到堆顶，并对堆进行调整。这里可以将堆尾元素赋值给堆顶元素，然后删除堆尾元素，这样就可以减少一次交换操作。

  2. 对于需要交换的元素，可以将它们保存在一个临时变量中，然后再一次性进行赋值，减少交换次数。

6.5.1 时间复杂度O(nlog2n)

下⽅有两个孩⼦，则“下坠” ⼀层，需对⽐关键字 2 次，下⽅只有⼀个孩⼦，则“下坠” ⼀层，只需对⽐关键字 1 次，

结论：⼀个结点，每“下坠”⼀层，最多只需对⽐关键字2次

若树⾼为h，某结点在第 i 层，则将这个结点向下调整最多只需要“下坠” h-i 层，关键字对⽐次数不超过 2(h-i)，n个结点的完全⼆叉树树⾼ h=⌊log2n⌋ + 1

堆排序 ：总共需要n-1趟，每⼀趟交换后 都需要将根节点“下坠”调整

根节点最多“下坠” h-1 层，每下坠⼀层 ⽽每“下坠”⼀层，最多只需对⽐关键字2次，因此每⼀趟排序复杂度不超过 O(h) = O(log2n)

共n-1 趟，总的时间复杂度 = O(nlog2n)

堆排序的时间复杂度 = O(n) + O(nlog2n) = O(nlog2n)

6.5.2 堆排序的空间复杂度 = O(1)

6.5.3 稳定性——不稳定

若左右孩 ⼦⼀样⼤，则优 先和左孩⼦交换

结论：堆排序是不稳定的

6.6.1 在堆中插⼊新元素

对于⼩根堆，新元素放到表尾，与⽗节点对⽐， 若新元素⽐⽗节点更⼩，则将⼆者互换。新元素 就这样⼀路“上升”，直到⽆法继续上升为⽌。

6.6.2  在堆中删除元素

被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌。