文档章节

基本算法--快速排序

阿信sxq
 阿信sxq
发布于 2016/05/10 10:41
字数 312
阅读 106
收藏 3

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

    /**
     *
     * @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

粉丝 226
博文 82
码字总数 72407
作品 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
266
0
各种排序算法分析与比较

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

长平狐
2013/12/25
271
0
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

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

yinwenjie
2017/06/06
0
0
面试三 : 快速排序

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

botaorain
2014/09/25
0
0
各种基本算法实现小结(六)—— 查找算法

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

长平狐
2013/01/06
109
0

没有更多内容

加载失败,请刷新页面

加载更多

iOS分段选择器、旅行App、标度尺、对对碰小游戏、自定义相册等源码

iOS精选源码 企业级开源项目,模仿艺龙旅行App 标签选择器--LeeTagView CSSegmentedControl常用的分段选择器,简单易用! 仿微信左滑删除 IOS左滑返回 输入框 iOS 基于PhotoKit框架的自定义相...

Android爱开源
16分钟前
0
0
浅谈 Java JPDA

本文首发个人公众号《andyqian》,期待你的关注~ 前言 程序员在坊间有非常多有趣的故事,其中就有这么一则:”这个在我的电脑上是好的,没问题的呀,诺,你看咯,一定是你打开姿势不正确,浏...

andyqian
22分钟前
39
1
人工智能可以跳出动感的跳舞视频

非常热门的人工智能技术目前正在快速的发展,与此同时越来越多人工智能应用也开始出现在我们的生活中。 此前有开发者利用谷歌开源免费的卷积神经网络工具,将色情影片中的人物换成明星并达到...

linux-tao
25分钟前
0
0
离线批量数据通道Tunnel的最佳实践及常见问题

基本介绍及应用场景 Tunnel是MaxCompute提供的离线批量数据通道服务,主要提供大批量离线数据上传和下载, 仅提供每次批量大于等于64MB数据的场景,小批量流式数据场景请使用DataHub实时数据...

阿里云云栖社区
25分钟前
0
0
git reset放弃修改&放弃增加文件

1. 本地修改了一堆文件(并没有使用git add到暂存区),想放弃修改。 单个文件/文件夹: $ git checkout -- filename 所有文件/文件夹: $ git checkout . 2. 本地新增了一堆文件(并没有git a...

JamesView
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部