是从大话数据结构这本书里学习到的算法，书上是用C语言写的，我自己用java实现了一下，加了不少注释。快排的的基本思想是：通过一趟排序将待排的记录划分为独立的两部分，其中一部分记录的关键字均不大于另一部分记录的关键字，然后再分别对这两部分记录继续进行快速排序，以达到整体有序。

1. public class SortTest {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] arr = {52,18,94,36,72,48,88,65,20};
   
5.                
   
6.                 printArray(arr);   
   
7.                 Sort.quickSort(arr);
   
8.                 printArray(arr);     
   
9.         }
   
10.       
    
11.         public static void printArray(int[] arr) {
    
12.                 System.out.print("[");
    
13.                 for(int x = 0; x < arr.length-1; x++) {
    
14.                         System.out.print(arr[x] + ",");
    
15.                 }
    
16.                 System.out.println(arr[arr.length-1] + "]");
    
17.         }
    
18. 
    
19. }
    
20. 
    
21. class Sort {
    
22.         //对整个数组进行快速排序
    
23.         public static void quickSort(int[] arr) {               
    
24.                 quickSort(arr, 0, arr.length-1);
    
25.         }
    
26.         
    
27.         //对数组[left...right]进行快速排序
    
28.         public static void quickSort(int[] arr, int left, int right) {
    
29.                 int pivot;
    
30.                 if(left < right) {      //若调用者传入的参数左指针比右指针大则不进行排序
    
31.                         pivot = getPivot(arr, left, right);  //调用getPivot方法获取分割高低两个数组的枢轴
    
32.                         quickSort(arr, left, pivot - 1);     //对低子数组进行递归快速排序
    
33.                         quickSort(arr, pivot + 1, right);         //对高子数组进行递归快速排序
    
34.                 }
    
35. 
    
36.         }
    
37. 
    
38.         private static int getPivot(int[] arr, int left, int right) {
    
39.                 //定义枢轴关键字为left所指的关键字
    
40.                 int pivotkey = arr[left];     
    
41.                 //当left和right不重合时执行循环
    
42.                 while(left < right) {         
    
43.                         //right向左搜索，然后交换左关键字和右关键字。
    
44.                         while(left < right && arr[right] >= pivotkey)
    
45.                                 right --;
    
46.                         swap(arr, left, right);
    
47.                         //right搜索完，left向右搜索，然后交换左右关键字。
    
48.                         while(left < right && arr[left] <= pivotkey)
    
49.                                 left ++;
    
50.                         swap(arr, left, right);
    
51.                 }
    
52.                 //left和right重合时，返回一个新的枢轴
    
53.                 return left;
    
54.                
    
55.         }
    
56.         private static void swap(int[] arr, int n1, int n2) {
    
57.                 int temp = arr[n1];
    
58.                 arr[n1] = arr[n2];
    
59.                 arr[n2] = temp;
    
60.         }        
    
61. }

复制代码

这个是传说中的二分排序？

121676463 发表于 2013-11-27 00:41
这个是传说中的二分排序？

就叫快速排序，quickSort，类库里的sort方法用的就是它，不过源码写得很牛逼，用了一大堆常量来分治。目前表示看不懂。