八大基本排序---快速排序（经典快排、随机快排）（荷兰国旗问题）

92 阅读 0 评论 61 点赞

我是靠谱客的博主舒服豌豆，这篇文章主要介绍八大基本排序---快速排序（经典快排、随机快排）（荷兰国旗问题），现在分享给大家，希望可以做个参考。

引言：

clip_image002_thumb[1]

解答：

clip_image004_thumb[1]

需要准备3个下标

clip_image006_thumb[1]

如果当前数字=num，cur跳下一个

clip_image008_thumb[1]

如果数组中的当前数字<num，把这个数（3）和小于区域的下一个数（5）交换

clip_image010_thumb[1]

然后小于区域扩一下

clip_image012_thumb[1]

然后cur跳下一个位置

clip_image014_thumb[1]

数组中的当前数字<num，把这个数（2）和小于区域的下一个数（5）交换，

然后小于区域扩一下

然后cur跳下一个位置

clip_image016_thumb[1]

PS：

如果一上来遇到的就是cur<num

把这个数（3）和小于等于区域的下一个数（3）交换【自己和自己交换】

clip_image018_thumb[1]

数组中的当前数字>num，把这个数（7）和大于区域的前一个数（x）交换

然后大于区域向左扩一个位置，more移动一下

然后让cur停留在原地，继续考察换过来的x跟num的大小关系

clip_image020_thumb[1]

当cur == more的时候，整个过程停止

复制代码

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
public class Code_08_NetherlandsFlag {

    public static int[] partition(int[] arr, int L, int R, int num) {
        int less = L - 1;
        int more = R + 1;
        while (L < more) {
            if (arr[L] < num) {
                swap(arr, ++less, L++);
            } else if (arr[L] > num) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }
        //less + 1：等于区域的第一个位置，more - 1:等于区域的最后 一个位置
        return new int[] { less + 1, more - 1 };
    }

    // for test
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

传统快排：与荷兰国旗问题类似

image_thumb[1]

复制代码

import java.util.Arrays;

//利用荷兰国旗问题进行快排
public class QuickSort {

public static void main(String[] args) {
        int[] arr = {3,1,4,5,2,2,0,13};
        System.out.println(Arrays.toString(arr));
//        int[] res = new int[2];
//        res = partition(arr, 0, arr.length-1);
//        System.out.println(res[0]+" " +res[1]);
//        System.out.println(Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
        
    }
    
    public static void quickSort(int[] arr,int L,int R){
        if (L>=R) {
            return;
        }
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0]-1);
        quickSort(arr, p[1]+1, R);
    }
    
    //以数组的最后一个数字arr[R]作为num
    //返回等于区域的下标
    public static int[] partition(int[] arr,int L ,int R){
        int less = L-1;
        int more = R+1;
        int num = arr[R];
        while (L < more) {
            if (arr[L]==num) {
                L++;
            }else if (arr[L]<num) {
                swap(arr,++less,L++);
            }else if (arr[L]>num) {
                swap(arr,L ,--more );
            }
        }
        int[] res = {less+1,more-1};
        return  res;
    }
    
    public static void swap(int[] arr, int i, int j ){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

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
import java.util.Arrays;

//利用荷兰国旗问题进行快排
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {3,1,4,5,2,2,0,13};
        System.out.println(Arrays.toString(arr));
//        int[] res = new int[2];
//        res = partition(arr, 0, arr.length-1);
//        System.out.println(res[0]+" " +res[1]);
//        System.out.println(Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
        
    }
    
    public static void quickSort(int[] arr,int L,int R){
        if (L>=R) {
            return;
        }
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0]-1);
        quickSort(arr, p[1]+1, R);
    }
    
    //以数组的最后一个数字arr[R]作为num
    //返回等于区域的下标
    public static int[] partition(int[] arr,int L ,int R){
        int less = L-1;
        int more = R+1;
        int num = arr[R];
        while (L < more) {
            if (arr[L]==num) {
                L++;
            }else if (arr[L]<num) {
                swap(arr,++less,L++);
            }else if (arr[L]>num) {
                swap(arr,L ,--more );
            }
        }
        int[] res = {less+1,more-1};
        return  res;
    }
    
    public static void swap(int[] arr, int i, int j ){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}