【高效且应用广泛的排序 —— 快速排序算法】

高效且应用广泛的排序 —— 快速排序算法

快速排序是一种常用的排序算法,主要采用分治的思想。以下是对快速排序算法的详细介绍及代码示例:

快速排序的基本思路是,每次将一个位置上的数据归位,使得该数左边的所有数据都比该数小,右边所有的数据都比该数大,然后递归将已归位的数据左右两边再次进行快排,从而实现所有数据的归位。

算法步骤如下:

  1. 从数列中挑出一个元素,称为“基准”。
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区操作。
  3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

在这里插入图片描述

例如,对于数组,选择最左边的元素 29 作为中间点元素,然后将数组分成三部分:(0, 14, 15, 20, 25),(29),(44, 37)。中间节点 29 已经排好序了,不需要处理。接下来再对左右分别进行快速排序。

下面是 Java 代码示例:

public class QuickSort {
    // 测试
    public static void main(String[] args) {
        int[] arr = {5,2,9,6,3,1,7,8,4};
        int left = 0;
        int right = arr.length - 1;
        quickSort(arr, left, right);
        System.out.println("排序结果:");
        for(int num : arr){
            System.out.print(num + " ");
        }
    }
    // 快速排序算法
    public static void quickSort(int[] arr,int left,int right) {
        if(left < right) {
            int partitionIndex = partition(arr, left, right);
            // 将数组划分为两部分,并返回划分点的索引
            quickSort(arr, left, partitionIndex - 1);
            // 递归排序左子数组
            quickSort(arr, partitionIndex + 1, right);
            // 递归排序右子数组
        }
    }
    // 划分函数
    public static int partition(int[] arr,int left,int right) {
        int pivot = arr[right];
        // 选择最后一个元素作为基准值
        int i = left - 1;
        // i 为较小元素的索引
        for(int j = left; j < right; j++){
            if(arr[j] <= pivot){
                i++;
                swap(arr, i, j);
                // 交换较小元素与当前元素
            }
            // 如果数组元素大于等于 middleValue,则继续向后遍历,middleIndex 值不变
        }
        swap(arr, i + 1, right);
        // 将基准值放置到正确的位置上
        return i + 1;
        // 返回划分点的索引
    }
    // 交换数组中两个元素的位置
    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i]= arr[j];
        arr[j]= temp;
    }
}

快速排序在平均情况下时间复杂度为 O(n log n),但在最坏情况下时间复杂度会变为 O(n²)。可以通过随机选择基准元素或使用三数取中法等方法来避免最坏情况。空间复杂度为 O(log n),因为在递归调用中需要使用栈来存储中间结果。快速排序虽然在最坏情况下时间复杂度可能较高,但在实际应用中通常表现良好,尤其对于大规模数据集的排序。如果实现得当,它是一种高效的排序算法。

快速排序算法基本思路

在这里插入图片描述

快速排序是一种高效的排序算法,其基本思路是分治法。首先从数列中取出一个数作为基准数,然后进行分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。接着再对左右区间重复这个步骤,直到各区间只有一个数。概括来说就是“挖坑填数+分治法”。

快速排序就像整理一堆杂乱的卡片。假设我们有一叠无序的数字卡片,我们随机选取一张卡片作为基准数,比如选择第一张卡片。然后我们从这叠卡片的右边开始,找到比基准数小的卡片,从左边开始找到比基准数大的卡片,找到后交换这两张卡片的位置。这样不断进行,直到左右指针相遇。此时,我们把基准数放到正确的位置上,这个位置左边的数字都小于等于基准数,右边的数字都大于基准数。然后我们再对左右两边的子序列重复这个过程,直到所有的子序列都只有一个数字,此时整个序列就有序了。

例如,有一组数字。我们选择4作为基准数,首先从右边开始,9大于4,继续向左,3小于4,此时停下。然后从左边开始,1小于4,继续向右,6大于4,停下。交换3和6的位置,得到。接着继续这个过程,指针不断移动,直到左右指针相遇。最后把4放到正确的位置上,此时序列变为。然后再对左边的子序列和右边的子序列分别进行快速排序,直到所有子序列都有序。

快速排序算法步骤

  1. 从序列中任选一个数作为基准数,一般就使用第一个数。
  2. 进行分区操作,将大于基准数的数放在右边,小于基准数的数放在左边,注意一定要先右后左。具体操作是设置两个指针i和j,分别指向数组的第一个元素和最后一个元素。从j开始向左挪动,直到找到一个小于基准数的数停下来;然后切换到i再向右挪动,直到找到一个数大于基准数的数停下来。最后将i和j指向的元素进行交换位置。重复这个过程直到i和j重合,此时把重合点的元素与基准元素交换位置。
  3. 对左右区间分别执行上述步骤,直到每个区间只有一个数为止。

例如对于数组,选择5作为基准数。首先j从6开始向左移动,找到3小于5停下。i从0开始向右移动,找到8大于5停下。交换3和8的位置,得到。接着j继续向左移动,找到1小于5停下。i继续向右移动,找到2小于5不停下,继续移动找到8大于5停下。交换1和8的位置,得到。此时i和j重合在1的位置,把1和5交换位置,得到。然后对左边的子序列和右边的子序列分别进行快速排序,直到所有子序列都有序。

快速排序代码示例解析

以下是一段快速排序的 Python 代码示例:

def quickSort(lists, left, right):
    # 快速排序
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    print("lists:", lists)
    quickSort(lists, low, left - 1)
    quickSort(lists, left + 1, high)
    return lists

这段代码首先判断左右指针的位置,如果左指针大于等于右指针,说明该子序列已经有序,直接返回。然后选择左指针指向的元素作为基准数key。接着使用两个循环,从右向左找到小于基准数的元素,从左向右找到大于基准数的元素,然后交换这两个元素的位置。当左右指针相遇时,将基准数放到正确的位置上。最后递归地对左右子序列进行快速排序。

以列表为例,调用quickSort函数进行排序。首先选择3作为基准数,从右向左找到2小于3停下,从左向右找到6大于3停下,交换2和6的位置,得到。接着继续这个过程,直到左右指针相遇,把3放到正确的位置上。然后对左边的子序列和右边的子序列分别进行快速排序,直到整个列表有序。

快速排序时间复杂度分析

快速排序的时间复杂度与划分是否平衡密切相关。最优情况下,时间复杂度为 O(nlogn)。这是因为每次划分都能将序列均匀地分成两部分,此时快速排序的性能与归并排序一样。

例如,对于一个包含 n 个数的序列,递归的第一层,将 n 个数划分为 2 个子区间,每个子区间的数字个数约为 n/2;递归的第二层,将 n 个数划分为 4 个子区间,每个子区间的数字个数约为 n/4;以此类推,递归的第 logn 层,将 n 个数划分为 n 个子区间,每个子区间的数字个数为 1。在每一层的划分过程中,时间复杂度约为 O(n),而总共需要划分 logn 层,所以最优情况下的时间复杂度为 O(nlogn)。

然而,在最坏情况下,时间复杂度为 O(n^2)。当每次选择的基准元素是最大或最小元素时,快速排序的时间复杂度是 O(n^2)。例如,序列已经是有序的,每次选择第一个元素作为基准数,那么每次划分只能分出一个元素,导致递归的深度达到 n,而每一层的时间复杂度为 O(n),所以最坏情况下的时间复杂度为 O(n^2)。

平均情况下,快速排序的时间复杂度也是 O(nlogn)。在实际应用中,快速排序通常表现良好,尤其对于大规模数据集的排序。

快速排序避免最坏情况方法

为了避免快速排序的最坏情况,可以采用以下几种方法:

  1. 随机选取划分点:每次随机从待排序序列中选取一个元素作为划分点,从而降低最坏情况的概率。这样可以避免每次都选择到最大或最小元素作为基准数,使得划分更加平衡。
  2. 三数取中法:选取待排序序列的第一个、中间一个、最后一个元素中的中间值作为划分点,从而降低最坏情况的概率。例如对于序列,可以选择1、6、3中的中间值3作为基准数,这样可以在一定程度上避免选择到最大或最小元素。
  3. 在递归深度较浅时采用其他排序算法,比如插入排序或归并排序等,从而避免快速排序退化成 O(n^2) 的情况。当问题规模小于某一 k 值时,采用插入排序,提高算法效率。

总结

快速排序算法是一种高效的排序算法,其基本思路是分治法,通过不断地划分和递归,将序列分成越来越小的子序列进行排序,直到所有子序列都有序。在实际应用中,可以根据不同的情况选择合适的方法来避免最坏情况的发生,以提高算法的性能。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/882200.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

构建高效企业客户管理系统:SpringBoot应用

1 绪论 1.1研究背景 随着网络不断的普及发展&#xff0c;企业客户管理系统依靠网络技术的支持得到了快速的发展&#xff0c;首先要从员工的实际需求出发&#xff0c;通过了解员工的需求开发出具有针对性的首页、个人中心、员工管理、客户信息管理、行业类型管理、项目信息管理、…

自动化测试概念篇

目录 一、自动化 1.自动化概念 1.1 回归测试 2. 自动化分类 2.1 接口自动化 2.2 UI自动化 3. 自动化测试金字塔 二、web自动化测试 1. 驱动 1.1 安装驱动管理 1.2 selenium库 三、selenium 1. 一个简单的web自动化示例 2. selenium驱动浏览器的工作原理 一、自动化…

【Linux系统编程】第二十二弹---操作系统核心概念:进程创建与终止机制详解

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】 目录 1、进程创建 1.1、fork函数重识 1.2、fork函数返回值 1.3、写时拷贝 1.4、fork常规用法 1.5、fork调用失败的原因 2、进程…

图像压缩编码(4)--H.26x系列视频压缩编码_2

目录 H.261 视频编码标准 H.261的编码与解码 1&#xff09; 帧内/帧间编码 2&#xff09;运动补偿 3&#xff09;量化 4&#xff09;环路滤波器 5&#xff09;缓存器 压缩数据的分层 数据复用结构 H.264的编码与解码 H.261 视频编码标准 实际应用时&#xff0c;要求有…

【C++】list详解及模拟实现

目录 1. list介绍 2. list使用 2.1 修改相关 2.2 遍历 2.3 构造 2.4 迭代器 2.5 容量相关 2.6 元素访问 2.7 操作相关 3. 模拟实现 3.1 节点类 3.1.1 初始结构 3.1.2 节点的构造函数 3.2 迭代器类 3.2.1 初始结构 3.2.2 迭代器 3.2.3 迭代器-- 3.2.4 解引…

基于VUE的医院抗生素使用审核流程信息化管理系统

开发背景 随着医疗行业的快速发展和信息技术的不断进步&#xff0c;医院内部管理系统的信息化建设变得尤为重要。抗生素作为治疗感染性疾病的重要药物&#xff0c;在临床使用过程中需要严格控制以避免滥用导致的耐药性问题。传统的抗生素使用审核流程往往依赖于人工审核&#x…

第十一章 从0-1搭建一个简单的JavaWeb系统(三)

目录 一、工程代码结构 二、代码实现 三、运行效果 四、未完待续 本章节的每一段代码&#xff0c;建议全部自己敲一遍&#xff0c;加深印象&#xff0c;切勿直接复制黏贴。 一、工程代码结构 本章节实现注销&#xff08;退出&#xff09;功能&#xff0c;以下图片中标红的…

苹果CMS插件:优化蜘蛛访问内容,提升百度收录率

确保蜘蛛抓取原始内容 专为苹果CMS设计的广告管理插件&#xff0c;能够智能识别搜索引擎蜘蛛与普通访客&#xff0c;确保蜘蛛访问时展示原始内容&#xff0c;从而提升被百度等搜索引擎收录的几率。 广告显示提升收益 对于普通访客&#xff0c;该插件则优先显示广告内容&#…

【网络】高级IO——select版本TCP服务器

目录 前言 一&#xff0c;select函数 1.1.参数一&#xff1a;nfds 1.2.参数二&#xff1a; readfds, writefds, exceptfds 1.2.1.fd_set类型和相关操作宏 1.2.2.readfds, writefds, exceptfds 1.2.3.怎么理解 readfds, writefds, exceptfds是输入输出型参数 1.3.参数三…

面试速通宝典——1

1. 内存有哪几种类型&#xff1f; ‌‌‌‌  内存分为五个区&#xff0c;堆&#xff08;malloc&#xff09;、栈&#xff08;如局部变量、函数参数&#xff09;、程序代码区&#xff08;存放二进制代码&#xff09;、全局/静态存储区&#xff08;全局变量、static变量&#…

2024-1.2.12-Android-Studio配置

本地博客: https://k1t0111.github.io/ K1T0 最近在做一些app方向的移动技术开发学习&#xff0c;但是由于AS的配置问题&#xff0c;市面上找不到最新的2024版本的AS的相关配置。笔者也是踩了很多坑&#xff0c;因此想写一篇文章记录一下最新的AS 2024 1.2.12的对应java环境的一…

springboot框架VUE3学院网站系统开发mysql数据库设计java编程计算机网页源码maven项目

博主介绍&#xff1a;专注于Java vue .net php phython 小程序 等诸多技术领域和毕业项目实战、企业信息化系统建设&#xff0c;从业十五余年开发设计教学工作 ☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆不然下次找不到哟 我的博客空间发布了1000毕设题目 方便大家学习使用 感兴趣的…

python 识别省市、区县并组建三级信息数据库

一、网址&#xff1a; 全国行政区划信息查询平台 二、分析并搭建框架 检查网页源码&#xff1a; 检查网页源码可以发现&#xff1a; 所有省级信息全部在javaScript下的json中&#xff0c;会在页面加载时加载json数据&#xff0c;填充到页面的option中。 1、第一步&#xff1a…

探秘 Web Bluetooth API:连接蓝牙设备的新利器

引言 随着物联网技术的快速发展&#xff0c;蓝牙设备在日常生活中扮演着越来越重要的角色。而在 Web 开发领域&#xff0c;Web Bluetooth API 的出现为我们提供了一种全新的方式来连接和控制蓝牙设备。本文将深入探讨 Web Bluetooth API 的使用方法和原理&#xff0c;帮助开发…

浅显易懂的Git教程

Git概述 SVN与Git的对比 SVN&#xff08;Subversion&#xff09; 类型&#xff1a;集中式版本控制系统 工作流程&#xff1a; 从中央服务器下载最新版本到本地。在本地进行开发。提交更改回中央服务器。 优点&#xff1a; 简单易用&#xff0c;适合小型团队。版本历史清…

vs2022快捷键异常不起作用解决办法

安装了新版本的vs2022&#xff0c;安装成功后&#xff0c;发现快捷键发生异常&#xff0c;之前常用的快捷键要么发生改变&#xff0c;要么无法使用&#xff0c;比如原来注释代码的快捷键是ctrlec&#xff0c;最新安装版本变成了ctrlkc&#xff0c;以前编译代码的快捷键是F6或者…

初始MYSQL数据库(6)—— 事务

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; MYSQL 目录 事务的概念 事务的ACID特性 使用事务 查看支持事务的存储引擎 事务的语法 保存点 自动/手动提交事务 事务的隔离性和…

Python模拟鼠标轨迹[Python]

一.鼠标轨迹模拟简介 传统的鼠标轨迹模拟依赖于简单的数学模型&#xff0c;如直线或曲线路径。然而&#xff0c;这种方法难以捕捉到人类操作的复杂性和多样性。AI大模型的出现&#xff0c;能够通过深度学习技术&#xff0c;学习并模拟更自然的鼠标移动行为。 二.鼠标轨迹算法实…

【原创】java+swing+mysql仓库管理系统设计与实现

个人主页&#xff1a;程序员杨工 个人简介&#xff1a;从事软件开发多年&#xff0c;前后端均有涉猎&#xff0c;具有丰富的开发经验 博客内容&#xff1a;全栈开发&#xff0c;分享Java、Python、Php、小程序、前后端、数据库经验和实战 文末有本人名片&#xff0c;希望和大家…

Qt开发技巧(四)“tr“使用,时间类使用,Qt容器取值,类对象的删除,QPainter画家类,QString的转换,用好 QVariant类型

继续讲一些Qt技巧操作 1.非必要不用"tr" 如果程序运行场景确定是某一固定语言&#xff0c;就不需要用tr,"tr"之主要针对多语种翻译的&#xff0c;因为tr的本意是包含英文&#xff0c;然后翻译到其他语言比如中文&#xff0c;不要滥用tr&#xff0c;如果没有…