归并排序
归并排序(merge - sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用.将已有的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,成为二路归并.
核心步骤讲解
归并排序的核心步骤如下:
可以看出,这算法的核心逻辑就是类似小学语文学文章的一种结构的"总-分-总".
让我们来具体剖析一下,来看看它的思路:
拆分过程:以10 6 7 1这一组为例来看一下拆分过程(核心:使用start, end, mid分别表示开头结尾和中间) :
合并过程:让我么以6,10/1,7这一组为例,来看一下合并过程:最主要的地方就在于传入两组要合并的组,然后创建一个新的数组tmpArr,存放要合并的两个组元素,并将tmpArr中的内容放在源数组中对应位置.
下面是代码:
public class MergeSort {
public static void mergeSort(int[] arr) {
mergeSortFun(arr, 0, arr.length - 1);
}
public static void mergeSortFun(int[] arr, int start, int end) {
//当start和end重合之后,结束递归
if(start >= end) {
return;
}
//找到要切割的位置
int mid = (start + end) / 2;
//左分支
mergeSortFun(arr, start, mid);
//右分支
mergeSortFun(arr, mid + 1, end);
//合并内容
merge(arr, start, mid, end);
}
public static void merge(int[] arr, int left, int mid, int right) {
//为了好理解,这里重新用s1,s2,e1,e2表示
int s1 = left, e1 = mid, s2 = mid + 1, e2 = right;
//定义一个新的数组,用来返回排序好的部分
int[] tmpArr = new int[right - left + 1];
//用k表示下标(在新创建的数组中的位置)
int k = 0;
while(s1 <= e1 && s2 <= e2) {
if(arr[s1] <= arr[s2]) {
tmpArr[k++] = arr[s1++];
} else {
tmpArr[k++] = arr[s2++];
}
}
//用来存放剩余的部分
while(s1 <= e1) {
tmpArr[k++] = arr[s1++];
}
while(s2 <= e2) {
tmpArr[k++] = arr[s2++];
}
//将排序好的数组,放到原来的数组中
for(int i = 0; i < tmpArr.length; i++) {
arr[i + left] = tmpArr[i];
}
}
public static void main(String[] args) {
int[] arr = {10, 6, 7, 1, 3, 9, 4, 2};
mergeSort(arr);
for(int x : arr) {
System.out.print(x + " ");
}
}
}
归并排序总结
1.归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题.
2.时间复杂度:O(N * logN)
3.空间复杂度:O(N)
4.稳定度:稳定.
海量数据的排序问题
外部排序:排序过程中需要在磁盘等外部存储进行的排序.
eg:内存只有1G,需要排序的数据有100G
因为内存中因为无法把所有数据全部放下,所以需要外部排序.而归并排序是最常用的外部排序.
1.先把文件切分成200份,每个512M
2.分别对512M内容进行排序,因为每个内存都放得下,所以任意排序都可以
3.进行二路归并,同时对200份有序文件进行归并过程,最终结果就有序了.
自然归并排序
自然归并排序是归并排序的一种变体,其主要特点是利用输入数据的初始有序性.自然归并排序的思想是先找到已经有序的子序列,然后合并这些子序列,直至整个数组有序.
核心步骤讲解
1.查找有序子序列:从数组的起始位置开始,找到第一个有序子序列(递增或递减).这可以通过遍历数组来实现.
2.合并有序子序列:将找到的有序子序列进行合并,在合并的过程中,继续查找下一个有序子序列,直到整个数组有序.
3.重复步骤1和2:重复执行步骤1和2,直到整个数组完全有序.
以下是大致过程:
相对于之前的归并排序,这里就不是单纯的向下递归的过程,而是一个寻找子序列的过程,而在归并的过程中,是基本与之前的一致的.所以这里只需要分析一下寻找子序列的过程即可:
重点:标记的end是上一组的下一个,然后循环时不断标记end,控制为两两一组,进行合并.反复执行上述过程,就可以直接完成.
可能讲的会有点不清楚,请看代码:
import java.util.Arrays;
public class NaturalMergeSort {
public static void main(String[] args) {
int[] array = {10, 6, 7, 1, 3, 9, 4, 2};
naturalMergeSort(array);
for(int x : array) {
System.out.print(x + " ");
}
}
public static void naturalMergeSort(int[] array) {
int n = array.length;
int[] tempArray = new int[n];
int l = -1, m, r;
//外部循环,直到不能发现更多的子数组
while(l != 0) {
l = 0;
//内部循环,以寻找并合并有序子数组
while (l < n) {
m = findNextSortedSubarray(array, l, n, tempArray);
//当m 与 n重合时,表明已经找到尾了,退出循环(里和外)
if (m == n) {
break;
}
r = findNextSortedSubarray(array, m, n, tempArray);
merge(array, l, m, r, tempArray);
l = r;
}
}
}
//查找下一个有序子数组的方法(返回的是结束位置)
private static int findNextSortedSubarray(int[] array, int start, int n, int[] tempArray) {
int end = start + 1;
while (end < n && array[end - 1] <= array[end]) {
end++;
}
return end;
}
//二路归并
private static void merge(int[] array, int l, int m, int r, int[] tempArray) {
int i = l, j = m, k = 0;
while (i < m && j < r) {
if (array[i] <= array[j]) {
tempArray[k++] = array[i++];
} else {
tempArray[k++] = array[j++];
}
}
while (i < m) {
tempArray[k++] = array[i++];
}
while (j < r) {
tempArray[k++] = array[j++];
}
System.arraycopy(tempArray, 0, array, l, k);
}
}
自然归并排序总结
1.这玩意的思路相比于其它排序其实特别恶心,在生产环境中非常不建议使用,你的项目组成员可能会骂街,说你小子装什么逼??(除非是这种情况:就比如你的数据结构老师不知道是为啥心血来潮让你讲这个,整一个反转课堂啥的,那你也没办法~~)
2.时间复杂度:遍历了一次:O(n)
3.空间复杂度:O(n)
