关于上节的快速排序,我们知道了它的本质是对冒泡排序的优化,通过时间的执行效率的测试,10W条数据,我们发现快速排序确实比冒泡排序效率高很多,关于快速排序的算法我们不在多说了,这节我们来学习另外一种算法:归并排序,首先来介绍下什么是归并排序?
归并排序介绍
归并排序是利用经典的分治策略来实现的算法的过程,分治:将问题分成很小的问题然后递归去解决,治:治的阶段则将分的阶段的得到的结果进行合并的过程.
上述抽象的概念很难理解,我们来看张图,这样可以更加直观的理解分和治的过程,如图:
分治的思想.png
- 从图中来看我们发现在分的过程中其实所做的事情不过,其核心点是在治的过程中,结合此图大家可以好好地想象下这个过程.
接下来我们采用图解的方式来更好的理解上图中的这个过程
- 由于是我们的核心是治的阶段,假设我这里待排序的元素是[4,5,7,8] 和[1,2,3,6]也就是上图中的治的阶段.
示意图.png
简单的说一下该过程的步骤:
上图中的temp为临时数组,用来存储比较后的元素,其中i为左边[4,5,7,8]的(下标)索引,j为右边元素[1,2,3,6]的(下标)索引
- 第一步: 右边的所有元素跟左边的比较,且将较小的数暂时存放在temp中,然后让j++
- 让j++对应元素继续比较也就是(2<4)成立,将2存放在temp中,j++
- 重复上述的过程,也就是(3<4)成立,将3存放在temp中,j++
- 注意:此时我们的右边元素为6即(6<4)不成立,我们将4存放在temp中,此时j不能在+1了,我们让i+1
- 还是重复上述过程,(5<6)成立,将5存放在temp中,让i++
- 此时我们发现7>6的,我们将6存放在temp中,这样我们右边的元素也就是[1,2,3,6]全部治的过程已经完成了,左边还剩7和8了,我们直接将剩余的添加到temp即可
- 最后一步,我们将temp中元素拷贝到我们原来的数组中就可以了,也就是说最后的排序结果为[1,2,3,4,5,6,7,8]
结合图和步骤相信大多数猿友们已经理解了,接下来我们用代码来实现
代码实现
我们还是采用图中的案例来测试我们的代码,这里先说明下,我们的代码分两部分完成即分和治的过程,我们先写治的代码:
//合并的方法
/**
*
* @param arr 待排序的原始数组
* @param left 左边有序序列的初始索引
* @param middle 中间索引
* @param right 右边有序序列的初始索引
* @param temp 临时存储元素的数组
*/
public static void merge(int[] arr,int left, int middle,int right,int[] temp){
int i = left; //定义临时的变量来记录我们左边有序序列的初始索引
int j = middle +1; //定义临时的变量来记录我们右边有序序列的初始索引
int t = 0; //定义临时的变量来记录temp数组的当前索引
//步骤1:
//首先把左右两边的有序序列的元素填充到temp数组中,直到左右两边有序序列中有一边填充完毕为止
//满足该条件继续循环
while (i <= middle && j<= right){
//如果左边当前下标为i的元素小于右边有序序列下表为j的元素
//我们需要做处理
if (arr[i] <= arr[j]){
//1.1 将左边有序序列的索引为i的元素填充到temp数组中
temp[t] = arr[i];
//1.2 移动左边的索引
i ++;
//1.3 同时移动temp的索引
t ++;
}else { //这里表示需要将右边有序序列中的元素填充到temp数组中
temp[t] = arr[j];
j ++;
t ++;
}
}
//步骤2:
//将有剩余数据的一边的数据填充到temp中
//该条件成立,表示左边有序序列中元素有剩余的情况,我们需要将剩余的元素全部填充到temp数组中
while (i <= middle){
temp[t] = arr[i];
t ++;
i ++;
}
//假如剩余是右边的有序序列
while (j <= right){
temp[t] = arr[j];
t ++;
j ++;
}
//步骤3:
//将temp中的元素拷贝到原数组arr中
//这里有个小技巧,在拷贝时,不是每次都拷贝所有的
//首先我们认为t是从0开始的
t = 0;
//定义一个临时索引,且让初始化为左右有序序列的left索引
//在我们看到的那张图中,第一次合并后 tempLeft是为0的,right = 1;
//第二次是: tempLeft = 2; right = 3;
//第三次是: tempLeft = 0; right =3;
//最后一次是: tempLeft = 0; right = 7;
int tempLeft = left;
//System.out.println("tempLeft="+tempLeft+ "<------------>" +"right="+right);
while (tempLeft <= right){
arr[tempLeft] = temp[t];
t ++;
tempLeft ++;
}
}
代码注释很详细,其实代码并不多,想看的可以自己看看,我们接着来看看分的过程代码:
//分+合并的方法
/**
*
* @param arr 待排序的数组
* @param left 左边有序序列的下标
* @param right 右边有序序列的下标
* @param temp 临时的数组
*/
public static void mergeSort(int[] arr, int left, int right, int[] temp){
//只要满足这个条件
if (left < right){
int mid = (left + right) /2; //中间索引的计算过程
//向左递归分解
mergeSort(arr,left,mid,temp);
//向右递归分解
//mid +1 表示: 右边的第一个
mergeSort(arr,mid +1,right,temp);
//合并
merge(arr,left,mid,right,temp);
}
}
采用的递归去处理,我们最后来测试一把,测试代码如下:
/**
* 算法学习-归并排序
*/
public class MergeSort {
public static void main(String[] args) {
int [] arr = {8,4,5,7,1,3,6,2};
int [] temp = new int[arr.length];
mergeSort(arr,0,arr.length -1,temp);
System.out.println("归并排序后的结果为:");
System.out.println(Arrays.toString(arr));
测试结果:
测试结果.png
从测试结果来看,我们完成了排序,最后一点我们来测试一把排序10w数据的执行时间效率,代码如下:
//归并排序的时间复杂度测试
int [] arr = new int[10000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random() * 10000000); //随机生成[0,100000)的数
}
Date date1 = new Date();
SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format = dateFormat.format(date1);
System.out.println("排序前的时间为:"+format);
//进行排序
int [] temp = new int[arr.length];
mergeSort(arr,0,arr.length -1,temp);
Date date2 = new Date();
SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String format2 = dateFormat.format(date2);
System.out.println("排序后的时间为:"+format2);
执行结果如下:
执行时间.png
可以从图中的测试结果来看,归并排序的执行效率是蛮高的,那么关于它的学习就到这里了....
