文档章节

基本算法--快速排序

阿信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

粉丝 222
博文 80
码字总数 70802
作品 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
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

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

yinwenjie
2017/06/06
0
0
各种排序算法分析与比较

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

长平狐
2013/12/25
178
0
面试三 : 快速排序

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

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

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

长平狐
2013/01/06
75
0

没有更多内容

加载失败,请刷新页面

加载更多

React 服务器渲染原理解析与实践

网盘下载地址 React 服务器渲染原理解析与实践 本套课程,讲解了React中SSR技术的整个搭建思路及流程,完整的从原理上讲清楚了SSR的概念,重点在于讲解编写SSR框架遇到的各种知识点,以及细节...

qq__2304636824
41分钟前
0
0
Jenkins使用

clean install -Dmaven.test.skip=true

1713716445
50分钟前
0
0
多线程

1. 多线程概念。并发和并行的概念。 多线程指的是一段时间内cpu同时执行多个线程。一个程序至少运行>=1个进程,进程就是运行中的程序,而一个进程至少运行>=1个线程,线程是操作系统能调度的...

鱼想吃肉
今天
1
0
HBase 表修复在线方式和离线方式

一、在线修复 1.1 使用检查命令 $ ./bin/hbase hbck 该命令可完整修复 HBase 元数据信息;存在有错误信息会进行输出; 也可以通过如下命令查看详细信息: $ ./bin/hbase hbck -details 1.2 ...

Ryan-瑞恩
今天
3
0
redis 系列二 -- 常用命令

1.基础命令 info ping quit save dbsize select flushdb flushall 2.键命令 2.1 set 直接赋值 set a a 2.2 get 取值 get a 2.3 exists 是否存在 exists a 2.4 expire 设置剩余时间 秒 expire......

imbiao
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部