快速排序详解(Java实现)
发布日期:2021-07-26 07:20:45 浏览次数:1 分类:技术文章

本文共 2097 字,大约阅读时间需要 6 分钟。

一、快速排序的基本思想

    每一轮的排序都会将区域分割成两个独立的分区,其中左分区的序列的所有值均会比右分区的所有值小。然后对子分区进行同样的分割操作,最后达到整体有序。在排序的过程中,由于已经分开的两部分的元素不需要进行比较,故减少了比较的次数,降低了排序时间。

 

二、快速排序的详细描述

    首先在要排序的区域a 中选取一个基准值,而后将区域分成两个分区,其中左分区 b 中的元素均小于或者等于基准值,右分区 c 的元素 均大于或者等于中轴值,而后通过递归调用快速排序的过程分别对两个分区再次进行排序,最后将两个分区产生的结果合并即可得到最后的排序序列。

  “基准值”的选择有很多种方法。最简单的是使用分区中第一个元素值。但是如果输入的数组是正序或者逆序的,就会将所有的记录分到“基准值”的一边。较好的方法是随机选取“基准值”,这样可以减少原始输入对排序造成的影响。但是随机选取“基准值”的开销大。

 

三、快速排序的算法思想

   为了实现一次划分,我们可以从数组(假定数据是存在数组中)的两端移动下标,必要时交换记录,直到数组两端的下标相遇为止。为此,我们附设两个指针(下标)i 和 j, 先通过 j 从当前区域的右端向左扫描,越过大于等于基准值的记录。当遇到小于基准值的记录时,扫描停止。然后,通过 i 从当前区域的左端向右扫描,越过小于基准值的记录。当遇到大于等于基准值的记录时,扫描停止。交换两个方向扫描停止的记录 a[j] 与 a[i]。 然后,继续扫描,直至 i 与 j 相遇为止,本轮扫描和交换的过程结束。这时i左边的记录的关键字值都小于基准值,右边的记录的关键字值都大于等于基准值。

最后,当前下标i=j,交换规则使得下标i左边的元素值一定会小于等于基准值,i右边元素值一定会大于等于基准值。所以最后一步是将当前i下标元素值与基准值交换。完成一轮快排,递归,同样对子分区进行操作,直至快排结束。

 通过两个不相邻元素交换,可以一次交换消除多个逆序,加快排序速度。快速排序方法在要排序的数据已经有序的情况下最不利于发挥其长处。

 

四、快速排序的核心算法

quickSort(int left,int right){    int i = left;    int j = right;    int temp=a[left];    int t;    while(i!=j){	//①当i与j没有相遇的时候,执行移动查找        while(j>i && a[j]>=temp){            j--;    	//②略过大于等于基准值的下标        }		//③当找到小于基准值,j下标停止移动        while(i

五、快速排序源码实现

package sort;public class QuickSort {    private static int[] a = {6,1,2,7,9,3,4,5,10,8};    public static void main(String[] args){        System.out.println("原数组值:");        for (int i : a) {            System.out.print(i+" ");        }        System.out.println();        quickSort(0, a.length-1);    }    public static void quickSort(int left,int right){        int i,j,temp;        if(left>right){            return;        }        temp=a[left]; //temp中存的就是基准数        i=left;        j=right;        while(i!=j){            //顺序很重要,要先从右边开始找 ,直到找到一个小于基准的值            while(a[j]>=temp && i
j+1){ quickSort(i+1,right);//继续处理右边的 ,这里是一个递归的过程 } }}

 

六、结果值查看

原数组值:6 1 2 7 9 3 4 5 10 8 交换值后:6 1 2 5 9 3 4 7 10 8 交换值后:6 1 2 5 4 3 9 7 10 8 基准值归位后:3 1 2 5 4 6 9 7 10 8 基准值归位后:2 1 3 5 4 6 9 7 10 8 基准值归位后:1 2 3 5 4 6 9 7 10 8 基准值归位后:1 2 3 4 5 6 9 7 10 8 交换值后:1 2 3 4 5 6 9 7 8 10 基准值归位后:1 2 3 4 5 6 8 7 9 10 基准值归位后:1 2 3 4 5 6 7 8 9 10 

 

转载地址:https://blog.csdn.net/qq_38741971/article/details/81661144 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:排序算法概述
下一篇:二十三、Oracle学习笔记:综合案例

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月03日 16时20分37秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python房价数据分析波士顿代码数据_python数据分析-波士顿房价预测-Go语言中文社区... 2019-04-21
redis线程阻塞原因排插_Redis阻塞原因详解 2019-04-21
labview自动保存报表_基于LabVIEW的Excel报表的自动生成功能 2019-04-21
geotool 导出shp_Java 读取shape文件 2019-04-21
mysql 关联更新_MySQL UPDATE多表关联更新 2019-04-21
mysql call_mysql的call用法 call调用函数的例子 2019-04-21
python参数验证_参数验证,Python中的最佳实践 2019-04-21
python画多层网络_在pymn中修改多层网络图 2019-04-21
java net 安卓_android -------- java.net.UnknownServiceException 2019-04-21
java 密钥 aes 解密_Java中AES加密解密以及签名校验 2019-04-21
java树转化成图_Java 转换一组数据为树型数据 2019-04-21
java 底层ppt_Java 如何设置 PPT 中的形状排列方式 具体内容 2019-04-21
mysql service5.7_Mysql5.7服务下载安装 2019-04-21
mysql查看线程完整执行命令_MySQL-查看运行的线程-SHOW PROCESSLIST 2019-04-21
mysql 更新数据 字符串_批量替换 MySQL 指定字段中的字符串 2019-04-21
web开发 mysql安装_mysqlinstallerwebcommunity5.7.21.0.msi安装图文教程 2019-04-21
mysql concat 整数型_MySQL 数字类型转换函数(concat/cast) 2019-04-21
mysql单元格函数是_MySQL常用内置函数 2019-04-21
mysql 怎么字段分裂_你可以分裂/爆炸MySQL查询中的字段吗? 2019-04-21
mysql server卸载出错_Mysql卸载问题Start Server卡住报错解决方法 2019-04-21