数据结构第七章排序，期末不挂科指南

概述

本小节最重要的一个点为 排序算法的稳定性概念：相同键值的两个记录在排序前后相对位置的变化情况。

n 个记录的序列为{R~1~，R~2~，...，R~n~} ，其对应的键值序列为{k~1~，k~2~，...，k~n~}，假设 k~i~ = k~j~，若在排序前的序列中 R~i~在 R~j~之前，即 i<j，经过排序后，R~i~仍在 R~j~之前，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。

稳定性是排序方法本身的特性，与数据无关。也就是说，一种排序方法如果是稳定的，则对所有的数据序列都是稳定的。

内部排序的方法很多，自考教材主要讨论了四种，分别是插入排序、交换排序、选择排序和归并排序

插入排序

常见的插入排序方法有 直接插入排序、折半插入排序、表插入排序、希尔排序

直接插入排序

通过案例说明，查看直接排序方法

应用直接插入排序方法，对序列{45,38,66,90,88,10,25,45}所示的一组键值进行排序，过程可参照下图所示

参照动图（动图来源网络）

直接插入排序说明

直接插入排序算法简单，非常容易理解，容易实现，实现的复杂度为 O(n^2^)，若待排序的记录数量非常大的时候，一般不选用直接排序。从空间上来看，它只需要一个记录的辅助空间，空间复杂度为 O(1)

自考真题

用插入排序算法对数据序列（47，33，61，82，72，11，25，57）进行排序，写出整个插入排序的每一趟过程。

要点，就是选择第一个元素之后，在从后面选择小的，往前插

答：第一趟：[47]，33，61，82，72，11，25，57 第二趟：[33，47]，61，82，72，11，25，57 第三趟：[33，47，61]，82，72，11，25，57 第四趟：[33，47，61，82]，72，11，25，57 第五趟：[33，47，61，72，82]，11，25，57 第六趟：[11，33，47，61，72，82]，25，57 第七趟：[11，25，33，47，61，72，82]，57 第八趟：[11，25，33，47，57，61，72，82]

==直接插入排序，时间复杂度为 O(n^2^)，算法稳定==

交换排序

交换排序的基本思想：比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，交换这两个记录

冒泡排序

冒泡排序是一种交换排序的方法，其过程是首先将第一个记录的键值和第二个记录的键值进行比较，出现逆序，则将这两个记录交换，然后继续比较低二个和第三个记录的键值。依次类推，直到完成第 n-1 个记录和第 n 个记录的键值比较交换为止。这个过程称为 起泡。

动图展示（图片来源网络）

自考真题

用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。

要点，每两个挨着比，每趟最大的沉底

答：第一趟：38，55，65，76，97，27，49，138 第二趟：38，55，65，76，27，49，97，138 第三趟：38，55，65，27，49，76，97，138 第四趟：38，55，27，49，65，76，97，138 第五趟：38，27，49，55，65，76，97，138 第六趟：27，38，49，55，65，76，97，138

==直接插入排序，时间复杂度为 O(n^2^)，算法稳定==

快速排序

快速排序是交换排序的一种，实质上是对冒泡排序的一种改进。它的基本思想是：在 n 个记录中取某一个记录的键值为标准，通常取第一个记录键值为基准，通过一趟排序将待排的记录分为小于这个键值和大于或等于这个键值的两个独立部分，这时一部分的记录键值均比另一部分记录的键值小，然后，对这两部分记录继续分别进行快速排序，以达到整个序列有序。

动图展示（图片来源网络）

自考真题

要点，用第一个数字，依次和后面的每个比较，然后拆分成 2 部分，一部分小于等于，一部分大于，依次类推即可

答：第一次交换（注意不是第一趟）：以 72 为基数，走起 60,26,57,88,42,80,73,48,72 交换了 72 和 60 第二次交换： 60,26,57,72 ,42,80,73,48,88 交换了 72 和 88 第三次交换： 60,26,57, 48,42,80,73,72,88 第四次交换： 60,26,57, 48,42,72,73,80,88 （得到第一趟结果）

所以 57 对应的位置是 2,72 对应的位置是 5,88 对应的位置是 8

==快速排序，时间复杂度为 O(nlog~2~n)，算法不稳定==

选择排序

选择排序的基本思想：每一次在 n-i+1(i=1,2,3,...,n-1)个记录中选取键值最小的记录作为有序序列的第 i 个记录。

直接选择排序

在第 i 次的选择操作中，通过 n-i 次键值间比较，从 n-i+1 个记录中选出键值最小的记录，并和第 i 个记录交换

动图展示（图片来源网络）

自考真题

应用直接选择排序算法，对初始关键字序列为 48，35，61，98，82，18，29，48 的记录进行从小到大排序，写出排序过程和结果。

每次选择最小的和未排序的第一个元素交换

答：第一趟：18,35,61,98,82,48,29,48 第二趟：18,29,61,98,82,48,35,48 第三趟：18,29,35,98,82,48,61,48 第四趟：18,29,35,48,82,98,61,48 第五趟：18,29,35,48,48,98,61,82 第六趟：18,29,35,48,48,61,98,82 第七趟：18,29,35,48,48,61,82,98

==直接选择排序，时间复杂度为 O(n^2^)，算法不稳定==

堆排序

堆排序是通过二叉树来进行学习的

教材中有两个重要概念

最小堆：任一结点的值都不大于它的两个孩子的值最大堆：任一结点的值都不小于它的两个孩子的值

动图展示（图片来源网络）

自考真题

判断序列（28，75，33，68，25，56，47，99，86，36）是否为堆？如果不是，则把它调整为堆（最小堆）。

要点，画出二叉树，然后调整为堆即可

不是堆，75 所在结点大于子结点，开始调整

调整之后，把 25 调整到最上部

最小堆序列为：25,26,33,68,36,56,47,99,86,75

==直接选择排序，时间复杂度为 O(nlog~2~n)，算法不稳定==

归并排序

归并的含义是将两个或两个以上的有序表合并成一个新的有序表。合并的方法是比较各子序列的第一个记录的键值，最小的一个就是排序后序列的第一个记录的键值。

二路归并排序

看图理解（图片来源网络）

自考真题

若采用二路归并排序方法对关键字序列（25，9，78，6，65，15，58，18，45，20}进行升序排序，写出其每趟排序结束后的关键字序列。

要点：二二合并排序

答：初始化：[25]，[9]，[78]，[6]，[65]，[15]，[58]，[18]，[45]，[20]第一趟：[9,25],[6,78],[15,65],[18,58],[20,45]第二趟：[6,9,25,78],[15,18,58,65],[20,45]第三趟：[6,9,15,18,25,58,65,78],[20,45]第四趟：[6,9,15,18,20,25,45,58,65,78]

==直接选择排序，时间复杂度为 O(nlog~2~n)，算法稳定==

结束语

到现在为止，数据结构期末不挂科指南已经全部完成，作为入门数据结构导论，自考的这门教材还不错，但是作为程序员来说，数据结构的大门刚刚为你打开。