数据结构导论【七】之排序_数据结构导论堆排序演示

接上一篇：数据结构导论【六】之 查找表

一、概述

数据排序 – 将一个文件的记录按关键字不减（或不增）次序排列，使文件成为有序文件，此过程称为排序。

稳定排序 – 若排序后，相同关键字的记录保持它们原来的相对次序，则此排序方法称为 稳定排序。

不稳定排序 – 若排序后，相同关键字的记录 不能 保持它们原来的相对次序，则此排序方法称为 不稳定排序。

排序类型：
1.内部排序：全部数据存于内存
2.外部排序：需要对外存进行访问的排序过程

---

稳定性是排序方法本身的特性，与数据无关，换句话说，一种排序方法如果是稳定的，则对所有的数据序列都是稳定的，反过来，如果在一组数据上出现不稳定的现象，则该方法是不稳定的。

---

排序文件的物理表示：数组表示

typedef struct {
	int key; // 关键字项
	ItemType otherItem; // 其他数据项
} RecordType;
typedef RecordType list[n + 1];

list R;
R[0] R[1] R[2] ... R[n]
R[i].key -- 第i个记录的关键字
1
2
3
4
5
6
7
8
9

---

二、插入排序（通过比较插入实现排序）

常见的插入排序方法

1. 直接插入排序
2. 折半插入排序
3. 表插入排序
4. 希尔排序

1.直接插入排序

①过程

对R₁， …,R_i-1已排好序，有K₁ <= K₂ <= … <=K_i-1,
现将K_i依次与K_i-1，K_i-2，…进行比较，并移动元素，直到发现R_i应插在R_j与R_j+1之间（即有K_j <= K_i < K_j+1），则将R_i插到j + 1号位置上，形成i个有序序列。(i 从 2 ~ n)

---

②算法分析

空间复杂度O(1)
时间复杂度O(n²)
稳定性：稳定排序。

---

③算法实现

void StraightInsertSort(list R, int n) {
	// 用直接插入排序法对R进行排序
	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]; // 插入
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

---

三、交换排序（通过比较交换实现排序）

1.冒泡排序

a.基本思想

通过多次重复比较、交换相邻记录而实现排序；每一趟的效果都是将当前键值最大的记录换到最后。

b.例

c.冒泡排序算法实现

void BubbleSort(List R, int n) {
	// 用冒泡排序法对R[1]...R[n]进行排序
	int i, j, temp, endsort;
	for (i = 1; i <= n - 1; i++) {
		// 若循环中记录未作交换，则说明序列已有序
		endsort = 0;
		for (j = 1; j <= n - i; j++) {
			if (R[j].key > R[j+1].key) {
				temp = R[j];
				R[j] = R[j + 1];
				R[j + 1] = temp;
				endsort = 1;
			}
		}
		if (endsort == 0) break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

d.算法分析

时间复杂度：
外循环最多n - 1次（最少1次），
第i次外循环时，内循环n-i次比较，
最大比较次数为 ${\sum }_{i=1}^n$
n - i = n(n - 1) / 2 ≈ n² / 2 = O(n²)

空间复杂度：O(1)
稳定性：稳定排序。

---

2.快速排序

a.基本思想

通过分步排序完成整个表的排序；
首先取第一个记录，将之与表中其余记录比较并交换，从而将它放到记录的正确的最终位置，使记录表分成俩部分 {其一(左边的)诸记录的关键字均小于它；其二（右边的）诸记录的关键字均大于它}；然后对这俩部分重新执行上述过程，依此类推，直至排序完毕。

---

b.过程

记录序列{r[h], r[low+!],…,r[p]}
设：左指针i，右指针j；
初值：i = h；j = p；处理元素 => x;

①j指针逐步左移，即：
将r[j]与x比较，j不断减1，直到发现某个r[j].key < x.key时，
则：
r[j] => i 位置上（开始时 i = 1）；i + 1 => i；转(2)

②i指针逐步右移，即：
将r[i]与x比较，i不断增1，直到发现某个r[i].key > x.key时，
则：
r[i] => j 位置上； j - 1 => j; 转(1);

③此过程直到①或②中 i = j 时停止，此时将处理元素x送到i或j位置上，它将原序列分为左、右俩个子序列，对它们分别进行上述过程，直至分裂后的子序列都只有一个元素为止。

c.快速排序算法实现

// h代表头，p代表尾
void quickpass(list r, int h, int p) {
	// 对顺序表r中的子序列r[h]至r[p]进行快速排序
	// 左右指针置初值
	i = h;
	j = p;
	// 取处理元素（即作为中轴记录）
	x = r[h];
	// 左右指针未碰头则反复做
	while (i < j) {
		while (r[j].key > x.key && i < j) {
		    // 右边未找到小关键字，则右指针j继续左移
			--j;
		}
		if (i < j) { // 右边找到比中轴记录小的记录，则将其送到左边
			r[i] = r[j];
			++i;
		}
		// 左边未找到大关键字，则左指针i继续右移
		while(r[i].key <= x.key && i < j) {
			++i;
		}
		// 左边找到比中轴记录大的记录，则将其送到右边
		if (i < j) {
			r[j] = r[i];
			--j;
		}
	}
	r[i] = x; // 中轴记录定位
	if (h < i - 1) {
		quickpass(r, h, i - 1); // 对左子序列进行快速排序
	}
	if (j + 1 < high) {
		quickpass(r, j + 1, p); // 对右子序列进行快速排序
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

d.算法分析

空间：O(log₂n)
时间：O(nlog₂n)
最差：O(n²)

注：若初始记录表有序或基本有序，则快速排序将蜕化为冒泡排序，其时间复杂度为O(n²);
即：快速排序在表基本有序时，最不利于其发挥效率。
稳定性：不稳定排序。

---

四、选择排序

1.直接选择排序

a.过程

设记录R1，R2,…,Rn，对i=1，2，…n-1重复下列工作：
1.在Ri,…,Rn中选最小（或最大）关键字记录Rj；
2.将Rj与第i个记录交换位置，即将选到的第i小的记录换到第i号位置上。

b.例

c.直接选择排序算法实现

void SelectSort(List R, int n) {
	for(i = 1; i <= n - 1; i++) {
		min = i; // 选择第i小的记录，并交换位置
		for(j = i + 1; j <= n; j++) {
			// 在R[i]...R[n]中找最小者
			if (R[j].key < R[min].key) {
				min = j;
			}
		}
		// 交换位置
		if (min != i) {
			temp = R[i];
			R[i] = R[min];
			R[min] = temp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

d.算法分析

空间：O(1)
时间：C_总=${\sum }_{i=1}^n$(n - i) = (n²-1) / 2 ≈ O(n²)
稳定性：不稳定排序

---

2.堆排序

a.堆

集合{K1, K2, … Kn},
对所有i = 1,2,…,n/2有：
K_i <= K_2i 且 K_i <= K_2i+1,
则此集合称为堆（最小堆）；
或K_i >= K_2i 且 K_i >= K_2i+1（则此集合称为最大堆）
例：
{13,40,27,88,55,34,65,92}（最小堆）
{92,65,88,40,55,34,13,27}（最大堆）

b.建堆（筛选法）

①方法

设记录{R1,R2,…Rn}
1.顺序输入成完全二叉树（以数组存储）
2.从最后一个双亲开始，如果有较小的孩子，则将其沿左或右孩中小的那个方向筛下，一直到不能再筛；
3.逐次处理完每个双亲。

---

②例子

---

③算法

下筛一个结点算法
建堆：对k=n/2,…1依次调用sift

---

c.堆排序

①过程

①从i = int(n / 2) -> 1
调用sift(r, i, n)建初始堆
对i = n, n - 1, n - 2,…,2重复②、③
②输出r[1]，即：r[1] <–> r[i]
③调用sift(r, 1, i - 1)，重新建堆

---

②例

d.算法分析

空间：O(1)(仅需一个记录大小的供交换用的辅助存储空间。)
时间：O(nlog₂n)
稳定性：不稳定排序

---

五、归并排序

1.有序序列的合并（俩个有序表归并成一个有序表）

思想
比较各个子序列的第一个记录的键值，最小的一个就是排序后序列的第一个记录。取出这个记录，继续比较各子序列现有的第一个记录的键值，便可找出排序后的第二个记录。如此继续下去，最终可以得到排序结果。

---

2.二路归并排序

a.思想

①n个记录的表看成n个长度为1的有序表
②俩俩归并成n/2个长度为2的有序表（n为奇数，则还有一个长为1的表）
③再俩俩归并为(n/2)/2个长度为4的有序表
再俩俩归并直至只剩1个长度为n的有序表；

共log₂n趟

---

b.例

c.算法实现

void Merge(List a, List R, int h, int m, int n) {
	// 将ah,...am和am+1,...,an俩个有序序列合并成一个有序序列Rh,...Rn
	// k, j置为文件的起始位置
	k = h;
	j = m + 1;
	// 将a中记录从小到大合并入R
	while((h <= m) && (j <= n)) {
		// a[h]键值小，送入R[k]并修改h值
		if (a[h].key <= a[j].key) {
			R[k] = a[h];
			h++;
		} else { // a[j]键值小，送入R[k]并修改j值
			R[k] = a[j];
			j++;
		}
		k++;
	}
	// j > n,将ah,...am剩余部分插入R的末尾
	while(h <= m) {
		R[k] = a[h];
		h++;
		k++;
	}
	// h > m,将am+1,...an剩余部分插入R的末尾
	while(j <= n) {
		R[k] = a[j];
		j++;
		k++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

d.算法分析

空间：O(n)
时间：O(nlog₂n)
稳定性：稳定排序

---

六、各种排序方法的比较

---

---

---

~ You’re terrific! The End ~