八大排序算法——快速排序

kyuskoj · 发表于 2021-12-23 08:22

配套源码地址：《八大排序》源码，提取码：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 = (int) (Math.random() * 100000);
      }

      Date start = new Date();
      //过长，先注释掉逐步打印
      //BubbleSort.sort(costArray);
      Date end = new Date();
      System.out.println(&#34;耗时：&#34;+(end.getTime()-start.getTime())/1000+&#34;s&#34;);
}
}该段代码内容主要有两个功能：

调用不同的排序算法进行测试

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

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进，相比冒泡排序，每次的交换都是跳跃式的。
基本思想

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

代码实现

思路如下：

首先在这个序列中找一个数作为基准数，为了方便可以取第一个数。

遍历数组，将小于基准数的放置于基准数左边，大于基准数的放置于基准数右边。此处可用双指针实现。

此时基准值把数组分为了两半，基准值算是已归位（找到排序后的位置）。

利用递归算法，对分治后的子数组进行排序。

public class QuickSort {
public static void sort(int[] array) {
      System.out.println(&#34;快速排序开始---------&#34;);
      mainSort(array, 0, array.length - 1);
}

private static void mainSort(int <span class="n">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<j) {
            i++;
         }
         //交换
         int temp = array[j];
         array[j] = array;
         array = temp;
      }
      //最后将基准为与i和j相等位置的数字交换
      array[left] = array;
      array = 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）：我们目前是拿第一个数作为基准数，对于部分有序序列，会浪费循环，可以用三数取中法优化，感性的小伙伴可自行了解。
优化二
快速排序对于长序列非常快，但对于短序列不如插入排序。可以综合使用。

最后，如果文章对你有帮助。
记得给文章点个赞呀！
也给 @程序员一条点个关注！

		自动登录	找回密码
密码			立即注册

八大排序算法——快速排序

本帖子中包含更多资源