Java-快速排序

浏览数：24 / 时间：2015年06月08日

一、快速排序的原理

使用分治算法进行快速排序，以最后一个元素为标识，然后从头开始遍历，把比这个标识小的元素全部放在左边，把比这个标识大的元素全部放在右边，最后就用这个标识将数组分成了两个部分，然后再分别对标识的前后部分的数组继续进行排序，如此下去就能得到排好序的数组。

二、快速排序的伪代码实现

 1 QUICKSORT(A, p, r)  
 2  if p < r  
 3     then q ← PARTITION(A, p, r)  
 4          QUICKSORT(A, p, q - 1)  
 5          QUICKSORT(A, q + 1, r)  
 6 PARTITION(A, p, r)  
 7   x ← A[r]  
 8   i ← p - 1  
 9   for j ← p to r - 1  
10        do if A[j] ≤ x  
11              then i ← i + 1  
12              exchange A[i] ←→ A[j]  
13   exchange A[i + 1] ←→ A[r]  
14   return i + 1

三、快速排序的Java代码实现

 1 import java.util.Comparator;
 2 
 3 
 4 public class QuickSort {
 5     
 6     public static <T> void quickSort(T[] t, int p, int r, Comparator<? super T> c){
 7         if(p < r-1){
 8             int q = partition(t, p, r, c);
 9             quickSort(t, p, q, c);
10             quickSort(t, q+1, r, c);
11             
12         }
13     }
14     public static <T> int partition(T[] t, int p, int r, Comparator<? super T> c){
15         T x = t[r-1];
16         int i = p-1;
17         for(int j = p; j < r-1; j ++){
18             if(c.compare(t[j], x) < 0){
19                 i = i + 1;
20                 T temp = t[i];
21                 t[i] = t[j];
22                 t[j] = temp;
23             }
24         }
25         T temp = t[i+1];
26         t[i+1] = t[r-1];
27         t[r-1] = temp;
28         return i + 1;        
29     }
30     
31     public static <T> void quickSort(T[] t, Comparator<? super T> c){
32         quickSort(t, 0, t.length, c);
33     }
34     
35     public static void main(String[] args){
36         //在这里进行代码测试
37         Integer[] ints = new Integer[]{2, 0, 5, 23, 1, 4, 8, 56, 19};
38         quickSort(ints, new Comparator<Integer>(){
39             public int compare(Integer o1, Integer o2){
40                 return o1-o2;
41             }
42         }); 
43         
44         for(int i = 0; i < ints.length; i ++){
45             System.out.print(ints[i] + " ");
46         }
47     }
48 }