A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 何创 中级黑马   /  2012-10-29 11:01  /  1737 人查看  /  7 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

JAVA中 快速排序,最好可以代码举例说明下,新手,不懂快速排序,最近看的排序,挺晕。

评分

参与人数 1技术分 +1 收起 理由
韩军博 + 1 神马都是浮云

查看全部评分

7 个回复

倒序浏览
本帖最后由 丁桂松 于 2012-10-29 11:15 编辑

占搂,等代码!
回复 使用道具 举报
本帖最后由 丁桂松 于 2012-10-29 11:08 编辑


快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边
数列进行排序,而影响快速排序法效率的正是轴心的选择。

解法这边所介绍的快速演算如下:将最左边的数设定为轴,并记录其值为 s
廻圈处理:
令索引 i 从数列左方往右方找,直到找到大于 s 的数
令索引 j 从数列左右方往左方找,直到找到小于 s 的数
如果 i >= j,则离开回圈
如果 i < j,则交换索引i与j两处的值
将左侧的轴与 j 进行交换
对轴左边进行递回
对轴右边进行递回
透过以下演算法,则轴左边的值都会小于s,轴右边的值都会大于s,如此再对轴左右两边进行
递回,就可以对完成排序的目的,例如下面的实例,*表示要交换的数,[]表示轴:
[41] 24 76* 11 45 64 21 69 19 36*
[41] 24 36 11 45* 64 21 69 19* 76
[41] 24 36 11 19 64* 21* 69 45 76
[41] 24 36 11 19 21 64 69 45 76
21 24 36 11 19 [41] 64 69 45 76
在上面的例子中,41左边的值都比它小,而右边的值都比它大,如此左右再进行递回至排序完
成。

评分

参与人数 1技术分 +1 收起 理由
韩军博 + 1 很给力!

查看全部评分

回复 使用道具 举报
最快的排序是希尔排序,但是一般不常用,把常用的:选择排序、冒泡排序弄明白就差不多了。
回复 使用道具 举报
这是冒泡排序,你可以参考下
public class Test1 {
        /*
         *  已知一个int类型的数组,用冒泡排序法将数组中的元素进行排列。
         * */
        public static void main(String[] args) {
       
                int[] a = {4,5,7,0,-2,9,1,1};
                bubbleSort(a);
                for(int i=0;i<a.length-1;i++){
                        System.out.print(a[i]);
                }
        }
       
        //循环里面的每一元素,让他们互相比较
        private static void bubbleSort(int[] source) {
                for(int i=source.length-1; i>0; i--){
                        for(int j=0; j<i; j++){
                                if(source[j]>source[j+1]){
                                        swap(source, j, j+1);
                                }
                        }
                }               
        }
       
        //对于满足source[j]>source[j+i]条件的互相交换位置
        private static void swap(int[] source, int x, int y) {
                int temp ;
                temp = source[x];
                source[x] = source[y];
                source[y] = temp;                               
        }
}

评分

参与人数 1技术分 +1 收起 理由
韩军博 + 1 很给力!

查看全部评分

回复 使用道具 举报
丁桂松 发表于 2012-10-29 11:05
快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二,分别对左边与右边
数列进行排序,而 ...

你说的,我貌似没搞懂。。更晕了。
回复 使用道具 举报
其实对于快排,二楼说得差不多了
块排的话就是快速的排序,速度很快(当然指的是平均速度),而冒泡,选择等,则相对慢很多。
说下块排的最简单实现方法:
1:从一个数组中取出第一个数字(理论上随便取,为了便于理解),放到一个新的数组里。
2:从第二个数字开始依次取出,和这个数字做比较,比它小得,放在它左边,比他大的放在它右边(这样它左边的数都是比它小的数字,而它右边的数则都是比它大的数字);
3:把左边(和右边)这半部分各取出第一个数,再放到一个数组中,拿左边所有数字和它比较,大的放左边,小的放右边
4:一直这么取下去...直到最后只有两个数字的时候,比一下,则全部有序了

譬如数组 a 中是 :       8    4     9     6      3       5       12
取出 8              :             8                       把    4     9     6      3       5       12  着几个数字和它依次比较  得到结果 :   4          6        3        5       8       9      12(可以看到,前面全部是比8 小的,后面全部是比8 大的)
4          6        3        5     和     9      12   取出第一个数字,进行排序:  则前半部分结果为:        3      4       6      5     后面两个 为     9    12   (这样后半部分排序就完成了) 现在的数组情况是  3      4       6      5      8      9     12
再看  4 前面是 3 只有一个数字,那也肯定是已经有序了(因为我们已经拿3和4 比较过了,因为比它小才放它前面的)。     4后面是6    5,那取出  6  ,把5 和6 进行比较, 6>5 当然 所有需要比较的都已经比较完了,最后正确的结果也已经出来了。 结果是:3  4  5  6  8  9  12






回复 使用道具 举报
看完思路(思路需要自己慢慢看,一步一步理解了往下看,不要着急,不然搞得头昏的  ps 下面的序号忘了标了),
我说下写法:首先这样的实现方式肯定是用递归无疑了,递归函数的参数应该有这个数组,数组的第一个元素下表和数组最后一个元素下标
递归的出口是 第一个元素下标等于或者大于最后一个元素的下标(自己好好想一下,如果递归不会用的话好好看一看递归怎么用)
希望你已经能理解了,另外,我真的很渴望技术分呀,哈哈哈
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马