算法入门教程-归并排序

关于上节的快速排序,我们知道了它的本质是对冒泡排序的优化,通过时间的执行效率的测试,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

可以从图中的测试结果来看,归并排序的执行效率是蛮高的,那么关于它的学习就到这里了....