经典排序算法小结
比较弱的排序算法
选择排序 (Selection Sort)
思想:扫描一次数组,我们就能得到最小值,把这个最小值取出,再扫描剩下的元素,就能得到第二小的值,以此类推。
设数组是A[0...n-1]
- 扫描
A[0...n-1]
,选出最小的,与A[0]
交换,A[0]
已经有序; - 扫描
A[1...n-1]
,选出最小的,与A[1]
交换,A[0...1]
已经有序; - 扫描
A[2...n-1]
,选出最小的,与A[2]
交换,A[0...2]
已经有序; - …
- 扫描
A[n-2...n-1]
,选出最小的,与A[n-2]
交换,A[0...n-2]
已经有序; - 整个数组已经有序
Notes: 一共扫描了
n-1
次,每一次扫描的范围都会减少一,总比较次数为n*(n-1)/2
;最多做n-1
次交换(选择排序的交换次数最少)。
- 时间复杂度:$O(n^2)$
- 为数不多的优点:原地排序
- 实际场景下几乎不使用
参考代码(C++):
template<typename T>
void SelectionSort(vector<T>& A) {
int n = A.size();
// 扫描n-1次
for (int i = 0; i < n - 1; ++i) {
int pos_min = i; // 最小值的位置
for (int j = i; j < n; ++j) {
if (A[j] < A[pos_min]) {
pos_min = j;
}
}
std::swap(A[i], A[pos_min]);
}
}
冒泡排序 (Bubble Sort)
思想:我有强迫症,看到这里有一对数字不是有序的,我就交换它们!又发现了一对,再交换…终于没有不是有序的数对了~
设数组是A[0...n-1]
- 考察
A[0]
和A[1]
,A[1]
和A[2]
…A[n-2]
和A[n-1]
,如果不是有序就交换,这一轮考察结束后,最大的已经被交换(冒泡)到A[n-1]
; - 考察
A[0]
和A[1]
,A[1]
和A[2]
…A[n-3]
和A[n-2]
,如果不是有序就交换,这一轮考察结束后,第2大的已经被交换(冒泡)到A[n-2]
; - …
- 考察
A[0]
和A[1]
,如果不是有序就交换,这一轮考察结束后,第n-1大的已经被交换(冒泡)到A[1]
; - 整个数组已经有序
Notes: 一共考察了
n-1
轮,每一轮考察的范围都会减少1,总比较次数为n*(n-1)/2
;最多做n*(n-1)/2
次交换(交换次数太多了)。
- 时间复杂度:$O(n^2)$
- 也属于排序的入门级算法
参考代码(C++):
template<typename T>
void BubbleSort(vector<T>& A) {
int n = A.size();
// 考察n-1轮
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n-1-i; ++j) { // 这一轮要考察的部分
if (A[j] > A[j+1]) { // 每次考察相邻的一对
std::swap(A[j], A[j+1]);
}
}
}
}
下面开始,是实用的排序算法。
插入排序 (Insertion Sort)
插排的原理就类似于抓扑克牌,每次摸一张牌,然后把它插入之前已经有序的牌中。
插入排序的具体做法如下:
- 从第2个元素开始(第1个元素已经有序),在已经有序的序列中从右往左走,如果当前位置元素大于待插入元素,就将其往右挪一位,直到走到数组头部或者走到第一个小于等于待插入元素的位置,将待插入元素挪到到该位置之后;
- 取出下一个元素(未排序的序列),重复上面的步骤,直到整个序列处理完。
- 插排的性能总体而言是比较好的,尤其在数组
近似有序
的时候,因为每个元素平均移动的次数将比较少。 - 虽然最坏时间复杂度是$O(n^2)$(数组完全逆序),但是最佳时间复杂度是$O(n)$(数组完全有序)。
- 在
STL
中,sort
内部的算法中在排序的后期使用了插排。
参考代码(C++):
template<typename T>
void InsertionSort(vector<T>& A) {
int n = A.size();
for (int i = 1; i < n; ++i) {
T temp = std::move(A[i]);
int j;
for (j = i; j > 0 && temp < A[j-1]; --j) {
A[j] = std::move(A[j-1]);
}
A[j] = std::move(temp);
}
}
堆排序 (Heap Sort)
基本思想:建堆,之后利用堆的性质不断取出最大/最小值,同时维护堆性。
- 高效实用的排序算法
- 建堆的平摊时间复杂度是
O(n)
,取出最值O(1)
,维护堆性O(logn)
,因此堆排序的时间复杂度是$O(n \log n)$,且无须额外空间
template<typename T>
void HeapSort(vector<T>& A) {
int n = A.size();
/**
* 第一步:将数组堆化(这里是建最大堆)
* 从第一个非叶子节点开始执行SiftDown操作
* begin_idx: 第一个非叶子节点的位置
* 如果堆顶从0开始,那么一个节点j的父节点是(j-1)/2
*/
int begin_idx = n / 2 - 1; // (n-1 - 1) / 2 = n/2 - 1
for (int i = begin_idx; i >= 0; --i) {
SiftDown(A, i, n);
}
/**
* 第二步:对堆化数据排序
*/
for (int i = n - 1; i > 0; --i) {
std::swap(A[0], A[i]); // 等价于:取出堆顶,与最后一个节点交换
SiftDown(A, 0, i); // 维持堆性,这时堆的size = i
}
}
SiftDown
是非常关键的操作:
template<typename T>
void SiftDown(vector<T>& A, int i, int n) {
/**
* 对位置i处的节点做SiftDown(最大堆)
* n: 当前堆的有效size
*/
T tmp = std::move(A[i]);
int child;
for (; 2*i+1 < n; i = child) { // 循环条件是左孩子存在
int lchild = 2*i + 1, rchild = lchild + 1;
child = lchild;
if (rchild < n && A[rchild] > A[lchild]) { // 选择左右孩子中较大的
child = rchild;
}
if (tmp < A[child]) {
A[i] = std::move(A[child]);
} else break;
}
A[i] = std::move(tmp);
}
归并排序 (Merge Sort)
基本思想:Divide & Conquer
- 把数组一分为二,分为长度大致相等的左、右两个子数组
- 分别对左、右子数组进行排序
- 左右子数组有序后,合并它们
- 处理左、右子数组时,递归地进行
归并排序的递归方程: \(T(n) = 2 T\left(\frac{n}{2}\right) + O(n)\) $T(n)$表示对整个数组进行排序的时间,$2T\left(\frac{n}{2}\right)$表示对两个子数组进行排序的时间,而$O(n)$表示合并两个子数组的时间复杂度。求解这个递归方程,得到$T(n) = O(n\log{n})$。
关于时间复杂度,也可以这么简单地理解:划分原问题为更小规模子问题的复杂度是$O(\log{n})$(其实是个递归树,而且这里是二叉树),合并已排好序的数组的复杂度是$O(n)$,因而是$O(n\log{n})$。
参考程序(C++):
首先是排序入口:
template<typename T>
void MergeSort(vector<T>& A, int start, int end) {
if (start >= end) return;
int mid = start + (end - start) / 2;
MergeSort(A, start, mid);
MergeSort(A, mid+1, end);
Merge(A, start, mid, end);
}
然后是合并排序数组的操作:
template<typename T>
void Merge(vector<T>& A, int start, int mid, int end) {
vector<T> helper(end-start+1); // 临时开辟辅助数组(在外部预先申请好空间可以提高效率)
int p = start, q = mid+1, k = 0;
while (p <= mid && q <= end) {
if (A[p] < A[q]) helper[k++] = A[p++];
else helper[k++] = A[q++];
}
while (p <= mid) helper[k++] = A[p++];
while (q <= end) helper[k++] = A[q++];
std::copy(helper.begin(), helper.end(), A.begin()+start); // 拷贝回原数组(大数据比快排慢的主要原因)
}
快速排序 (Quick Sort)
我喜欢把快排称为「划分排序」(Partition Sort),因为这是其工作原理所在。至于为什么叫「快排」,顾名思义,因为快嘛——它是目前在实际应用中表现最好的算法之一(虽然平均意义上的时间复杂度依然是$O(n \log n)$)。
快排和归并排序可以说是一对「姐妹算法」,体现了正向思维和逆向思维的联系。快排的基本思想是先让数组整体有序,再对局部进行递归操作。而归并排序是先局部有序,然后通过合并有序的局部来构造有序的整体。
总体步骤:
- 如果数组只有1个元素,不做任何操作,返回
- 选取一个主元(pivot),对原数组进行划分(partition)。通常的做法是以pivot为分界点将数组分为两部分,使得左边的元素都小于pivot,右边的元素都不小于pivot。
- 分别对左、右两部分进行排序
可以在HackerRank练习,那里的教程写得比较详细。先练习Partition
的实现,再练习整个排序的递归实现。后面还有复杂度的讲解。基本上认真做一遍,就能很好地理解快排了~
关于快排的复杂度分析,这里就不搬运了,CLRS上有详细的推导。
通常Partition
的实现是「就地」(in-place)进行的,因为这样可以避免额外的空间开销,从而提高效率。Partition
的写法不止一种,往往Pivot的选取不同,Partition的方式也不同。这里给出一种被称为Lomuto Partitioning的划分方法,它选取子数组的最后一个元素作为Pivot,然后用一个变量fstLarger
记录第一个比Pivot大的元素位置,它初始化为第一个元素的下标。当往右遍历子数组时,如果遇到了比Pivot小的元素,就将该元素与fstLarger
处的元素交换,之后fstLarger
往右移一位。还是看图比较直观:
template<typename T>
int Partition(vector<T>& A, int low, int high) {
int pivot = A[high];
int fstLargerPos = low;
for (int i = low; i < high; ++i) {
if (A[i] < pivot) {
swap(A[i], A[fstLargerPos]);
fstLargerPos++;
}
}
std::swap(A[high], A[fstLargerPos]);
return fstLargerPos;
}
最后返回Pivot所在的位置,Pivot直到整个排序结束都不会改变了,它已经处于「正确」的位置上。这个返回值也是划分的依据,它将决定左、右子数组的长度。于是,快排主体的递归写法如下(还是很简洁的~):
template<typename T>
void QuickSort(vector<T>& A, int low, int high) {
if (low >= high) return;
int mid = Partition(A, low, high);
QuickSort(A, low, mid-1);
QuickSort(A, mid+1, high);
}