黑马程序员技术交流社区

标题: 整理了一些排序方法，高手勿喷（3） [打印本页]

---

作者: wojiaojay    时间: 2014-5-6 19:55
标题: 整理了一些排序方法，高手勿喷（3）
6. 快速排序

快速排序也是用归并方法实现的一个“分而治之”的排序算法，它的魅力之处在于它能在每次partition（排序算法的核心所在）都能为一个数组元素确定其排序最终正确位置（一次就定位准，下次循环就不考虑这个元素了）。

快速排序的partition操作按以下逻辑进行，假定本次排序的数组为arr：

1） 选择一个元素（为了简单起见，就选择本次partition的第一个元素，即arr[0]）作为基准元素，接下来的步骤会为其确定排序完成后最终的位置；

2） 1）  接下来需要遍历[1…n-1]对应的数组元素以帮助找到arr[0]值（以v替代）对应的位置，定义i为当前访问数组的索引，lt为值小于v的最大索引，gt为值大于v的最小索引，那么在遍历过程中，如果发现i指向的值与v相等，则将i值加1，继续下一次比较；如果i指向的值比v小，则将i和lt对应的元素进行交换，然后分别将两个索引加1；如果i指向的值比v大，则将i与gt对应的元素进行交换，然后i自增，gt自减。循环遍历完成（i > gt时结束）之后可以保证[0…lt-1]对应的值都是比v小的，[lt..gt]之间的值都是与v相等的，[gt+1…n-1]对应的值都是比v大的。

3） 分别对[0…lt-1]和[gt+1…n-1]两个子数组进行排序，如此递归，直至子子子数组的长度为0。



下面举个partition的具体实例：

初始（i = 1, lt = 0, gt = 8）：

       [41, 59, 43, 26, 63, 30, 29, 26, 42]（需要确定位置的为0th[41]）

第一趟（i = 1, lt = 0, gt = 8）：

       [41, 42, 43, 26, 63, 30, 29, 26, 59]（1st[59] > 41，1st[59]<->8th[42]，gt--）

第二趟（i = 1, lt = 0, gt = 7）：

       [41, 26, 43, 26, 63, 30, 29, 42, 59]（1st[42] > 41，1st[42]<->7th[26]，gt--）

第三趟（i = 1, lt = 0, gt = 6）：

       [26, 41, 43, 26, 63, 30, 29, 42, 59]（1st[26] < 41, 1st[26]<->0st[41]，i++, lt++）

第四趟（i = 2, lt = 1, gt = 6）：

       [26, 41, 29, 26, 63, 30, 43, 42, 59]（2nd[43] > 41，2nd[43]<->6th[29]，gt--）

第五趟（i = 2, lt = 1, gt = 5）：

       [26, 29, 41, 26, 63, 30, 43, 42, 59]（2nd[29] < 41, 2nd[29]<->1st[41]，i++，lt++）

第六趟（i = 3, lt = 2, gt = 5）：   

       [26, 29, 26, 41, 63, 30, 43, 42, 59]（3rd[26] < 41，3rd[26]<->2nd[41]，i++，lt++）

第七趟（i = 4, lt = 3, gt = 5）：

       [26, 29, 26, 41, 30, 63, 43, 42, 59] （4th[63] > 41，4th[63]<->5th[30]，gt--）

第八趟（i = 4, lt = 3, gt = 4）：   

       [26, 29, 26, 30, 41, 63, 43, 42, 59]（4th[30] < 41，4th[30]<->3rd[41]，i++，lt++）


可以看出，在一次partition之后，以41为分割线，41左侧皆为比它小的元素，41右侧皆为比它大或相等的元素（当然这个实例比较特殊，没有出现和41相等的元素）。快速排序顾名思义就是排序速度非常快，后面我会放在我机器上跑各个排序方法的时间对比图。值得一提的是JDK中在Arrays工具内中内置的sort方法就是接合插入排序和三路快速排序实现的，有兴趣的同学可以看看JDK的源码。


实现代码：



Java代码  收藏代码
/**
* Quick Sorting
*/  
QUICK(new Sortable() {  
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {  
        this.sort(array, 0, array.length - 1, ascend);  
    }  

    private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {  
        if (lo >= hi) {  
            return;  
        }  

        T toFinal = array[lo];  
        int leftIdx = lo;  
        int rightIdx = hi;  

        int i = lo + 1;  

        while (i <= rightIdx) {  
            int compare = array.compareTo(toFinal);  
            if (compare == 0) {  
                i++;  
            } else if (compare < 0 == ascend) {  
                exchange(array, leftIdx++, i++);  
            } else {  
                exchange(array, rightIdx--, i);  
            }  
        }  

        // partially sort left array and right array  
        // no need to include the leftIdx-th to rightIdx-th elements  
        // since they are already in its final position  
        sort(array, lo, leftIdx - 1, ascend);  
        sort(array, rightIdx + 1, hi, ascend);  
    }  
}
一篇文章里放不下，只能分3次发了，为啥有10000字节限制......:dizzy:

---

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

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