一、概念

1. 内排序和外排序的定义

由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：内排序与外排序。

1. 内排序：待排序记录存放在计算机内存中进行的排序过程。插入排序、快速排序、选择排序、归并排序、基数排序等目前竞赛研究的算法基本上都是内排序方法。
2. 外排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。

2. 衡量效率的方法

2.1 内排序：

• 比较次数，也就是时间复杂度。

2.2 外排序：

• IO次数，也就是读写外存的次数。

3. 排序稳定性

如果两个元素的排序关键字相等，排序后它们的先后次序仍与排序前相同，就称这个排序算法是稳定的；如果相对次序可能改变，就称这个排序算法是不稳定的。

例如，按分数从小到大排列下面五名同学，括号中的字母用来区分不同的人：

57(A), 49(B), 26(C), 49(D), 5(E)

• 稳定排序的结果一定是：5(E), 26(C), 49(B), 49(D), 57(A)。
• 不稳定排序则可能得到：5(E), 26(C), 49(D), 49(B), 57(A)。

两种结果按分数看都是有序的。区别在于：49(B) 原来排在 49(D) 前面，稳定排序会保留这个顺序，而不稳定排序不保证保留。

二、常用排序算法

排序法	最坏时间	平均时间复杂度	稳定性	空间复杂度
插入排序	O(n²)		稳定	O(1)
选择排序			不稳定
冒泡排序			稳定
希尔排序	O(n^s), 1 ≤ s ≤ 2, 取决于增量序列	O(n^s)	不稳定
快速排序	O(n²)	O(n log n)		O(log n)
堆排序	O(n log n)			O(1)
归并排序			稳定	O(n)
计数排序	O(n+k)			O(k)

请注意，快速排序的平均时间复杂度是O(n log n)，堆排序的最坏和平均时间复杂度都是O(n log n)，空间复杂度为O(1)。希尔排序的平均时间复杂度取决于增量序列，通常在O(n^s)，其中1 ≤ s ≤ 2。归并排序的空间复杂度为O(n)，因为它需要额外的数组来存储合并过程中的元素。计数排序的空间复杂度为O(k)，其中k是输入数据中的最大值。

1. 插入排序

1.1 概念

插入排序会将数组分为两部分，前一部分是有序序列，后一部分是未排好序的序列。每一次操作，将未排好序的序列中的一个元素与有序序列中的元素分别进行比较，比较的过程从后向前，然后将该元素插入到有序序列的合适位置。

插入排序在实现上，需要用到O(1)的额外空间，因为在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序是一个时间复杂度为O(n²)的排序方法，对于每一个未排序的元素，都需要与有序序列中的元素进行从后向前比较，需要两层循环，外层是未排序的序列，内层是有序序列。

1.2 代码示例

2. 选择排序

2.1 概念

选择排序的工作原理是，每一次操作，从未排序的序列中选择最小（或最大）的元素，将其放到已排序的序列的最开始（或者末尾），直到未排序序列中的元素数量为0。

为了节省空间，使用一个数组进行排序操作。以升序序列为例。每一次操作，通过比较找出未排序的序列中最小的元素，将其与未排序序列的头元素交换，这样前一部分就会成为有序序列，每一次都会在有序序列末尾加上元素，最后以升序排列。

选择排序使用一个数组，每一次需要进行交换，因此使用的额外空间是O(1)。

选择排序是一个最好和最坏都是O(n²)时间复杂度的排序方法，比较的次数与序列的初始状态无关，总的比较次数为(n-1) + (n-2) + (n-3) + ... + 1 = n * (n-1) / 2次，交换次数为O(n)，最好为0（即序列本身有序），最坏为n-1次。

2.2 代码示例

3. 冒泡排序

3.1 概念

冒泡排序的工作原理是，重复地走访要排序的序列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。访问序列的工作是重复地进行直到没有再需要交换，也就是说该序列已经排序完成。

以升序为例。从头开始比较相邻的两个元素的大小，如果前面的元素大于后面的元素，就交换两个元素，第1次比较第1个和第2个，第2次比较第2个和第3个，以此类推，直到比较完所有的元素，这时，序列中最大的元素就会排到末尾，末尾的序列成为已排序的序列。然后，继续从头开始比较，重复上述过程，但只需要比较未排序的序列。直到未排序的序列中元素数量为0。

冒泡排序在一个数组中进行操作，排序的过程就是不断地进行比较和交换，因此空间复杂度为O(1)。

冒泡排序中，比较的次数与序列的初始状态没有关系。比较的次数为(n-1) + (n-2) + (n-3) + ... + 1 = n * (n-1) / 2次。因此时间复杂度为O(n²)。

3.2 代码示例

4. 快速排序

4.1 概念

快速排序的工作原理是，通过元素之间的比较和交换来达到排序的目的。每一轮挑选一个基准元素，并让其他比它大的元素移动到序列的一边，比它小的元素移动到另一边，从而把序列拆成两部分。因为这两部分内部依然无序，下一轮的序列就是基准元素两边的两个序列。

在实际操作中，每一轮会以序列的头元素为基准元素，在后面的序列中，从前向后找比基准元素大的值，从后向前找比基准元素小的值。前后都找到之后，交换两个元素。之后继续遍历，直到前后两个数组下标一样时，交换该元素与作为基准元素的头元素，此次操作结束。之后，以此元素为分界线，将前后两个序列分别进行上述操作，直到序列中只剩一个元素，快速排序即完成。

4.2 代码示例

5. 归并排序

5.1 概念

归并排序的工作原理是，对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的有序序列，逐层进行，最终合成一个有序序列，所有的元素都是有序的。

归并排序中，所有的操作都是在数组中完成的，序列的合并通过比较完成，因此空间复杂度是O(n)。

归并排序的每一轮会将序列折半，共需要log₂n轮，因此时间复杂度是O(nlog₂n)。

5.2 代码示例

6. 计数排序

6.1 概念

计数排序的工作原理是，将序列中的元素作为键存储在额外的数组空间中，而该元素的个数作为值存储在数组空间中，因为数组的索引是有序的，通过遍历该数组排序。

计数排序需要额外的数组空间，因此空间复杂度是O(k)。

计数排序只需要分别遍历原数组和新的数组，时间复杂度是O(n+k)。

6.2 代码示例

三、课后习题

1. NOIP2011 体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到一个比自己高的同学，并站在他的后面。这种站队的方法类似于X算法。

{{ select(1) }}

• 快速排序
• 插入排序
• 冒泡排序
• 归并排序

2. NOIP2009 排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列排序算法不稳定的是X。

{{ select(2) }}

• 冒泡排序
• 插入排序
• 归并排序
• 快速排序

3. NOIP2009 快速排序平均情况和最坏情况下的算法时间复杂度分别为X。

{{ select(3) }}

• 平均 (O(n\log n))，最坏 (O(n^2))。
• 平均 (O(n))，最坏 (O(n^2))。
• 平均 (O(n))，最坏 (O(n\log n))。
• 平均 (O(n\log n))，最坏 (O(n\log n))。

4. 如果不在快速排序中引入随机化，有可能导致的后果是X。

{{ select(4) }}

• 数组访问越界
• 陷入死循环
• 排序结果错误
• 排序时间退化为平方级

5. NOIP2010 基于比较的排序时间复杂度的下限是X，其中n是待排元素的个数。

{{ select(5) }}

• O(n)
• O($n\log{n}$)
• O(n^2)
• O(n^3)

6. NOIP2013 （X）的平均时间复杂度为O($n\log{n}$)，其中n是待排序的元素个数。

{{ select(6) }}

• 快速排序
• 插入排序
• 冒泡排序
• 基数排序

7. NOIP2014 以下时间复杂度不是O(n^2)的排序方法是X。

{{ select(7) }}

• 插入排序
• 归并排序
• 冒泡排序
• 选择排序

8. NOIP2017 对于给定的序列{ak}，我们把（i,j）称为逆序对当且仅当i<j且ai>aj。那么序列1，7，2，3，5，4的逆序对数为X个。

{{ select(8) }}

• 4
• 5
• 6
• 7

9. NOIP2012 使用冒泡排序对序列进行升序排序，每执行一次交换操作将会减少1个逆序对，因此序列5，4，3，2，1需要执行X次交换操作，才能完成冒泡排序。

{{ select(9) }}

• 0
• 5
• 10
• 15

10. NOIP2017 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做X次比较。

{{ select(10) }}

• $n^2$
• $\sqrt n$
• $2n$
• $2n-1$

11. 对初始数据序列{8，3，9，11，2，1，4，7，5，10，6}进行希尔排序。若第一趟排序结果为（1，3，7，5，2，6，4，9，11，10，8），第二趟排序结果为（1，2，6，4，3，7，5，8，11，10，9），则两趟排序采用的增量（间隔）依次是X。

{{ select(11) }}

• 3、1
• 3、2
• 5、2
• 5、3

12. 设线性表中每个元素有两个数据项k1和k2，现对线性表按以下规则进行排序：先看数据项k1，k1值小的元素在前，大的元素在后；在k1值相同的情况下，再看k2，k2值小的在前，大的元素在后。满足这种要求的排序方法是X。

{{ select(12) }}

• 先按k1进行直接插入排序，再按k2进行简单选择排序
• 先按k2进行直接插入排序，再按k1进行简单选择排序
• 先按k1进行简单选择排序，再按k2进行直接插入排序
• 先按k2进行简单选择排序，再按k1进行直接插入排序