首次认识排序算法还是在大二的《数据结构》课程上听老师介绍的。那时候颇不理解,不仅不理解这些排序算法,更不理解为什么机械学院要开设《数据结构》这门课程。后来在大四以及此后的硕士项目过程中,我真有用到排序算法,不过当时图方便,而且数据量不大,我使用的冒泡排序(编码简单)。之后与排序算法结缘,是准备秋招。为了考试,为了项目,为了秋招,回顾这几次与排序算法的近距离接触,我并没有真正理解各类排序算法的原理。
求解数组中的逆序对
这两天看到一道题目:求解数组中的逆序对。
难度标记为“困难”,一上来就被吓住了,一定很难,除了暴力解决,多半是用些什么炫酷的算法,动态规划?分治算法?回溯……脑海里过了几部电影后,经过bobo点播,竟然是用归并排序!而且只在归并排序源代码里增加一行代码即可!
归并排序算法
归并排序采用分治策略,将一个待排序数组一分为二,把每部分递归使用归并排序,再将两部分合并成一个序列,这也是“归并” 由来,也是其时间复杂度为O(nlogn)的原因。合并的时候需要额外申请空间,这是归并排序空间复杂度为O(n)的原因。直接上归并排序的代码:
#ifndef _MERGE_SORT_
#define _MERGE_SORT_
// 归并排序:额外使用O(n)的空间, 时间复杂度O(nlogn)
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r){
T *aux = new T[r - l + 1];
for (int i = l; i <= r; i++){
aux[i - l] = arr[i];
}
int i = l, j = mid + 1;
for (int k = l; k <= r; k++){
if (i > mid){
arr[k] = aux[j - l];
j++;
}
else if (j > r){
arr[k] = aux[i - l];
i++;
}
else if (aux[i - l] < aux[j - l]){
arr[k] = aux[i - l];
i++;
}
else{
arr[k] = aux[j - l];
j++;
}
}
delete[] aux;
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
if (l >= r){
return;
}
int mid = (l + r) / 2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid + 1, r);
if (arr[mid] > arr[mid + 1]){
__merge(arr, l, mid, r);
}
}
template<typename T>
void MergeSort(T arr[], int N){
__mergeSort(arr, 0, N - 1);
}
#endif // _MERGE_SORT_
使用归并排序求解逆序对
那么如何解上面那个逆序对的问题呢?试想,合并之前左右两个子序列已经有序,合并时候的关键在于比较左右两个序列的元素大小。以上述代码中的变量为例:
[4,7,9,10]为左边有序子序列,[1,3,5,6]为右边有序子序列,现在要合并为一个有序序列。l和r分别代表左右边界。按照上述代码的__merge中的逻辑,现在考察arr[i]和arr[j],显然9>3,所以构成了一个逆序对。别着急,因为左边序列是有序的了,即i后面的元素比arr[i]大,肯定也和arr[j]构成逆序对。当然上图例子只有10。所以逆序对的数量可以直接增加(mid-i+1)。声明一个全局的变量times,在__merge函数的arr[i-l]>arr[j-l]的逻辑分支里加上下面一行代码,最后归并排序完成后返回times即可:
else{
nums[k] = aux[j - l];
times = times + mid - i + 1;// 增加这一行代码即可
j++;
}
O(n2)的排序算法
归并排序时间复杂度为O(nlogn),还有些时间复杂度为O(n2)的排序算法,比如冒泡排序、选择排序、插入排序和希尔排序)。一提到O(n2),就感觉这类算法很low,不高级,不优雅。
其实不是。我前几次接触排序算法,都是从时间复杂度为O(n2)的排序算法起步的。bobo总结得很好,为什么要学习O(n2)的排序算法:
一些O(n2)的排序算法,性能甚至好过O(nlogn)的排序算法,比如希尔排序,插入排序。插入排序对于少量数据排序的高性能,甚至可以作为O(nlogn)的排序算法优化的一部分,改进O(nlogn)的排序算法的时间性能。比如,判断到某个子序列可能只有十几个元素,那么可以直接使用插入排序。
温故而知新,很多基础知识,经典算法,前人早已总结完毕。这些东西一定是有道理的,如果觉得它没用,那一定是还没感悟到其中的道理。
不限于此,很多人生哲学道理,古人早已总结完毕。清代乾隆年间,纪晓岚主编《四库全书》。他曾经说过:“世间的道理与事情,都在古人的书中说尽,现在如再著述,仍然超不过古人的范围,又何必再多著述。”所以,纪晓岚一生之中,从不著书,只是编书——整理前人的典籍,将中国文化作系统的分类,以便于以后的学者们学习。