算法与数据结构(3)—— 归并排序
程序员文章站
2022-06-04 17:15:07
...
前言:
前面介绍的几个时间复杂度为 O(n^2)的几个排序算法(选择、插入、冒泡、希尔排序),其中尤为需要注意的是插入排序,在近乎有序的测试用例条件下,此算法的效率会高于O(n*logn)的排序算法,几乎是O(n),
一、O(n*logn) 和 O(n^2)算法比较:
O(n*logn)可以在1s内轻松处理百万数量级的数据,当n=10^5时,其实这个测试数量也不是很大,O(n*logn)比O(n^2)快6000倍。
二、归并排序:
(1)整体思路:
- 将数组对半划分,分别对左右数组进行排序。
- 继续划分左边,右边的数组,然后继续划分.....直到划到一个只剩下一个元素,开始对每一个小部分进行排序
- 小部分排序完,进行向上归并,就是与旁边的小组进行归并(此时每个小组都是有序的,层层往上归并)
(2)算法复杂度
n个元素每次分两组,log以2为底n,就相当于一个树的高度。每次归并处理都可以看做O(n)的时间复杂度,整个过程O(nlogn)
(3) 代码实现
- i,j分别指向当前正在考虑的元素,
- k最终归并,i和j比较后放入的位置,即表示下一个需要放的位置
- 一个前闭后闭的数组,明确边界的问题
- 复制数组时始终要记住有一个L的偏移量
private static void merge(Comparable[] arr, int l, int mid, int r) {
//Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
Comparable[] aux = new Comparable[r-l+1];
for(int i = l; i <= r; i ++){
aux[i-l] = arr[i];
}
// l...mid区间和mid+1...r区间
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].compareTo(aux[j-l]) < 0){
arr[k] = aux[i-l];
i ++;
}else {
arr[k] = aux[j-l];
j ++;
}
}
}
//递归使用归并排序,对arr[l..r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r){
if(l >= r) return;
int mid = (r-l)/2 + l;
sort(arr, l, mid);
sort(arr, mid+1, r);
merge(arr, l, mid, r);
}
public static void sort(Comparable[] arr){
int n = arr.length;
sort(arr, 0, n-1);
}
(4)归并与插入比较
对于无序数组来说,归并肯定好
对于近乎有序的数组,数组越有序,插入排序的时间性能越趋近于O(n),比归并排序高效
三、归并优化
(1)优化一
所有的排序算法中都存在一种优化,就是递归到底优化。,当递归元素较少时,可以用插入排序来提高性能
- 当待排序的数组元素较少时,近乎有序的情况概率较大,此时插入排序有优势。
- 虽然插入排序的时间复杂度是O(n^2)级别,而归并排序是O(n*logn),但是别忽视这两者都依赖于常数系数n,当n较小时,插入排序是稍快于归并排序的
所以,在此优化中,在一开始判断递归到底的情况下,设定一定的值(这里设定15),剩下的数组采用插入算法进行排序。
(2)优化二
在merge中,并没有对左右两个部分进行判断在归并,而是一律归并,当左部分的最后一个值小于右部分第一个值的话,此时压根就不需要归并,真个数组都是有序的,直接跳过即可~
注意:归并必须要对logN层进行递归,只是每次发现不需要递归退出来,无法退化成O(N)的算法~
对于改进,数组中存在有序会有一定的效果,但也会阻碍(if语句本身消耗),但总体不打
四、优化后的代码
总之,就是对sort函数进行优化~
private static void sort(Comparable[] arr, int l, int r){
// 优化1,小规模用插入
if( r - l <= 15){
InsertionSortoptimize.sort(arr, l, r);
return;
}
int mid = (r-l)/2 + l;
sort(arr, l, mid);
sort(arr, mid+1, r);
// 优化2,对于已经有序不进行merger
if(arr[mid].compareTo(arr[mid+1]) > 0){
merge(arr, l, mid, r);
}
}
实验证明,确实是比较好,这种优化更加实用与几乎有序的数组排序~