本人独立域名One Coder博客：http://www.coderli.com

转载请务必注明出处：One Coder - http://www.coderli.com/archives/quick-sort

1. package lhz.algorithm.chapter.seven; 
2. /** 
3.  * 快速排序，《算法导论》第七章 
4. * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/747858
5.  * @author lihzh(苦逼coder) 
6.  */ 
7. public class QuickSort { 
8.      
9.     //待排数组 
10.     private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 }; 
11.  
12.     public static void main(String[] args) { 
13.         //快速排序 
14.         quickSort(input, 0, input.length - 1); 
15.         //打印数组 
16.         printArray(); 
17.     } 
18.      
19.     /** 
20.      * 快速排序，伪代码： 
21.      * QUICKSORT(A, p, r) 
22.      * 1 if p < r 
23.      * 2    then q ← PARTITION(A, p, r) 
24.      * 3        QUICKSORT(A, p, q - 1) 
25.      * 4        QUICKSORT(A, q + 1, r) 
26.      *  
27.      * PARTITION(A, p, r) 
28.      * 1 x ← A[r] 
29.      * 2 i ← p - 1 
30.      * 3 for j ← p to r - 1 
31.      * 4    do if A[j] ≤ x 
32.      * 5        then i ← i + 1 
33.      * 6            exchange A[i] ↔ A[j] 
34.      * 7 exchange A[i + 1] ↔ A[r] 
35.      * 8 return i + 1 
36.      * 复杂度，最坏情况下：Θ(n^2) 
37.      * 一般平衡情况：Θ(nlgn) 
38.      * @param array 待排数组 
39.      * @param from 起始位置 
40.      * @param to 终止位置 
41.      */ 
42.     private static void quickSort(int[] array, int from, int to) { 
43.         if (from < to) { 
44.             int temp = array[to]; 
45.             int i = from - 1; 
46.             for (int j = from; j < to; j++) { 
47.                 if (array[j] <= temp) { 
48.                     i++; 
49.                     int tempValue = array[j]; 
50.                     array[j] = array[i]; 
51.                     array[i] = tempValue; 
52.                 } 
53.             } 
54.             array[to] = array[i+1]; 
55.             array[i+1] = temp; 
56.             quickSort(array, from, i); 
57.             quickSort(array, i + 1, to); 
58.         } 
59.     } 
60.  
61.     private static void printArray() { 
62.         for (int i : input) { 
63.             System.out.print(i + " "); 
64.         } 
65.     } 
66. } 

  本人独立域名One Coder博客：http://www.coderli.com

转载请务必注明出处：One Coder - http://www.coderli.com/archives/quick-sort

     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/747858，如需转载请自行联系原作者