一、简单步骤（数字从左向右依次递增）

1. 找出主元，可以是任意元素，这里总是选择最后一个最为主元

2. 从左向右依次查找，比主元小的放到左侧

3. 当查找到末尾后，主元与左侧小于主元的下一个数字交换。

这样得到一个主元左侧都比主元小，相反右侧都大于主元

二、实现代码

1. public class QuickSort {
3. public static void main(String[] args) {
4. int[] arr = {6, 9, 2, 5, 8, 6};
6. QuickSort quickSortSample = new QuickSort();
7. quickSortSample.quickSort(arr, 0, arr.length-1);
9. for (int j = 0; j < arr.length; j++) {
10. System.out.print( + arr[j]);
11. }
12. }
14. public void quickSort(int data[], int start, int end) {
15. if (start < end) {
16. int partitionIndex = partition(data, start, end);
17. quickSort(data, start, partitionIndex-1);
18. quickSort(data, partitionIndex+1, end);
19. }
20. }
22. public int partition(int data[], int start, int end) {
23. int key = data[end]; // 以最后一个元素，data[hi]为主元
24. int i = start -1 ;
25. for (int j = start; j < end; j++) {
26. if (data[j] <= key) {
27. i = i + 1;
28. swap(data, i, j);
29. }
30. }
31. swap(data, i+1, end);
33. return i+1;
34. }
36. private void swap(int data[] , int i, int j) {
37. int temp = data[i];
38. data[i] = data[j];
39. data[j] = temp;
40. }
42. }

    三、逐步演示

    6, 9, 2, 5, 8, 6

    
    

    当前指向位置	交换的判断条件	交换后的数组
    i = 0, j = 0	6 <= 6	6 9 2 5 8 6
    i = 1, j = 2	2 <= 6	6 2 9 5 8 6
    i = 2, j = 3	5 <= 6	6 2 5 9 8 6
    i = 3	i之前都主元6小	6 2 5 6 8 9

    
    
    

    当前指向位置	交换的判断条件	交换后的数组
    i = 0, j = 1	2 <= 5	2 6 5 6 8 9
    i = 1	i之前都主元5小	2 5 6 6 8 9

    
    
    

    当前指向位置	交换的判断条件	交换后的数组
    i = 4, j = 4	8 <= 9	2 5 6 6 8 9
    i = 5	i之前都主元9小	2 5 6 6 8 9

    
    
    
    

    四、参考资料

    WIKI - 排序算法 http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
    白话经典算法系列之六 快速排序 快速搞定 http://blog.csdn.net/morewindows/article/details/6684558
    快速排序算法 http://blog.csdn.net/v_JULY_v/article/details/6116297
    十二之续、快速排序算法的深入分析 http://blog.csdn.net/v_july_v/article/details/6211155
    十二之再续：快速排序算法之所有版本的c/c++实现 http://blog.csdn.net/v_july_v/article/details/6262915