接下来准备学习一下归并排序
去别的blog看了一段，很多博客概括介绍归并的时候是这样子的：
基本理念:分治思想（divide and conquer）
主要用处:将两个(或者多个 两个就称为<u>二路归并</u>)已经排好序的序列合并排序
时间复杂度： O(n logn)
可以看出来这也是我们遇到的第三个n logn时间复杂度的排序了
归并排序
基本思想：
以二路归并为例子
其实说白了只有一句话
先分割再合并
- 给定一个数组array[n]
- 选取一个中间位置mid吧(只是一个标志,不要太care,注意inside，not outside) 需要排序的开始位置start，需要排序的结束位置end
需要有end和start的原因是因为，万一我们只需要对array的[start,end]进行排序呢？
plus 至于是左闭右开还是都是闭，看你的end的取值咯，只要对应就好
另外(** start>mid>end**)
- 那么我们是不是就需要将array[start,mid]
姑且称之为array1和array[mid+1,end]姑且称之为array2两个数组排序后进行合并？ - 那么
3.提到的那两个数组是不是按照刚才说的是将其排好序后才能merge(归并)在一起？那么问题来了，这两个数组要排序？ - 那么这个两个数组（array1和array2）自己的问题就是需要排序
那么是不是还要对于每个数组按照刚才2.的步骤来一遍？
递归 boom 问题解决了，那么还有一个问题，众所周知，递归除了将步骤跳到前面做重复的工作(代码中就是调用相同的函数) 还需要有一个临界值，也就是什么时候表示我们不递归了？ 直到递归到后面拆分的array数组的元素只有一个，是不是就开始回溯了？
over 大致思路就是这样
下面看示例图：
归并排序示例.png
关注细节：
-
如何将两个已经排好序的数组(比如是
array1和array2)合并成为一个数组呢？
思路很简单，反正二者都是已经排好序的了，先确定一个临时数组temp
(确保足够长，要满足 temp.length >= array1.length + array2.length)
然后就一个一个比较(假设是从小到大排序)，假设i，j=0；
那么就是
①如果array1[i]>array2[j] 那么temp[k]=array1[i]; k++; i++; 否则temp[k] = array2[j]; k++; j++;
②然后接下来接着做①直到其中一个数组已经走到底了，那么就只需要
那么接下来就是将没走到底的全接了temp后面
package mergeSort;
import java.util.Arrays;
/**
* @author mengf
* 将两个有序的数组合并为一个有序的数组的示例
* 默认两个数组的排序从小到大
*/
public class Demo1 {
public static void main(String[] args) {
int[] array = merge(new int[] { 1, 3, 5, 7, 11 },
new int[] { 2, 4, 6, 8, 10, 12, 14, 15 });
System.out.println(Arrays.toString(array));
}
public static int[] merge(int[] array1, int[] array2) {
// i是array1的索引
// j是array2的索引
// k是新数组result的索引
int i = 0, j = 0, k = 0;
int length1 = array1.length;
int length2 = array2.length;
int[] result = new int[length1 + length2];
while (i < length1 && j < length2) {
// if (array1[i]<array2[j]) {
// result[k] = array1[i];
// i++;
// }else {
// result[k] = array2[j];
// j++;
// }
// k++;
// 上面注释掉的这段代码可以用一下一句来表示
// 第一次发现三目运算符是如此的清爽
result[k++] = array1[i] < array2[j] ? array1[i++] : array2[j++];
}
if (i < length1) {
while (i < length1) {
result[k++] = array1[i++];
}
} else if (j < length2) {
while (j < length2) {
result[k++] = array2[j++];
}
}
return result;
}
}
然后解决了思路的拆分问题(递归)，也解决了将拼起来的两个有序数组merge起来的问题，那么这个算法应该是没有问题的了！
接下来我们开始上代码！
package mergeSort;
import java.util.Arrays;
public class MergeSort {
/**
* 默认size是10 可以自行设定 扩容 一般设置为size是需要排序的数组的长度就好了
*/
private static int temp[] = new int[10];
public static void setBufferSize(int length) {
temp = new int[length];
}
public static void main(String[] args) {
int array[] = new int[]{
10,9,8,7,6,5,4,3,2,1,0,-1,-10,-13,24
};
setBufferSize(array.length);
//闭区间 所以length-1
mergeSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
}
public static void mergeSort(int[] array, int start, int end) {
if (start == end) {
return ;
}
int mid = start + (end - start) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, mid + 1, end);
return;
}
private static void merge(int[] array,int start1,int end1,int start2,int end2) {
int i = start1;
int j = start2;
int k = 0;
while (i <= end1 && j <= end2) {
temp[k++] = array[i] < array[j] ? array[i++]:array[j++];
}
while (i <= end1) {
temp[k++] = array[i++];
}
while (j <= end2) {
temp[k++] = array[j++];
}
//将temp的复制到对应的[start1,end1] [start2,end2]
k = 0 ;
for(int index = start1 ; index <= end1 ; index++){
array[index] = temp[k++];
}
for(int index = start2 ; index <= end2 ; index++){
array[index] = temp[k++];
}
}
}
测试的是成功的，但是不知道是不是最优的做法，我只是按照思路自行写了一遍，大家可以参考其他网站的写法，毕竟这些常见排序算法的讲解到处都是！
如果有更好的更优雅的书写方式，可以指出来，sharing is important！
我还是想吐槽啊，简书为啥不能可以修改文字的颜色，不需要太多颜色，就红色我也满足了啊！！！我也不是想搞得花哨，只是觉得黑白还是太单调了，粗体有的时候也不能满足我想要强调的心情。
网友评论