快速排序法

· 2021/7/18 20:54:37 · 次浏览

快速排序的核心思想就是在数组中找一个元素作为临界点，大于临界点就放在右边，小于临界点就放在左边，然后再递归调用该方法，对临界点左边的元素和右边的元素进行重复操作，这样就可以使得呈现从小到大的排序。

快速排序——第一版

使用数组的第一个元素作为临界值，所以arr[limit]表示第一个元素，使用指针 i 来遍历数组，并在使用一个 j 来指向小于等于临界值的元素，故让 j 指向第一个元素。

运行时（结合下面的图示一起理解会更好点）：

1、 i 自增，并进行判断

  • 如果 arr[i] 大于arr[limit]，则不进行操作，因为这些值本来就是大于arr[limit]的；
  • 若 arr[i] 小于arr[limit]，则让 j 加一，并且让 arr[i]、arr[j] 交换位置，使得 j 指向的仍是小于等于arr[limit]的元素。

2、重复第一步骤直到 i > arr.length-1

3、最后让 arr[j] 与 arr[limit] 交换。这样就使得 j 左边的全是小于等于自己的，右边的全是大于自己的，然后递归调用将左边的和右边的数组段排序。

例题图示

初始状态：

 不断运行，执行第一步，这里因为直到 arr[i] == 1 都是大于arr[j]的，所以只执行 i++ ，所以这里演示 arr[i] == 1 的操作图解。

执行 j++，因为从 j 到 i 的所有元素都是大于limit的，所以如果 arr[j]、arr[i]交换位置，则可以使arr[j]仍然小于等于arr[limit]，而 j 右边的所有元素仍然大于arr[limit]

 以此类推，你可以先演算一遍，有助于理解快速排序，第一阶段排序完之后的结果我放在下图。

 

 

最后将 j 返回，返回之后才能直到下一段要排序的为 arr[0... j-1] 和 arr[j+1...arr.length-1]。

 代码实现

import java.util.Random;

/**
 * @Description：快速排序版本一
 * @Author: hour
 * @DATE: 2021/7/16 16:31
 * @PROJECT_NAME: quickSort
 */
public class QuickSort01 {

    public <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length-1);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int start, int end) {
        /* 设置跳出条件 */
        if (start >= end) { return ;}

        int mid = partition(arr, start, end);
        sort(arr, start, mid-1);
        sort(arr, mid+1, end);
    }

     /**
     * 快速交换的核心代码部分：
     *          1、 使用i遍历数组并进行判断
     *                  如果arr[i]大于arr[start]（第一个元素就是临界值），则继续执行；
     *                  若arr[i]小于arr[start]，则让j++，并且交换两个的值
     *          2、 循环结束，交换arr[j] 和 arr[start]（即临界值）
     *          3、 返回临界值所在位置下标，作为分片临界
     * @return
     */
    private <E extends Comparable<E>> int partition(E[] arr, int start, int end) {
        int i = start + 1;
        int j = start;

        for (;i <= end;i++) {
            if (arr[i].compareTo(arr[start]) < 0) {
                swap(arr, i , ++j);
            }
        }
        swap(arr, j, start);
        return j;
    }


   /**
     * 将arr数组中的下标为first和second的元素交换
     * @param arr 待交换的数组
     * @param first 第一个元素的下标
     * @param second 第二个元素的下标
     * @param <E> 泛型的标志
     */
    private <E> void swap(E[] arr, int first, int second) {
        E temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

附测试代码：

import java.util.Random;

public class QuickTest {
    public static void main(String[] args) {

        Integer[] arr = getRandomArrays(10);

        QuickSort01 quickSort01 = new QuickSort01();
        quickSort01.sort(arr);

        for(int i = 0;i < arr.length-1; i++) 
            System.out.print(arr[i] + "  ");
    }


    /** 获取长度为len的随机数组 */
    private static Integer[] getRandomArrays(int len) {
        Random random = new Random();
        Integer[] arr = new Integer[len];
        for (int i = 0; i < len; i++) {
            arr[i] = random.nextInt(len);
        }

        return arr;
    }

    

}

 

版一问题的指出与解决

显然，如果一个数组本来就有序（从小到大），但是如果使用版一，显然限制就很大，他一样会一层层遍历，比如说一个数组为{1,2,3,4,5,6,7,8,9}，使用版一运行顺序应该如下：

  1. 使用limit、j 指向1，i 指向2；然后使用 i 遍历 1 右边的所有数，
  2. 最后limit与 j 交换，因为 j 没有执行过加一，所以就是和本身交换。

第一步和第二步相加的操作数为操作数组段的元素个数。

之后便是要对arr[j+1...arr.length-1]进行排序，也是重复上述操作，每次要进行的操作都与元素个数相同，所以整一套流程下来算法复杂度为 O(n^{2})，而这不是最难受的，更难受的是他的递归深度是O(n)，而之前为什么不管是大学老师还是有些书上我们会有让我们尽量不要使用递归就是因为递归深度越大要使用的内存就越大，会相当耗费内存，且很容易爆出栈溢出，当我测试十万条有序数组时，他出现如下错误：

Exception in thread "main" java.lang.StackOverflowError

但对于这种情况可以通过修改VM Option，添加一个值 "-Xss128m"，此时就不会出现栈溢出了，但结果却高达 12.607584606s

 所以问题该如何解决？那么只要在数组中随机选择一个临界就可以有效避免这种麻烦，因为这样操作之后就不需要每次都轮询 n-1 个元素。

而这个实现也是相当简单。

代码

import java.util.Random;

/**
 * @Description：快速排序版本一
 * @Author: hour
 * @DATE: 2021/7/16 16:31
 * @PROJECT_NAME: quickSort
 */
public class QuickSort01 {
    private Random random = new Random();

    public <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length-1);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int start, int end) {
        /* 设置跳出条件 */
        if (start >= end) { return ;}

        int mid = partition(arr, start, end);
        sort(arr, start, mid-1);
        sort(arr, mid+1, end);
    }


    private <E extends Comparable<E>> int partition(E[] arr, int start, int end) {
        // todo : 这里修改了，使得每次的临界值都是随机的
        int mid = start + random.nextInt(end-start+1);
        swap(arr, mid, start);
        int j = start;

        for (int i = start;i <= end;i++) {
            if (arr[i].compareTo(arr[start]) < 0) {
                swap(arr, i , ++j);
            }
        }
        swap(arr, j, start);
        return j;
    }



    private <E> void swap(E[] arr, int first, int second) {
        E temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

比较结果如图 ：

 结果显著，差距不是一星半点。当然每次运行的结果肯定不一样，毕竟这个临界点是随机抽取的，所以他的时间复杂度仍然是O(n^{2})，因为最差的情况可以使每次都抽中了最小的元素，但随着数据规模变大这种情况出现的概率可以忽略不计。

版一剩余问题

可以，有序问题基本解决，但也指出了如果每次运气都不好，抽中“最小”的了呢？

虽然我不能靠运气每次选中最小，但是我可以强迫他选择最小——元素全部相等，在这种情况下，随机选择的情况会如何？

这个问题又当如何解决，复杂度又变成了  O(n^{2})。这时有人提出了双路快排，先介绍一下双路快排。

双路快排：（下面的操作如果觉得理解起来有点空洞，不妨虽然用一个例子试试，自己画个图）

  1. 让limit执行第一个元素，也就是作为临界点，另外使用两个指针，一个指针 i 指向start+1；另一个指针 j 指向end，两个指针从两头开始遍历
  2. 当 arr[i] >= arr[limit]时，跳出循环，并让 j 开始遍历直到arr[j] <= arr[limit]，否则 i++ ；
  3. 两个遍历结束交换arr[i] 和 arr[j]的值，并且执行 i++ 、 j++ ，使得指向下一个元素继续执行遍历，重复操作2，直到 i >= j ，说明已经将所有元素遍历完成。
  4. 最后交换arr[limit] 和 arr[j]
  5. 结果仍然分布为 j 的左边为小于等于arr[limit]，右边大于arr[limit]
  6. 最后返回 j ，然后对arr[start...j-1] 和 arr[j+1...end]进行排序

执行完这一些列操作就可以使得

 代码实现

import java.util.Random;

/**
 * @Description：快速排序版本一
 * @Author: hour
 * @DATE: 2021/7/16 16:31
 * @PROJECT_NAME: quickSort
 */
public class QuickSort01 {
    private Random random = new Random();

    public <E extends Comparable<E>> void sort2Ways(E[] arr) {
        sort2Ways(arr, 0, arr.length-1);
    }


    private <E extends Comparable<E>> void sort2Ways(E[] arr, int start,int end) {
        if (start >= end)   { return; }


        int mid = partition2Ways(arr, start, end);
        sort2Ways(arr, start, mid-1);
        sort2Ways(arr, mid+1, end);
    }

    private <E extends Comparable<E>> int partition2Ways(E[] arr, int start, int end) {
        int mid = start + random.nextInt(end-start);
        swap(arr, mid, start);

        int i = start +1;
        int j = end;

        while (true) {
            /* 这里的 i <= j是必要的，如果第一次循环就满足该条件的情况也需要考虑 */
            while (i<=j && arr[i].compareTo(arr[start]) > 0) {
                i ++;
            }
            /* 而这个主要考虑的是运行时执行了多个i++之后的情况，所以要判断j >= i */
            while (j>=i && arr[j].compareTo(arr[start]) < 0) {
                j --;
            }
            if (i >= j) { break; }

            swap(arr ,i ,j);
            i ++;
            j --;
        }

        swap(arr, i , start);
        return i;
    }


    private <E> void swap(E[] arr, int first, int second) {
        E temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

运行结果如下图：

或许有人要说了，哪有这种情况，全部元素相等，这不是扯淡吗？不实用好吧。

可是这种情况只是适用于大量元素相等的情况，这种情况就会多的多了，只要相同的数据越多，这个算法就可以有越大优势。

双路快排剩余问题

我们从上面的双路快排可以知道，我们是把数组分为两部分，大于等于临界值，小于等于临界值，但是我们知道，如果有很多元素都等于临界值，这些等于临界值的元素仍然会被排序，但其实我们都知道这些元素不需要再排序了，如果让这些元素不排序，就会节约很多资源。

那么这个问题如何解决大家应该都有想法了，分为三段，一段小于临界值、一段大于临界值

、一段等于临界值。没错，确实如此，来看看如何操作吧。

第一步——初始

数组元素如下，假设第一个元素就是抽中的临界点i = start+1，

arr[start+1...lt]值都小于arr[limit]

arr[gt...end]值都大于arr[limit]

arr[lt+1...gt-1]值都等于arr[limit]，当i >= gt 的时候就结束了。

 第二步——i 开始遍历数组

要让 lt 和 gt 实现上述的意义，就必须执行以下判断：

  • arr[i] > 6：gt--，交换arr[i] 和 arr[gt]，注意这里 i 不执行加一，因为转换过来的元素仍然可能大于临界值

  • arr[i] == 6：不做任何操作，直接 i++

  •  arr[i] > 6：lt++，交换arr[i] 和 arr[lt]，注意这里需要执行i++，比如说数组{9,4,3,5}，使用三路排序，且抽中的临界就是9，执行一次lt++后，然后 i 没有改变，但会继续循环，这时又会使得lt++，这时就出现了错误，本来 lt 不应该大于 i ，上面的区间也能说明，简单想想也可以求证，就不赘述了

 一轮操作完毕后，并且执行完arr[start]和arr[lt]的交换后

显然，第一次遍历的结果与我们推出的一样。而实际结果也和代码结果一样

 代码实现

import java.util.Random;

/**
 * @Description：快速排序版本一
 * @Author: hour
 * @DATE: 2021/7/16 16:31
 * @PROJECT_NAME: quickSort
 */
public class QuickSort01 {
    private Random random = new Random();

    public <E extends Comparable<E>> void sort3Ways(E[] arr) {
        sort3Ways(arr, 0, arr.length-1);
    }


    private <E extends Comparable<E>> void sort3Ways(E[] arr, int start,int end) {
        if (start >= end)   { return; }

        int[] mid = partition3Ways(arr, start, end);

        sort3Ways(arr, start, mid[0]);
        sort3Ways(arr, mid[1], end);
    }

    private <E extends Comparable<E>> int[] partition3Ways(E[] arr, int start, int end) {
        int mid = start + random.nextInt(end-start+1);
        swap(arr, mid, start);

        int i = start +1;
        int gt = end + 1;
        int lt = start;

        while(i < gt) {
            if (arr[i].compareTo(arr[start]) < 0) {
                lt ++;
                swap(arr ,lt ,i);
                i ++;
            } else if (arr[i].compareTo(arr[start]) > 0) {
                gt --;
                swap(arr, gt, i);
            } else {
                i ++;
            }
        }

        swap(arr, lt , start);
        
        System.out.println();
        return new int[]{lt ,gt};
    }



   private <E> void swap(E[] arr, int first, int second) {
        E temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
   }
}

 至此，我想总结的就这么多了，有啥问题可以说出来，初出茅庐。

对了如果需要视频资源可以向我买，老弟我也是买的，视频资源还包括很多其他算法。

详情请见https://download.csdn.net/download/qq_50679242/20334507

热门文章

暂无图片
编程学习 ·
2022/1/17 15:17:17

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·
2022/1/17 10:17:14

GMX 命令分类列表

建模和计算操作命令&#xff1a; 1.1 . 创建拓扑与坐标文件 gmx editconf - 编辑模拟盒子以及写入子组(subgroups) gmx protonate - 结构质子化 gmx x2top - 根据坐标生成原始拓扑文件 gmx solvate - 体系溶剂化 gmx insert-molecules - 将分子插入已有空位 gmx genconf - 增加…
暂无图片
编程学习 ·
2022/1/17 0:17:09

一文高效回顾研究生课程《数值分析》重点

数值分析这门课的本质就是用离散的已知点去估计整体&#xff0c;就是由黑盒子产生的结果去估计这个黑盒子。在数学里这个黑盒子就是一个函数嘛&#xff0c;这门课会介绍许多方法去利用离散点最大化地逼近这个函数&#xff0c;甚至它的导数、积分&#xff0c;甚至微分方程的解。…
暂无图片
编程学习 ·
2022/1/16 19:17:06

在职阿里5年，一个28岁女软测工程师的心声

简单的先说一下&#xff0c;坐标杭州&#xff0c;14届本科毕业&#xff0c;算上年前在阿里巴巴的面试&#xff0c;一共有面试了有6家公司&#xff08;因为不想请假&#xff0c;因此只是每个晚上去其他公司面试&#xff0c;所以面试的公司比较少&#xff09; ​ 编辑切换为居中…
暂无图片
编程学习 ·
2022/1/16 14:17:04

字符串左旋c语言

目录 题目&#xff1a; 解题思路&#xff1a; 第一步&#xff1a; 第二步&#xff1a; 第三步&#xff1a; 总代码&#xff1a; 题目&#xff1a; 实现一个函数&#xff0c;可以左旋字符串中的k个字符。 例如&#xff1a; ABCD左旋一个字符得到BCDA ABCD左旋两个字符…
暂无图片
编程学习 ·
2022/1/16 9:16:58

设计模式--观察者模式笔记

模式的定义与特点 观察者&#xff08;Observer&#xff09;模式的定义&#xff1a;指多个对象间存在一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式&#xf…
暂无图片
编程学习 ·
2022/1/16 4:16:55

睡觉突然身体动不了，什么是睡眠痽痪症

很多朋友可能有这样的体验&#xff0c;睡觉过程中突然意识清醒&#xff0c;身体却动弹不了。这时候感觉非常恐怖&#xff0c;希望旁边有一个人推自己一下。阳光以前也经常会碰到这样的情况&#xff0c;一年有一百多次&#xff0c;那时候很害怕晚上到来&#xff0c;睡觉了就会出…
暂无图片
编程学习 ·
2022/1/15 23:16:49

深入理解C++智能指针——浅析MSVC源码

文章目录unique_ptrshared_ptr 与 weak_ptrstd::bad_weak_ptr 异常std::enable_shared_from_thisunique_ptr unique_ptr 是一个只移型别&#xff08;move-only type&#xff0c;只移型别还有std::mutex等&#xff09;。 结合一下工厂模式&#xff0c;看看其基本用法&#xff…
暂无图片
编程学习 ·
2022/1/15 18:16:46

@TableField(exist = false)

TableField(exist false) //申明此字段不在数据库存在&#xff0c;但代码中需要用到它&#xff0c;通知Mybatis-plus在做写库操作是忽略它。,.
暂无图片
编程学习 ·
2022/1/15 13:16:44

Java Web day15

第十二章文件上传和下载 一、如何实现文件上传 要实现Web开发中的文件上传功能&#xff0c;通常需要完成两步操作&#xff1a;一.是在Web页面中添加上传输入项&#xff1b;二是在Servlet中读取上传文件的数据&#xff0c;并保存到本地硬盘中。 需要使用一个Apache组织提供一个…
暂无图片
编程学习 ·
2022/1/15 8:16:42

【51nod 2478】【单调栈】【前缀和】小b接水

小b接水题目解题思路Code51nod 2478 小b接水 题目 输入样例 12 0 1 0 2 1 0 1 3 2 1 2 1输出样例 6解题思路 可以发现最后能拦住水的都是向两边递减高度&#xff08;&#xff1f;&#xff09; 不管两个高积木之间的的积木是怎样乱七八糟的高度&#xff0c;最后能用来装水的…
暂无图片
编程学习 ·
2022/1/15 3:16:37

花了大半天写了一个UVC扩展单元调试工具

基于DIRECTSHOW 实现的&#xff0c;用的是MFC VS2019. 详见&#xff1a;http://www.usbzh.com/article/detail-761.html 获取方法 加QQ群:952873936&#xff0c;然后在群文件\USB调试工具&测试软件\UVCXU-V1.0(UVC扩展单元调试工具-USB中文网官方版).exe USB中文网 USB中文…
暂无图片
编程学习 ·
2022/1/14 22:16:30

贪心（一）：区间问题、Huffman树

区间问题 例题一&#xff1a;区间选点 给定 N 个闭区间 [ai,bi]请你在数轴上选择尽量少的点&#xff0c;使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 输入格式 第一行包含整数 N&#xff0c;表示区间数。 接下来 …
暂无图片
编程学习 ·
2022/1/14 12:16:25

C语言练习实例——费氏数列

目录 题目 解法 输出结果 题目 Fibonacci为1200年代的欧洲数学家&#xff0c;在他的着作中曾经提到&#xff1a;「若有一只免子每个月生一只小免子&#xff0c;一个月后小免子也开始生产。起初只有一只免子&#xff0c;一个月后就有两只免子&#xff0c;二个月后有三只免子…
暂无图片
编程学习 ·
2022/1/14 7:16:20

Android开发(2)： Android 资源

个人笔记整理 Android 资源 Android中的资源&#xff0c;一般分为两类&#xff1a; 系统内置资源&#xff1a;Android SDK中所提供的已经定义好的资源&#xff0c;用户可以直接拿来使用。 用户自定义资源&#xff1a;用户自己定义或引入的&#xff0c;只适用于当前应用的资源…
暂无图片
编程学习 ·
2022/1/14 2:16:16

零基础如何在短时间内拿到算法offer

​算法工程师是利用算法处理事物的职业 算法&#xff08;Algorithm&#xff09;是一系列解决问题的清晰指令&#xff0c;也就是说&#xff0c;能够对一定规范的输入&#xff0c;在有限时间内获得所要求的输出。 如果一个算法有缺陷&#xff0c;或不适合于某个问题&#xff0c;执…
暂无图片
编程学习 ·
2022/1/13 21:16:11

人工智能：知识图谱实战总结

人工智能python&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习人工智能&#xff1a;知识图谱实战前言一、实体建模工具Protegepython&#xff0c;NLP&#xff0c;知识图谱&#xff0c;机器学习&#xff0c;深度学习 人工智能&#xff1a;知识图…
暂无图片
编程学习 ·
2022/1/13 16:16:06

【无标题】

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注…