📚 八大排序算法合集——两万字，8张动图，450行代码。大厂面试必备。

🌲 配套源码地址：《八大排序》源码，提取码：5ehp

哈喽，大家好，我是一条~

今天给大家带来《糊涂算法》专栏的第二期内容——排序算法的讲解。相信无论是初学者学习还是大厂面试，都少不了排序算法这关，即使没学过算法，对冒泡排序也不会陌生。

今天，一条就带大家彻底跨过**「排序算法」这道坎，保姆级教程建议收藏**。⭐️

准备

古语云：“兵马未动，粮草先行”。想跟着一条一块把「排序算法」弄明白的,建议先准备好以下代码模板。

📢 观看本教程需知道基本循环语法、两数交换、双指针等前置知识。

📚 建议先看完代码和逐步分析后再尝试自己写。

• 新建一个Java工程,本文全篇也基于Java语言实现代码。
• 建立如下目录结构

• 在MainTest测试类中编写测试模板。

/** * 测试类 * Author：一条 * Date：2021/09/23 */
public class MainTest {
    public static void main(String[] args) {
        //待排序序列
        int[] array={6,10,4,5,2,8};
        //调用不同排序算法
				// BubbleSort.sort(array);

        // 创建有100000个随机数据的数组
        int[] costArray=new int[100000];
        for (int i = 0; i < 100000; i++) {
            // 生成一个[0,100000) 的一个数
            costArray[i] = (int) (Math.random() * 100000);
        }

        Date start = new Date();
        //过长，先注释掉逐步打印
				//BubbleSort.sort(costArray);
        Date end = new Date();
        System.out.println("耗时："+(end.getTime()-start.getTime())/1000+"s");
    }
}

该段代码内容主要有两个功能：

• 调用不同的排序算法进行测试
• 测试不同排序算法将10w个数排好序需要的时间。更加具象的理解时间复杂度的不同

归并排序

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，采用经典的分治（divide-and-conquer）策略。

将乱序序列不断的分成一半，排好序再拼回去，用递归实现。

难点在于如何归并两个排好序的数组？

我们可以开辟一个临时数组，使用快慢指针来辅助我们的归并。

虽然需要额外空间的来完成这个排序。但是现在计算机的内存都比较大，时间的效率要比空间的效率重要的多。

所以空间换时间也是优化算法时的一个方向。

动图讲解

代码实现

public class MergeSort {
    public static void sort(int[] array){
        divide(array,0,array.length-1);
    }

    private static int[] divide(int[] array, int left, int right) {
        int mid = (left+right)/2;
        if(left<right){
            divide(array,left,mid);
            divide(array,mid+1,right);
            //左右归并
            merge(array,left,mid,right);
        }
        System.out.println(Arrays.toString(array));
        return array;
    }

    public static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right-left+1];
        int i= left;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=right){
            if(array[i]<array[j]){
                temp[k++] = array[i++];
            }else{
                temp[k++] = array[j++];
            }
        }
        // 把左边剩余的数移入数组
        while(i<=mid){
            temp[k++] = array[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=right){
            temp[k++] = array[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            array[x+left] = temp[x];
        }
    }
}

输出结果

耗时测试

点击查看更多排序算法