【排序算法系列】快速排序

这篇具有很好参考价值的文章主要介绍了【排序算法系列】快速排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

文章中的部分照片来源于哔站黑马程序员阿伟老师处,仅用学习,无商用,侵权联系删除!

要想学习快速排序,前提必须了解 递归算法

概况

快速排序是一种高效的排序算法,它采用了分治的策略。

基本思想是选择一个基准数,通过一趟排序将待排序序列划分成两个子序列,其中一个子序列的所有元素小于基准数,另一个子序列的所有元素大于基准数。然后对这两个子序列递归地应用快速排序算法,直到子序列的长度为1或0,即达到最终的排序结果。

快速排序是一种原地排序算法,它的平均时间复杂度为O(nlogn),其中n是待排序序列的长度。但在最坏情况下,即待排序序列已经有序或近乎有序时,快速排序的时间复杂度为O(n^2),这是因为每次划分都只能减少一个元素的位置。

步骤

其基本步骤如下:

  1. 选择一个基准数(通常是序列的第一个元素)。

  2. 定义两个指针,一个指向序列的起始位置,另一个指向序列的末尾位置。

  3. 从右向左移动右指针,直到找到一个小于基准数的元素。

  4. 从左向右移动左指针,直到找到一个大于基准数的元素。

  5. 交换左右指针所指向的元素。

  6. 重复步骤3、4、5,直到左指针和右指针相遇。

  7. 将基准数和左指针所指向的元素进行交换,使得基准数归位。

  8. 对基准数左边的子序列和右边的子序列递归应用以上步骤,直到子序列的长度为1或0。

  9. 完成排序后,序列就被分成了若干个以基准数为中心的子序列,子序列的元素都已经有序。

【排序算法系列】快速排序,算法,算法,数据结构,排序算法,java

代码示例

需求:采用快速排序将下列数据进行排序,数据如下{6, 2, 6, 3, 9, 4, 7, 8, 5, 1, 10}

例如:

package text.text02;

/*
快速排序:
            以0索引的数字为基准数,确定基准数在数组中正确的位置。
            比基准数小的全部在左边,比基准数大的全部在右边。
            后面以此类推。
步骤:
    1. 从数列中挑出一个元素,一般都是左边第一个数字,称为 "基准数";
    2. 创建两个指针,一个从前往后走,一个从后往前走。
    3. 先执行后面的指针,找出第一个比基准数小的数字
    4. 再执行前面的指针,找出第一个比基准数大的数字
    5. 交换两个指针指向的数字
    6. 直到两个指针相遇
    7. 将基准数跟指针指向位置的数字交换位置,称之为:基准数归位。
    8. 第一轮结束之后,基准数左边的数字都是比基准数小的,基准数右边的数字都是比基准数大的。
    9. 把基准数左边看做一个序列,把基准数右边看做一个序列,按照刚刚的规则递归排序
 */
public class text15A {
    public static void main(String[] args) {
        int[] arr = {6, 2, 6, 3, 9, 4, 7, 8, 5, 1, 10};
        //调用quickSort方法
        quickSort(arr, 0, arr.length - 1);
        //遍历数组输出数组数据
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");      //1  2  3  4  5  6  6  7  8  9  10
        }
    }

    //创建快速排序方法quickSort
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        //定义变量接受startIndex和endIndex,方便以后递归
        int i = startIndex;
        int j = endIndex;

        //起始索引大于结束索引,说明遍历完成,结束方法(出口)
        if (startIndex > endIndex) {
            return;
        }

        //定义个变量记录基准数
        int number = arr[startIndex];

        //当起始索引小于结束索引时
        while (startIndex < endIndex) {
            //当起始索引小于结束索引并且从右向左遍历时的某个数大于基准数时
            while (startIndex < endIndex && arr[endIndex] >= number) {
                endIndex--;
            }

            //当起始索引小于结束索引并且从左向右遍历时的某个数小于基准数时
            while (startIndex < endIndex && arr[startIndex] <= number) {
                startIndex++;
            }

            //将从右向左遍历时大于基准数的某个数与从左向右遍历时小于基准数的某个数进行交换
            int temp = arr[endIndex];
            arr[endIndex] = arr[startIndex];
            arr[startIndex] = temp;
        }
        //当起始索引与结束索引相等时,将其对应的数与基准数进行交换
        int num = arr[startIndex];
        arr[startIndex] = number;
        arr[i] = num;

        //在基准数左边的数接着递归调用该方法
        quickSort(arr, i, startIndex - 1);
        //在基准数右边的数接着递归调用该方法
        quickSort(arr, startIndex + 1, j);
    }
}

输出结果

【排序算法系列】快速排序,算法,算法,数据结构,排序算法,java
流程图:文章来源地址https://www.toymoban.com/news/detail-830034.html

开始
├─ 定义快速排序方法 quickSort
│    ├─ 如果起始索引大于结束索引,返回
│    ├─ 选择数组中的一个元素作为基准数
│    ├─ 定义指针 i 指向起始索引
│    ├─ 定义指针 j 指向结束索引
│    ├─ 循环直到指针 i 和 j 相遇
│    │    ├─ 从右向左移动指针 j,找到一个比基准数小的数字
│    │    ├─ 从左向右移动指针 i,找到一个比基准数大的数字
│    │    ├─ 如果指针 i 和 j 没有相遇
│    │    │    ├─ 交换指针 i 和指针 j 指向的数字
│    ├─ 交换基准数与指针 i 指向的数字,基准数归位
│    ├─ 递归调用 quickSort 方法,对基准数左边的序列进行排序
│    ├─ 递归调用 quickSort 方法,对基准数右边的序列进行排序
├─ 创建数组 arr
├─ 调用 quickSort 方法,对数组 arr 进行排序
├─ 遍历数组 arr,输出排序后的数据
结束

到了这里,关于【排序算法系列】快速排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法之快速排序

    快速排序 (Quick Sort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数

    2024年02月10日
    浏览(43)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

    2024年02月08日
    浏览(50)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(53)
  • 【数据结构】排序算法系列

    常见的排序如下: (1) 冒泡排序 【数据结构】交换排序(一)——冒泡排序_Jacky_Feng的博客-CSDN博客 (2) 快速排序 【数据结构】交换排序(二)——快速排序_Jacky_Feng的博客-CSDN博客 【算法】快速排序及其拓展优化(单向快速排序、单链表的快速排序)_Jacky_Feng的博客-C

    2024年02月14日
    浏览(29)
  • 【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现 好了废话不多说,开

    2024年02月08日
    浏览(44)
  • Java 与数据结构(6):快速排序

    ChatGPT 中文指南(大全) 内容包含:如何开通chatgpt、chatgpt的同类站点、prompts 、AI绘图、ChatGPT 工具、相关报告论文、ChatGPT应用项目等 链接:ChatGPT 中文指南(大全) 指令指南,精选资源清单,更好的使用 chatGPT 让你的生产力up up up! 快速排序(Quick Sort)是一种基于分治思想的排序

    2024年02月07日
    浏览(38)
  • 【数据结构与算法】快速排序的三种实现方法

      目录 一.基本思想 二.Hoare法 动态演示 三.挖坑法 动态演示 四.前后指针法 动态演示 五.快速排序优化 随机下标交换法 三路取中法 六.快速排序的特性 任取待排序元素序列中的某元素作为 基准值 ,按照该排序码将待排序集合 分割成两子序列 , 左子序列中所有元素均小于基

    2023年04月09日
    浏览(62)
  • 【数据结构与算法】快速排序的非递归实现方法

      目录 一.前言 二.非递归实现 如果数据量过大的话,不断递归就会出现 栈溢出 的现象,这个时候你的代码是没问题的,但就是跑不起来,这个时候就要 把递归改成非递归 。 一般有两种改法: 1.直接改,利用循环等; 2.借助栈的辅助。 而快速排序的非递归实现方法就需要

    2023年04月17日
    浏览(53)
  • 【数据结构】详解七大排序算法(直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序)

    1、基本思想    把待排序的数按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所以的记录插入完为止,得到一个新的有序序列。    实际中我们玩扑克牌时,就用到了插入排序的思想 基本步骤:    当插入第i个元素时,前面的arr[0]、arr[2]…arr

    2024年02月04日
    浏览(74)
  • 数据结构和算法——快速排序(算法概述、选主元、子集划分、小规模数据的处理、算法实现)

    目录 算法概述 图示 伪代码 选主元 子集划分 小规模数据的处理 算法实现 快速排序和归并排序有一些相似,都是用到了分而治之的思想:   通过初步的认识,我们能够知道快速排序算法最好的情况应该是: 每次都正好中分 ,即每次选主元都为元素的中位数的位置。 最好情

    2024年02月15日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包