第七章排序 - 《数据结构导论》笔记

概要

阅读说明

以下排序方法均以按递增（即升序）排列的方式对序列进行排序。

概述

排序就是将一组对象按照规定的次序重新排列的过程，是数据处理中一种很重要也很常用的运算。

排序是为检索服务的，例如图书馆书的摆放是按照索引号排序以后的结果，再例如电话号码簿、字典等。

而排序又分为两大类：

内部排序（Internal Sorting）：待排序的记录全部存放在计算机内存中进行的排序过程。
外部排序（External Sorting）：待排序的记录数量很大，内存不能存储全部记录，需要对外存进行访问的排序过程。

排序的方法有很多，例如插入排序、交换排序、选择排序和归并排序等等。

而排序方法一般会关注以下指标：

稳定性：对于相当的元素，排序前和排序后的相对位置（位置关系）是否有发生变化，如果没有，则说明排序的方法是稳定的，否则是不稳定的。
- 例如一个序列中有两个66，分别用R0和R1表示，排序前R0在R1的前面，而稳定是指排序以后R0仍然在R1的前面。
- 稳定性是排序方法本身的特性，与数据无关，也就是说，一种排序方法如果是稳定的，则排序处理对数据序列中的所有数据都是稳定的，相反如果有一组数据出现不稳定，该方法就是不稳定的。
时间复杂度和空间复杂度。

插入排序

常用的插入排序有：

直接插入排序，文中只介绍了这一种。
折半插入排序。
表插入排序。
希尔排序。

直接插入排序

Straight Insertion Sorting是一种简单的排序方法，它的思想是将未排序区的元素逐个有序地插入到已排序区的合适位置，并始终保持已排序区的有序性。

直接插入排序类似图书馆中整理图书的过程。

步骤如下：

将待排序的序列分成已排序区和未排序区。
从未排序区中取出第一个元素，在已排序区中，从后往前比较，小的话就往前面的位置放，直到找到插入位置并进行插入操作，此时已排序区依然是有序的。
重复步骤2，直到所有元素都被插入到已排序区中。

例如有一个待排序的序列：(45, 38, 66, 90, 88, 10, 25, 45)，序列中有两个45以说明算法的稳定性。

排序过程如下：

已排序区为空，未排序区为如上序列。
未排序区中取出第一个元素45，直接放进已排序区中。
取出第二个元素38，在已排序区中从后往前对元素进行比较，即45和38比，大了，让38排在前面。
- 此时已排序区序列：(38, 45)。
取出第三个元素66，比45大，排在45的后面，90同理，不做赘述。
- 此时已排序区序列：(38, 45, 66, 90)。
取出第五个元素88，90和88比，大了，再往前找一个元素进行比较，即66和88比，小了，说明再往前的元素都是比66还要小，无需再往前找了，就排在90的前面。
- 此时已排序区序列：(38, 45, 66, 88, 90)。
后面的元素同理，不再赘述。

给出具体的算法，说明：

序列R的0的位置不使用，用于岗哨的作用。
n为表长。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void StraightInsertSort(List R, int n)
{
	int i, j;
	for (i = 2; i <= n; i++) {
		R[0] = R[i];
		j = i-1;
		while (R[0].key < R[j].key) {
			R[j+1] = R[j];
			j--;
		}
		R[j+1] = R[0];
	}
}

该算法，R[0]的位置起到了两个作用：

保存了R[i]位置的值，拿上面例子的步骤6为例，把已排序区中大于88的元素全部往后一个位置覆盖，当和66比较的时候结束了while循环，这个时候就从岗哨的位置即R[0]里取出88，避免了覆盖导致的丢失，最终放到了R[j+1]的位置，已排序区保持有序。
在while循环条件中起到了监视数组下标变量j是否越界，实现了自动控制while循环的结束，而不必特意去检查越界的情况。

一个字，妙啊。

总结规律：

直接插入排序算法简单，易于理解，容易实现。
来看下指标：
- 45的相对位置没有变化，具有稳定性。
- 时间复杂度为O(n²)。
- 只需要一个记录的辅助空间，并不随循环的变化而导致空间的增加，空间复杂度为O(1)。
若待排序记录的数量很大时，一般不选用直接插入排序。

交换排序

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

递增排序，记录值小的放到前面，大的放到后面。
递减排序，大的放到前面，小的放到后面。

冒泡排序

冒泡排序Bubble Sorting是一种交换排序方法，其处理过程是：

将第一个记录键值和第二个记录键值比较。
- 若为逆序，即第一个记录比第二个记录大，则交换这两个记录。
- 不为逆序，不操作。
然后继续比较第二个和第三个记录键值，依次类推，直至比较完最后一个记录键值。
以上过程称为第一趟起泡，作用是将记录键值最大的记录移到第n个位置上，即第n个位置已经是排序好的区域了。
第二趟起泡将从步骤1重新开始，直到未排序区域的最后一个记录键值结束。
重复以上过程，直到未排序区域仅剩下一个时，整个排序过程终止。

举个例子，现有一组待排序序列：(45，38，66，90，88，10，25，45)，排序过程如下：

第一趟排序结果：38，45，66，88，10，25，45，90。
- 45和38比较，45大，交换两者位置。
  - 交换后序列：38，45，66，90，88，10，25，45。
- 45和66比，无逆序，不操作。
- 66和90比，不操作。
- 90和88比，90大，交换位置。
  - 交换后序列：38，45，66，88，90，10，25，45。
- 90和10比，90大，交换位置。
  - 交换后序列：38，45，66，88，10，90，25，45。
- 后者同理，不再赘述。
第二趟排序结果：38，45，66，10，25，45，88，90。
第三趟排序结果：38，45，10，25，45，66，88，90。
第四趟排序结果：38，10，25，45，45，66，88，90。
第五趟排序结果：10，25，38，45，45，66，88，90。
第六趟排序结果：10，25，38，45，45，66，88，90。
第七趟排序结果：10，25，38，45，45，66，88，90。

算法如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

总结：

冒泡排序时间复杂度为$O(n^2)$。
冒泡排序是稳定的排序方法。

快速排序

快速排序Quick Sorting是交换排序的一种，实际上是对冒泡排序的一种改进。思想是：