快速_排序

快速排序

总体说一下，我总结的实现快速排序有四种方法

• 第一种是最简单最容易上手的快速排序，很普通

• 第二种是我利用坑位法的第一种实现方式，实现快排

• 第三种是我利用坑位法的第二种实现方式，实现快排

  这两种都是利用坑位法实现比 nums[left]小的元素统统放到左边，比nums[left]大的放到右边，最后放完之后中间剩下的一个位置在用来放 nums[left]

  这两种坑位法在实现上略微差别，我的代码写的很清晰，可以参看一下

• 第三种我是利用双指针来实现上面说的那个逻辑

最后我想补充一下，其实还可以继续优化，代码我没有写出来，我说一下大概的优化逻辑，很简单。

我们每次找出key的时候，可以判断一下左边和右边剩余的元素还剩多少。

假如左边元素剩余的数量 <20 ,那么我们就不用快排了，直接可以使用选择排序，因为在数据量小的情况下，选择排序甚至比快速排序更快，当然这个20不是绝对的，可以根据自己的选择取调

写一下左边的实现，右边的逻辑一样

int key=partSort(nums,left,right);
if(key-1-left > 20){
	quickSort(nums,left,key-1);
}else{
    selectPlus(nums,left,key-left);
}
1
2
3
4
5
6

---

//快排①_最普通的实现方式
public static void quickSort_level_1(int[] nums,int left,int right){
    if(left>=right)return;

    int key=nums[left];
    int begin=left;
    int end=right;

    while(begin<end){
        while (begin<end && nums[end] >= key)end--;
        nums[begin]=nums[end];
        while(begin<end&&nums[begin]<=key)begin++;
        nums[end]=nums[begin];
    }

    //这一步最容易忘
    nums[begin]=key;

    quickSort_level_1(nums,begin+1,right);
    quickSort_level_1(nums,left,begin-1);
}

public static int getMidIndex(int[] nums,int left,int right){
    int mid=(left+right)>>2;
    if(nums[mid]>nums[left]){
        if(nums[mid]<nums[right])return mid;
        else if(nums[left]>nums[right])return left;
        return right;
    }else{
        if(nums[left]<nums[right])return left;
        else if(nums[mid]>nums[right])return mid;
        return right;
    }
}
//快排②_坑位法_1
public static int partSort2(int[] nums,int left,int right){
    int midIndex=getMidIndex(nums,left,right);
    swap(nums,midIndex,left);
    int begin=left;
    int end=right;
    int prive=left;
    int key=nums[left];
    while(begin<end){
        while (begin<end && nums[end]>=key){
            end--;
        }
        nums[prive]=nums[end];
        prive=end;
        while (begin<end&&nums[begin]<=key){
            begin++;
        }
        nums[prive]=nums[begin];
        prive=begin;
    }
    prive=begin;
    nums[prive]=key;
    return prive;
}
public static void quickSort_level_2(int[] nums,int left,int right){
    if(left>=right)return;

    int keyIndex=partSort2(nums,left,right);

    quickSort_level_2(nums,left,keyIndex-1);
    quickSort_level_2(nums,keyIndex+1,right);
}

//快排③_坑位法_2
public static int partSort3(int[] nums,int left,int right){
    int midIndex=getMidIndex(nums,left,right);
    swap(nums,midIndex,left);
    int begin=left;
    int end=right;
    int prev=left;
    int key=nums[left];
    while(begin<end){
        while(begin<end && nums[end]>=key){
            end--;
        }
        while (begin<end && nums[begin]<=key){
            begin++;
        }

        swap(nums,begin,end);
    }
    swap(nums,begin,prev);
    return begin;
}
public static void quickSort_level_3(int[] nums,int left,int right){
    if(left>=right)return;

    int key= partSort3(nums,left,right);

    quickSort_level_3(nums,left,key-1);
    quickSort_level_3(nums,key+1,right);
}

//快排④_双指针法
public static int partSort4(int[] nums,int left,int right){
    int midIndex=getMidIndex(nums,left,right);
    swap(nums,midIndex,left);
    int pre=left;
    int cur=left+1;
    int key=nums[left];
    while(cur<=right){
        if(nums[cur]<=key && (++pre!=cur)){
            swap(nums,pre,cur);
        }
        cur++;
    }
    swap(nums,pre,left);
    return pre;
}
public static void quickSort_level_4(int[] nums,int left,int right){
    if(left>=right)return;

    int key=partSort4(nums,left,right);

    quickSort_level_4(nums,left,key-1);
    quickSort_level_4(nums,key+1,right);
}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121