《糊涂算法》之八大排序

文章8 |   阅读 400 |   点赞0

《糊涂算法》之八大排序——快速排序

x33g5p2x  于10个月前 转载在 其他  
字(2.1k)|赞(0)|评价(0)|浏览(77)

📚 八大排序算法合集——两万字,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个数排好序需要的时间。更加具象的理解时间复杂度的不同

快速排序

快速排序(Quicksort)是对冒泡排序的一种改进,相比冒泡排序,每次的交换都是跳跃式的。

基本思想

将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

体现出分治的思想。

动图讲解

代码实现

思路如下:

  • 首先在这个序列中找一个数作为基准数,为了方便可以取第一个数。
  • 遍历数组,将小于基准数的放置于基准数左边,大于基准数的放置于基准数右边。此处可用双指针实现。
  • 此时基准值把数组分为了两半,基准值算是已归位(找到排序后的位置)
  • 利用递归算法,对分治后的子数组进行排序。
public class QuickSort {
    public static void sort(int[] array) {
        System.out.println("快速排序开始---------");
        mainSort(array, 0, array.length - 1);
    }

    private static void mainSort(int[] array, int left, int right) {
        if(left > right) {
            return;
        }
        //双指针
        int i=left;
        int j=right;
        //base就是基准数
        int base = array[left];
        //左边小于基准,右边大于基准
        while (i<j) {
            //先看右边,依次往左递减
            while (base<=array[j]&&i<j) {
                j--;
            }
            //再看左边,依次往右递增
            while (base>=array[i]&&i<j) {
                i++;
            }
            //交换
            int temp = array[j];
            array[j] = array[i];
            array[i] = temp;
        }
        //最后将基准为与i和j相等位置的数字交换
        array[left] = array[i];
        array[i] = base;
        System.out.println(Arrays.toString(array));
        //递归调用左半数组
        mainSort(array, left, j-1);
        //递归调用右半数组
        mainSort(array, j+1, right);
    }
}

输出结果

**

**

逐步分析

  • 6作为基准数,利用左右指针使左边的数<6,右边的数>6
  • 对左右两边递归,即左边用5作为基准数继续比较。
  • 直到left > right结束递归。

耗时测试

快速排序为什么这么快?

算法优化

优化一

三数取中(median-of-three):我们目前是拿第一个数作为基准数,对于部分有序序列,会浪费循环,可以用三数取中法优化,感性的小伙伴可自行了解。

优化二

快速排序对于长序列非常快,但对于短序列不如插入排序。可以综合使用。

点击查看更多排序算法

上一篇:归并排序
下一篇:希尔排序

相关文章