前言
承接上文基础排序算法—冒泡,插入,选择,相比之下,归并排序和快速排序更为高效,时间复杂度均为O(nlogn),相比简单排序的O(n^2)好了很多,下面介绍一下这两种算法的思路,实现和主要指标.主要思路来自<数据结构与算法之美>
正文
归并排序
主要思路
在归并排序采用分冶的思想,使用递归实现.描述如下
- 开始
归并排序- 如果数组元素小于两个,无需排序,结束
- 否则需要排序,
归并排序数组左侧,归并排序数组右侧,按序合并左右侧
采用的是自顶至下的思路,例如[1,5,3,7,4,6],左侧为[1,5,3],右侧为[7,4,6],左侧归并排序后为[1,3,5],右侧归并排序后为[4,6,7],按序合并后[1,3,4,5,6,7]这里的关键是只在主流程思考,不要试图代入到递归的子流程中,引用一句: "编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤" ,递归公式如下
merge_sort(arr[low,high))=merge_sort(arr[low,mid))+merge_sort(arr[mid,high)
merge(arr,low,mid,high)
java实现如下
public void sort(Comparable[] arr) {
if (arr.length <= 1) {
return;
}
mergeSort(arr, 0, arr.length);
}
private void mergeSort(Comparable[] arr, int low, int high) {
if (high - low <= 1) {
return;
}
int mid = low + (high - low) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid, high);
merge(arr, low, mid, high);
}
private void merge(Comparable[] arr, int low, int mid, int high) {
Comparable[] left = Arrays.copyOfRange(arr, low, mid);
Comparable[] right = Arrays.copyOfRange(arr, mid, high);
int l = 0, r = 0;
int pos = low;
for (int i = 0; i < (high - low); i++) {
Comparable next = null;
if (l == left.length) {
next = right[r++];
} else if (r == right.length) {
next = left[l++];
} else if (left[l].compareTo(right[r]) <= 0) {
next = left[l++];
} else {
next = right[r++];
}
arr[pos++] = next;
}
}
merge方法将两个有序数组合并为一个有序数组,最后的判断逻辑有一点繁琐,王争文中有提到可以用哨兵简化,也许是我使用方法不对,使用哨兵后感觉反而更麻烦了,最终采用了繁琐的写法.
时间复杂度
对于递归实现,分析时间复杂度时也要推导出公式,对左右数组归并排序数量级都是一半,因此为T(n/2),merge()方法是对两个数组按序排列,时间复杂度为O(n), 当n=1时,时间复杂度为常数,由此可得
T(n) = T(n/2) + T(n/2) + n = 2*T(n/2) + n
T(1) = C
下面对公式进行代入
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n
= 2*(2*(2*T(n/8)+n/4) + n/2) + n
= 2^3*T(n/2^3) + 3n
= 2^k*T(n/2^k) + kn
当T(n/2^k) == T(1) 即n/2^k == 1 可得k=logn(底数为2),代入到T(n)中得
T(n) = n*C +logn*n
所以归并排序的时间复杂度为O(nlogn),根据归并排序的思路,它的算法复杂度不受数组顺序影响.
是原地排序吗?
不是,merge过程中需要对左右子数组复制进行归并,尽管递归过程中会不断申请额外空间,但是同一时间申请的最大额外空间为O(n),空间复杂度为O(n)
稳定吗?
归并排序数组元素的移动只发生在merge阶段,当左右相等时,我们会优先选择左侧(left[l].compareTo(right[r]) <= 0),因此是稳定的
快速排序
主要思路
快排通过partition(划分)将数组划分为中间值的左侧和右侧.保证左侧<=中间值<右侧,再对左侧右侧(不包含中间值所在下标)递归处理,实现排序.
快排的递归伪代码如下
quick_sort(arr,low,high)={
if (high-low<=1) return
mid = partition(arr,low,high)
quick_sort(arr,low,mid)
quick_sort(arr,mid+1,high)
}
java代码如下
public void sort(Comparable[] arr) {
if (arr.length <= 1) {
return;
}
quickSort(arr, 0, arr.length);
}
private void quickSort(Comparable[] arr, int low, int high) {
if (high - low <= 1) {
return;
}
int mid = partition(arr, low, high);
quickSort(arr, low, mid);
quickSort(arr, mid + 1, high);
}
private int partition(Comparable[] arr, int low, int high) {
Comparable cmpValue = arr[high - 1];
int i = low;
for (int j = low; j < high - 1; j++) {
if (arr[j].compareTo(cmpValue) <= 0) {
swap(arr, i++, j);
}
}
swap(arr, i, high - 1);
return i;
}
快速排序的核心在于partition(划分),这里有两种方式:
- 选定一个中间值(比如第一个元素/最后一个元素),左右各选一个锚点,将左侧>中间值的与右侧<=中间值的做交换,直到左右锚点相遇/左右锚点反序/任意锚点到达边界,这样左侧都小于等于中间值,右侧都大于中间值
- 类似于选择排序,将数组在逻辑上划分为左侧的已排序部分和右侧的未排序部分,初始时已排序部分为空.依次将小于中间值的数字插入到已排序部分
时间复杂度
和归并排序类似,时间复杂度的递推公式为
T(n) = n + T(n/2) + T(n/2) = n + 2*T(n/2)
T(1) = C
推到过程同上,时间复杂度也是O(nlogn)
是原地排序吗?
是的,快速排序过程中不占用额外空间
稳定吗?
不稳定,从上文基础排序算法—冒泡,插入,选择中我们得知选择排序是不稳定的,快速排序的划分过程采用的事选择排序的思想,因此也是不稳定的
归并排序 vs 快速排序
- 两种排序的时间复杂度相同,O(nlogn),都很优秀
- 归并排序空间复杂度为O(n),快速排序的空间复杂度为O(1)
- 归并排序是稳定的,快速排序是不稳定的
- 两种排序的使用都用了递归
- 递归的使用方法上,归并排序是自底至上,先划分执行子任务,子任务完成后,再归并.快速排序是自顶至下,先进行partition,再划分执行子任务.
从实际使用来说,快速排序的效率更高,一般的库实现也会优先选择它.
源码地址github
