黑马程序员技术交流社区

标题: 想问一个关于排序的问题，新手。 [打印本页]

---

作者: 何创    时间: 2012-10-29 11:01
标题: 想问一个关于排序的问题，新手。
JAVA中 快速排序，最好可以代码举例说明下，新手，不懂快速排序，最近看的排序，挺晕。

---

作者: 丁桂松    时间: 2012-10-29 11:05


占搂,等代码!

---

作者: 丁桂松    时间: 2012-10-29 11:05



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

解法这边所介绍的快速演算如下：将最左边的数设定为轴，并记录其值为 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左边的值都比它小，而右边的值都比它大，如此左右再进行递回至排序完
成。

---

作者: 周万谋    时间: 2012-10-29 11:12
最快的排序是希尔排序，但是一般不常用，把常用的：选择排序、冒泡排序弄明白就差不多了。

---

作者: 罗力    时间: 2012-10-29 14:14
这是冒泡排序，你可以参考下
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;                               
        }
}

---

作者: 何创    时间: 2012-10-29 21:58

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

你说的，我貌似没搞懂。。更晕了。

---

作者: xuchulong1    时间: 2012-10-29 22:34
其实对于快排，二楼说得差不多了
块排的话就是快速的排序，速度很快（当然指的是平均速度），而冒泡，选择等，则相对慢很多。
说下块排的最简单实现方法：
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

---

作者: xuchulong1    时间: 2012-10-29 22:43
看完思路（思路需要自己慢慢看，一步一步理解了往下看，不要着急，不然搞得头昏的  ps 下面的序号忘了标了），
我说下写法：首先这样的实现方式肯定是用递归无疑了，递归函数的参数应该有这个数组，数组的第一个元素下表和数组最后一个元素下标
递归的出口是 第一个元素下标等于或者大于最后一个元素的下标（自己好好想一下，如果递归不会用的话好好看一看递归怎么用）
希望你已经能理解了，另外，我真的很渴望技术分呀，哈哈哈

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2