数据结构篇：常用排序算法回顾

类别	排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	存储方式及稳定性
插入排序	直接插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	顺序√ 链式√
插入排序	折半插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	顺序√
插入排序	希尔排序	$O(nlog_2n)$ / $O(n^{1.3})$	$O(n^2)$	$O(1)$	顺序 ×
交换排序	冒泡排序	$O(n^{2})$	$O(n^{2})$	$O(1)$	顺序√ 链式√
交换排序	快速排序	$O(nlog_2{n})$	$O(nlog_2{n})$	$O(log_2{n})$	顺序 ×
选择排序	简单选择排序	$O(n^{2})$	$O(n^{2})$	$O(1)$	顺序 × 链式√
选择排序	堆排序	$O(nlog_2{n})$	$O(nlog_2{n})$	$O(1)$	顺序 ×
归并排序	归并排序	$O(nlog_2{n})$	$O(nlog_2{n})$	$O(n)$	顺序√
基数排序	基数排序	$O(r)$	$O(n^{2})$	$O(d(n+r))$	顺序√ 链式√

（一）基本概念

1. 排序

• def 重排列表中元素，使其满足按关键字有序的过程

2. 算法的稳定性

稳定的排序	不稳定排序
冒泡排序	快速排序
插入排序	希尔排序
归并排序	简单选择排序
基数排序	堆排序

• quiz 如何说明某算法是不稳定的？

  答：对于该算法，可证有一组关键字的实例，在排序后原先排序相对在前的元素现被置后（相对位置改变），是为不稳定的

3. 分类

• 内部排序

  • def 排序期间，元素全部的存放在内存中
  • 基于比较（除基数排序）和移动，关注复杂度

• 外部排序

  • def 排序期间，元素无法全部同时存放在内存中，需要在内存与外存间不断移动
  • 除复杂度考量，还需关注如何减少磁盘 IO

（二）插入排序

1. 直接插入排序

// 直接插入排序
void insertSort(ElemType a[], int n) {
	int i, j;
	for (int i = 2; i <= n; i++) {
		if (a[i] < a[i - 1]) {
			a[0] = a[i];         // a[0]: sentinel
			for (int j = i - 1; a[j] > a[0]; j--)
				a[j + 1] = a[j]; // shift right
			a[j + 1] = a[0];	 // insert
		}
	}
}

• method 每次取⼀待排序记录按关键字大小插入到前面已排好序的子序列中， 重复直到完成

• 时间复杂度：$O(n^2)$

  • 最好情况下比较 0 次、移动 n-1 次，为 O (n)；最坏情况下比较$\\\sum_{i=2}^{n}i$ 次、移动$\\\sum_{i=2}^{n}(i+1)$ 次，为$O(n^2)$

• 空间复杂度：$O(1)$

• 稳定：√

• 适用：顺序和链式存储，链式存储可从前往后依次查找

2. 折半插入排序

// 折半插入排序
void insertSort(ElemType a[], int n) {
	int i, j, low, high, mid;
	for (int i = 2; i <= n; i++) {
		a[0] = a[i];

		low = 1, high = i - 1;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (a[mid] > a[0]) high = mid - 1;
			else low = mid + 1;
		}
		for (j = i - 1; j >= high - 1; --j) {
			a[j + 1] = a[j]; // shift right
		}
		a[high + 1] = a[0];
	}
}

• method 先⽤折半查找找到应该插⼊的位置，再移动元素

• 时间复杂度：$O(n^2)$，分析同上，仅减少了比较元素的次数，约为$O(nlog_2{n})$

• 空间复杂度：$O(1)$

• 稳定：√

• 适用：顺序存储

3. 希尔排序（递减增量排序）

// 希尔排序
void shellSort(ElemType a[], int n) {
	int dk, i, j;
	for (dk = n / 2; dk >= 1; dk /= 2) {
		for (i = dk + 1; i <= n; i++) {
			if (a[i] < a[i - dk]) {
				a[0] = a[i];
				for (j = i - dk; j > 0 && a[0] < a[j]; j -= dk)
					a[j + dk] = a[j];
				a[j + dk] = a[0];
			}
		}
	}
}

• method 先追求表中元素部分有序，再逐渐逼近全局有序

  • 将待排序表分割成 L [i, i + d, i + 2d,…, i + kd] 的 “特殊” 子表，对各个子表直接插⼊排序。缩小增量 d，重复直到 d = 1

• 时间复杂度：$O(n^{1.3})$（n 在某特定范围时）

• 空间复杂度：$O(1)$

• 稳定：×

• 适用：基本有序的顺序存储

（三）交换排序

1. 冒泡排序

// 从后往前
void bubbleSort(ElemType a[], int n) {
	for (int i = 0; i < n - 1; i++)
		for (int j = n - 1; j > i; j--)
			if (a[j - 1] > a[j])
				swap(a[j - 1], a[j]);
}

// 从前往后
void bubbleSort2(ElemType a[], int n) {
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < n - i - 1; j++)
			if (a[j] > a[j + 1])
				swap(a[j], a[j + 1]);
}

• method 从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 A [i-1]>A [i]），则交换它们，直到序列比较完

• 时间复杂度：$O(n^{2})$

• 空间复杂度：$O(1)$

• 稳定：√

• 适用：基本有序的顺序、链式存储

2. 快速排序

// 快速排序 （in C++）
void quick_sort(int q[], int l, int r) {
    if (l >= r) {
        return;
    }
    int i = l - 1, j = r + 1, x = q[l + ((r - l) >> 1)];
    while (i < j) {
        do {
            i++;
        } while (q[i] < x);
        do {
            j--;
        } while (q[j] > x);
        if (i < j) {
            swap(q[i], q[j]);
        }
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

// 快速排序 （in Java）
private static void quickSort(int l, int r) {
    if (l >= r) {
        return;
    }
    int x = q[l + ((r - l) >> 1)];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do {
            i++;
        } while (q[i] < x);
        do {
            j--;
        } while (q[j] > x);
        if (i < j) {
            swap(i, j);
        }
    }
    quickSort(l, j);
    quickSort(j + 1, r);
}

private static void swap(int i, int j) {
    int t = q[i];
    q[i] = q[j];
    q[j] = t;
}

• method

  • 在待排序表 L [1…n] 中任取⼀个元素 pivot 作为枢轴
  • ⼀次划分将待排序表划分为独立的两部分 L [1…k-1] 和 L [k+1…n]，使左边所有元素 \textlesspivot，右边所有元素$\geq$ pivot，pivot 放在其最终的位置 L (k) 上
  • 对两子表分别递归重复，直至每部分只有⼀个元素或空

• 时间复杂度：$O(nlog_2{n})$，划分均匀，则最好情况下时间复杂度为$O(n^2)$；若原排序表基本逆序或正序，则最坏情况下时间复杂度为$O(nlog_2{n})$

• 空间复杂度：$O(log_2{n})$，最好情况下容量与递归调用的最大深度一致，为$O(log_2{n})$；最坏情况下进行 n-1 次递归调用，为$O(n)$

• 稳定：×

• 适用：顺序存储

（四）选择排序

1. 简单选择排序

// 选择排序
void selectSort(ElemType a[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int min = a[i];
		for (int j = i + 1; j < n; j++)
			if (a[j] < a[min]) min = j;
		if (min != i) swap(a[i], a[min]);
	}
}

• method 每⼀趟在待排序元素中选取关键字最小的元素加⼊有序子序列

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(1)$

• 稳定：顺序 × 链式√

• 适用：顺序、链式存储

2. 堆排序

// 建立大根堆
void buildMaxHeap(ElemType a[], int len) {
	for (int i = len / 2; i > 0; i--) {
		heapAdjust(a, i, len);
	}
}

// 将以k为根的子树调整为大根堆
void heapAdjust(ElemType a[], int k, int len) {
	a[0] = a[k];
	for (int i = 2 * k; i <= len; i *= 2) {
		if (i < len && a[i] < a[i + 1]) i++;
		if (a[0] >= a[i]) break;
		else {
			a[k] = a[i];
			k = i;
		}
	}
	a[k] = a[0];
}

// 堆排序
void heapSort(ElemType a[], int len) {
	buildMaxHeap(a, len);
	for (int i = len; i > 1; i--) {
		swap(a[i], a[1]);
		heapAdjust(a, 1, i - 1);
	}
}

• method 每⼀趟将堆顶元素加⼊有序子序列 （与待排序序列中的最后⼀个元素交换）

$$\sum^1_{i=h-1}2^{i-1}2(h-i) = \sum^1_{i=h-1}2^i(h-i) = \sum^{h-j}_{j=1}2^{h-j}j \leq \sum^{h-j}_{j=1}\frac{j}{2^j} \leq 4n$$

• 时间复杂度：$O(nlog_2{n})$

  • 建堆 $O(n)$：⼀个结点，每 “下坠” ⼀层，最多只需对比关键字 2 次
    • 若树高为 h，某结点在第 i 层，则将这个结点向下调整最多只需要 “下坠” h-i 层，关键字对比次数不超过 2 (h-i)，n 个结点的完全二叉树树高 h=⌊log2n⌋ + 1
    • 第 i 层最多有 2i−1 个结点，而只有第 1 ~ (h-1) 层的结点才有可能需要 “下坠” 调整
    • 将整棵树调整为大根堆，关键字对比次数不超过 4n
  • 排序 $O(nlog_2{n})$：根节点最多 “下坠” h-1 层，每 “下坠” ⼀层最多只需对比关键字 2 次，因此每⼀趟排序复杂度不超过 $O(h) = O(log_2n)$ ；共 n-1 趟，总的时间复杂度 = $O(nlog_2n)$

• 空间复杂度：$O(1)$

• 稳定：×

• 适用：顺序存储

（五）归并排序

// 归并排序（in C++）
void mergeSort(int q[], int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = l + ((r - l) >> 1);
    mergeSort(q, l, mid);
    mergeSort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) {
            tmp[k++] = q[i++];
        }
        else {
            tmp[k++] = q[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = q[i++];
    }
    while (j <= r) {
        tmp[k++] = q[j++];
    }
    for (i = l, j = 0; i <= r; i++, j++) {
        q[i] = tmp[j];
    }
}

// 归并排序（in Java）
private static void mergeSort(int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(l, mid);
        mergeSort(mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) {
                tmp[k++] = q[i++];
            } else {
                tmp[k++] = q[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = q[i++];
        }
        while (j <= r) {
            tmp[k++] = q[j++];
        }

        for (i = l, j = 0; i <= r; i++, j++) {
            q[i] = tmp[j];
        }
    }

• method 把两个或多个已经有序的序列合并成⼀个；只剩⼀个子表未合并时，可以将该表中剩余元素全部加到总表

  • 形态上是⼀棵倒立的二叉树

• 时间复杂度：$O(nlog_2{n})$，n 个元素进行 2 路归并排序，归并趟数 = ⌈log2n⌉，每趟归并时间复杂度为$O(n)$

• 空间复杂度：$O(n)$

• 稳定：√

• 适用：顺序存储

（六）基数排序

// 基数排序
int maxbit(ElemType a[], int n) {
	int maxData = a[0];
	for (int i = 1; i < n; i++)
		maxData = max(maxData, a[i]);

	int d = 1, p = 10;
	while (maxData >= p)
		maxData /= 10, ++d;

	return d;
}

void radixSort(ElemType a[], int n) {
	int d = maxbit(a, n);
	int* tmp = new int[n], * count = new int[10];
	int i, j, k, radix = 1;
	for (i = 1; i <= d; i++) {
		for (j = 0; j < n; j++)
			count[j] = 0; // init
		for (j = 0; j < n; j++) {
			k = (a[j] / radix) % 10; // allocate
			count[k]++;
		}
		for (j = 1; j < 10; j++)
			count[j] += count[j - 1]; 
		for (j = n - 1; j >= 0; j--) {
			k = (a[j] / radix) % 10;
			tmp[count[k] - 1] = a[j]; // collect
			count[k]--;
		}
		for (j = 0; j < n; j++)
			a[j] = tmp[j]; 
		radix *= 10;
	}
	delete[]tmp, count;
}

• method

  • 初始化： 设置 r 个空队列，$Q_0, Q_1,…, Q_{r−1}$ 按照各个关键字位权重递增的次序（个、十、百），对 d 个关键字位分别做 “分配” 和 “收集”
  • 分配：顺序扫描各个元素，若当前处理的关键字位 = x，则将元素插⼊ $Q_x$ 队尾
  • 收集：把 $Q_0, Q_1,…, Q_{r−1}$ 各个队列中的结点依次出队并链接

• 时间复杂度：$O(r)$，r 为每组关键字的取值范围

  • 基数排序不是基于 “比较” 的排序算法
  • 收集一个队列只需 O (1) 时间

• 空间复杂度：$O(d(n+r))$，需要 r 个辅助队列，把关键字拆为 d 个部分，每个部分可能取得 r 个值

• 稳定：√

• 适用：一般为链式存储，组数 d 和关键字取值范围 r 较小、而数据元素个数 n 较大的情况

（七）外部排序

1. 多路归并排序

• method 各个⼦序列有序，每次读入两个块的内容，进行内部排序后写回磁盘

• 外部排序时间开销 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间

2. 败者树

• method 使⽤多路平衡归并可减少归并趟数，但是该方法从 k 个归并段选出⼀个最 小 / 最大元素需要对比关键字 k-1 次，构造败者树可以使关键字对比次数减少到 ⌈log2k⌉

  • 非叶子结点用来记忆左右子树中的 “失败者”，而让胜者往上继续进行比较直到根结点

3. 置换 - 选择排序

设初始待排文件为 FI，初始归并段输出文件为 FO，内存⼯作区为 WA，FO 和 WA 的初始状态为空，WA 可容纳 w 个记录。置换 - 选择算法的步骤如下：

• 从 FI 输⼊ w 个记录到工作区 WA

• 从 WA 中选出其中关键字取最小值的记录，记为 MINIMAX 记录

• 将 MINIMAX 记录输出到 FO 中去

• 若 FI 不空，则从 FI 输⼊下⼀个记录到 WA 中

• 从 WA 中所有关键字比 MINIMAX 记录的关键字⼤的记录中选出最小关键字记录，作为新的 MINIMAX 记录

• 重复 3～5 直⾄在 WA 中选不出新的 MINIMAX 记录为止，由此得到⼀个初始归并段，输出⼀个归并段的结束标志到 FO 中去

• 重复 2～6 直⾄ WA 为空，得到全部初始归并段