ZJU 数据结构课程笔记 | 排序

这是我在学习浙江大学 MOOC『数据结构』的第六章：排序 的过程中做的笔记。

ZJU 数据结构 MOOC 课程链接

前提

N是正整数
只讨论基于比较的排序 (默认从小到大排序)
只讨论内部排序 (排序的数据元素全部存放在计算机内存)
稳定性: 任意两个相等的数据, 排序前后的相对位置不改变

没有一种排序时任何情况下都是表现最好的, 须灵活选取

简单排序

冒泡排序

每遍历一次筛出最大值

void Bubble_Sort(ElementType A[], int N)
{
	for (P = N - 1; P >= 0; P --) { //待排元素下标
		flag = 0;
		for (i = 0; i < P; i ++) {
			if (A[i] > A[i + 1]) {
				swap(A[i], A[i + 1]);
				flag = 1;
			}
		}
		if (flag == 0) break; //没有发生交换
	}
}

插入排序

void Insertion_Sort(ElementType A[], int N)
{
	//排序开始时, 假设数组首位已经有序
	for (P = 1; P < N; P ++) {
		tmp = A[P]; //待插元素
		for (i = P; i > 0 && A[i - 1] > tmp; i --)
			A[i - 1] = A[i]; //较大元素后移, 为tmp插入提供空位
		A[i] = tmp; //插入操作
	}
}

时间复杂度下界

逆序对: 对于i < j, 若A[i] > A[j], 称(i, j)是一对逆序对 (inversion)

对任意序列, 交换两个相邻元素可以消去一个逆序对

定理:

任意N个不同元素组成的序列平均具有N*(N - 1) / 4个逆序对.
任何仅交换相邻两元素的排序算法, 平均时间复杂度为( ).

要提高算法效率, 我们必须:

每次消去不止一个逆序对.
每次交换相隔较远的两个元素.

希尔排序

定义递减的增量序列

对每个进行”-间隔”排序 (T = )

“-间隔”有序的序列, 再执行”-间隔”排序后, 仍然时”-间隔”有序的

void Shell_sort(ElementType A[], int N)
{
	for (D = N / 2; D > 0; D /= 2) { //希尔增量序列
		for (P = D; P < N; P += D) { //插入排序
			Tmp = A[P];
			for (i = P; i >= D && A[i - D] > Tmp; i -= D) {
				A[i] = A[i - D];
			}
			A[i] = A[Tmp];
		}
	}
}

增量元素不互质, 则小增量可能根本不起作用.

Hibbarb增量序列

相邻元素互质

最坏情况:

猜想:

Sedgewick增量序列

$D_k=94^i-92^i+1$ or

猜想:

堆排序

选择排序

void Selection_sort(ElementType A[], int N)
{
	int i, j, k, t;
	for (i = 0; i < N; i ++) {
		for (j = i + 1, k = i; j < N; j ++) {
			if (A[j] < A[k]) k = j; 
		}
		if (k != i) {
			t = A[i]; A[i] = A[k]; A[k] = t;
		}
	}
}

如何快速找到最小元?

堆排序

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

基本思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列
实现逻辑
① 先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素.
② 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key.
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆.
④ 直到无序区只有一个元素为止.

void Heap_sort(ElementType A[], int N)
{
	BuildHeap(A);
	for (i = 0; i < N; i ++) {
		TmpA[i] = DeleteMin(A);
	}
	for (i = 0; i < N; i ++) {
		A[i] = Tmp[i];
	}
}

该算法需要额外开辟空间存放数据, 效率低下.

改进:

void Heap_sort(ElementType A[], int N)
{
	for (i = N / 2; i >= 0; i --) {
		percdown(A, i, N);
	}
	for (i = N - 1; i > 0; i --) {
		Swap(&A[0], &A[i]);
		percdown(A, 0, i);
	}
}

时间复杂度:

有序子列归并

void Merge(ELementType A[], ElementTypep TmpA[]
		  int L, int R, int RightEnd)
{
	LeftEnd = R - 1;
	Tmp = L;
	NumElements = RightEnd - L + 1;
	while (L <= LeftEnd && R <= RightEnd) {
		if (A[L] <= A[R]) TmpA[Tmp ++] = A[L ++];
		else TmpA[Tmp ++] = A[R ++];
	}
	while (L <= LeftEnd)
		TmpA[Tmp ++] = A[L ++];
	while (R <= RightEnd)
		TmpA[Tmp ++] = A[R ++];
	for (i = 0; i < NumElements; i ++, RightEnd --)
		A[RightEnd] = TmpA[RightEnd];
}

递归算法

分而治之

void MSort(ElementType A[], ElementType TmpA[], int L, int RightEnd)
{
	int Center;
	if (L < RightEnd) {
		Center = (L + RightEnd) / 2;
		MSort(A, TmpA, L, Center);
		MSort(A, TmpA, Center + 1, RightEnd);
		Merge(A, TmpA, L, Center + 1, RightEnd);
	}
}

时间复杂度: .

优点: 具有稳定性. 缺点: 不友好.

优化: 统一函数接口

void Merge_sort(ELementType A[], int N)
{
	ElementType *TmpA;
	TmpA = (ElementType *)malloc(N * sizeof(ElementType));
	if (TmpA != NULL) {
		MSort(A, TmpA, 0, N - 1)
		free(TmpA);
	}
	else Error("No Space");
}

非递归算法

to be continue…