文档章节

基本算法--快速排序

阿信sxq
 阿信sxq
发布于 2016/05/10 10:41
字数 312
阅读 106
收藏 3
点赞 2
评论 1

原理:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描, 将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素, 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

    /**
     *
     * @author 阿信sxq-2015年7月16日
     *
     * @param args
     */
    public static void main(String[] args) {
        int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4,
                62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
        if (a.length > 0) {//查看数组是否为空    
            _quickSort(a, 0, a.length - 1);
        }
        System.out.println(Arrays.toString(a));

    }

    public static void _quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int low = left;
        int high = right;
        int tmp = arr[low];//数组的第一个作为中轴    
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];//比中轴小的记录移到低端    

            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];//比中轴大的记录移到高端    
        }
        arr[low] = tmp;//中轴记录到尾    
        _quickSort(arr, left, low - 1);//对低字表进行递归排序    
        _quickSort(arr, low + 1, right);//对高字表进行递归排序    
    }

 

© 著作权归作者所有

共有 人打赏支持
阿信sxq

阿信sxq

粉丝 214
博文 80
码字总数 70640
作品 1
成都
后端工程师
加载中

评论(1)

tangqinchao
tangqinchao
阿信分析下这个版本呢 https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F#Java
【源码共享】快速排序算法的几种实现方式

快速排序算法的基本特性 时间复杂度:O(nlgn) 最坏:O(n^2) 空间复杂度:O(nlgn) 不稳定。 快速排序是一种排序算法,对包含n个数的输入数组,平均时间为O(nlgn),最坏情况是O(n^2)...

Master_Li ⋅ 2016/10/08 ⋅ 0

线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie ⋅ 2017/06/06 ⋅ 0

各种排序算法分析与比较

首先,请允许我用这样的题目来作为本博文的题目,但是目前也想不到其他好的题目,所以就先定为这个题目吧。 排序算法对于数据结构和算法课程来说都是非常重要的内容,在数据结构中,排序算法...

长平狐 ⋅ 2013/12/25 ⋅ 0

面试三 : 快速排序

今天我们看看快速排序,其实我们是在大二上学期上的数据结构,现在基本上忘的差不多了,最近这两年一直在做应用,所以这个面试官给我敲响了警钟,虽然说我面试的结果不怎么样,但是我的收获还...

botaorain ⋅ 2014/09/25 ⋅ 0

各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(六)—— 查找算法 (均已测试通过) =================================================================== 1、简单查找 在一组无序数列中,查找特定某个数值,并返...

长平狐 ⋅ 2013/01/06 ⋅ 0

快排序和堆排序,最小堆、最大堆

1)分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(箱排序、基数排序) 所需辅助空间最多...

hanzhankang ⋅ 2014/01/18 ⋅ 0

php四种基础算法:冒泡,选择,插入和快速排序法

许多人都说 算法是程序的核心,一个程序的好于差,关键是这个程序算法的优劣。作为一个初级phper,虽然很少接触到算法方面的东西 。但是对于冒泡排序,插入排序,选择排序,快速排序四种基本算...

PHP86 ⋅ 2013/12/21 ⋅ 0

java 快排的思路与算法

java 快排的思路与算法 有时候面试的时候的会问道Arrays.sort()是怎么实现的,我以前根本不知道是什么东西,最近点进去看了一下。直接吓傻, //看到这个时候还是比较淡定的,可怕的事情来了。...

年少爱追梦 ⋅ 2016/03/07 ⋅ 0

【scala数据结构和算法】Scala实现:快速排序

算法思想: 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法...

赖德发的博客 ⋅ 2017/12/19 ⋅ 0

java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯 ⋅ 06/05 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

中标麒麟(龙芯版)7.0优盘安装

########################################## 制作U盘安装盘: 1.准备U盘: PMON环境下U盘必须格式化成ext3; 昆仑固件环境下可以格式化成ext3,ext4 2.把整个镜像 xxx.iso 复制到U盘下面 3....

gugudu ⋅ 10分钟前 ⋅ 0

老司机写的大数据建模五步走

本文将尝试来梳理一下数据建模的步骤,以及每一步需要做的工作。 01 第一步:选择模型或自定义模式 这是建模的第一步,我们需要基于业务问题,来决定可以选择哪些可用的模型。 比如,如果要预...

gulf ⋅ 19分钟前 ⋅ 0

PacificA 一致性协议解读

PacificA 的 paper 在 08 年左右发出来的,比 Raft 早了 6,7 年。 在 PacificA 论文中,他们强调该算法使用范围是 LAN (Local Area Network),讲白了就是对跨机房不友好。 不管是 ZAB,Raf...

黑客画家 ⋅ 21分钟前 ⋅ 0

盘符图标个性化

设置自己的专属盘符图标 准备ico格式的图片文件一个,在根目录下创建autorun.inf文件 文件内容 [Autorun]icon=logo.ico 重新启动或者插拔U盘即可看到结果...

阿豪boy ⋅ 22分钟前 ⋅ 0

Windows下QQ聊天记录中图片的默认存放位置

Windows下QQ聊天记录中图片的默认存放位置在设置中是没有说明的。 实测位置在:D:\Documents\Tencent Files\974101467\Image 其中: “974101467”为对应的QQ号; “C2C”为个人之间的聊天图...

临江仙卜算子 ⋅ 28分钟前 ⋅ 0

GC 的三种基本实现方式

参考资料《代码的未来》(作者: [日] 松本行弘)。 由于并非本人原著(我只是个“搬运工“),SO 未经本人允许请尽情转载。 另外个人像说明一下这里所说的GC指泛指垃圾回收机制,而单指Jav...

xixingzhe ⋅ 29分钟前 ⋅ 0

Android双击退出

/** * 菜单、返回键响应 */ @Override public boolean onKeyDown(int keyCode, KeyEvent event) { // TODO Auto-generated method stub if(keyCode......

王先森oO ⋅ 33分钟前 ⋅ 0

idea 整合 vue 启动

刚学习Vue 搭建了一个项目 只能命令启动 Idea里面不会启动 尝试了一下修改启动的配置 如下: 1.首先你要保证你的package.json没有修改过 具体原因没有看 因为我改了这个name的值 就没办法启动...

事儿爹 ⋅ 39分钟前 ⋅ 0

redis在windows环境的后台运行方法

在后台运行,首先需要安装redis服务,命令为 redis-server.exe --service-install redis.windows.conf --loglevel verbose 启动,命令为 redis-server --service-start 停止,命令为 redis-...

程序羊 ⋅ 42分钟前 ⋅ 0

比特币现金开发者提出新的交易订单规则

本周,四位比特币现金的四位开发者和研究员:Joannes Vermorel(Lokad),AmaurySéchet(比特币ABC),Shammah Chancellor(比特币ABC)和Tomas van der Wansem(Bitcrust)共同发表了一篇关...

lpy411 ⋅ 46分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部