数据结构与算法(23): 排序- 快速排序

发表于   |   分类于

  快速排序的基本思想：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程递归进行，以达到有序序列。

快速排序的每一轮处理其实就是将一轮的基准数归位。

  时间复杂度：O($N\log{N}$)。
  空间复杂度：O($\log{N}$) ~ O($N$)。（递归调用，栈空间）
  快速排序是不稳定的。

partition函数用来解决这样一个问题：给定一个数组data[]和数组中任意一个元素a，重排数组使得a左边都小于它，右边都不小于它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class QuickSort {
    public static void main(String[] args) {
        int[] data1 = new int[]{1,2,8,9,4,5,6,7};
        int[] data2 = new int[]{8,4,5,9,6,2,1,7};
        QuickSort sort = new QuickSort();
        sort.quickSort(data1, 0 , data1.length-1);
        sort.quickSort(data2, 0 , data2.length-1);
        
        print(data1);
        print(data2);
    }
    
    public void quickSort(int[] data, int start ,int end){
        if (start >= end)
            return;
		// pivotIndex可以取随机数
        // int index = partition1(data, start, end, end);
        int index = partition2(data, start, end, end);
        if (index > start)
            quickSort(data, start, index - 1);
        if (index < end)
            quickSort(data, index + 1, end);
    }
    
    private int partition1(int[] data, int start, int end, int pivotIndex){
        int pivot = data[pivotIndex];
        swap(data, pivotIndex, end);
        int small = start;
        for(int i = start; i < end; ++i) {
            if(data[i] < pivot) {
                if(small != i){
                    swap(data, i, small);
                }
                ++small;
            }
        }
        // 基数归位
        swap(data, small, end);
        return small;
    }
    
    private int partition2(int[] data, int start, int end, int pivotIndex){
        int small = start;
        int large = end;
        int pivot = data[pivotIndex];
        swap(data, end, pivotIndex);
        while (small != large){
            while (data[small] <= pivot && small < large)
                small++;
            while (data[large] >= pivot && small < large)
                large--;
            
            if (small < large)
                swap(data, small, large);
        }
        
        // 基数归位
        swap(data, end, small);
        return small;
    }
    
    private void swap(int[] data, int i, int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
    
    private static void print(int[] data){
        for (int i: data){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

感谢:http://www.cnblogs.com/skywang12345/p/3596746.html