快速排序

一般来说，常用的就是三路快排，左中右主要分为：小于区域 、 等于区域 、 大于区域；每次将数组最右边的数作为基准元素，然后挨个比较，进行排序

1 递归实现

1.1 定义swap交换函数

将指定位置的两个数值进行互换

private static void swap(int[] arr, int i, int index) {
    int temp = arr[i];
    arr[i] = arr[index];
    arr[index] = temp;
}
1
2
3
4
5

1.2 定义partition函数，分出L区、R区；找到等于区域

每次将数组arr划定L点和R点，arr数组一共被分出3个部分

//arr[L..R]范围上，拿arr[R]做划分值
//L...R < = >
public static int[] partition(int[] arr, int L, int R){
    int lessR = L - 1;
    int moreL = R;
    int index = L;
    while(index < moreL){
        if(arr[index] < arr[R]){
            swap(arr, ++lessR, index++);
        } else if(arr[index] > arr[R]){
            swap(arr, --moreL, index);
        } else {
            index++;
        }
    }
    swap(arr, moreL, R);
    return new int[]{ lessR+1, moreL};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.3 找到等于区域之后，又将其重新作为一个整体，重新划分，递归

public static void process(int[] arr, int L, int R){
    if(L >= R){
        return;
    }
    int[] equalsE = partition(arr, L, R);
    process(arr, L, equalsE[0] - 1);
    process(arr, equalsE[1] + 1, R);
}
1
2
3
4
5
6
7
8

1.4 定义quickSort调用其他函数

public static void quickSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    process(arr, 0, arr.length - 1);
}
1
2
3
4
5
6

1.5 整体代码

public static void quickSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    process(arr, 0, arr.length - 1);
}

//arr[L..R]范围上，拿arr[R]做划分值
//L...R < = >
public static int[] partition(int[] arr, int L, int R){
    int lessR = L - 1;
    int moreL = R;
    int index = L;
    while(index < moreL){
        if(arr[index] < arr[R]){
            swap(arr, ++lessR, index++);
        } else if(arr[index] > arr[R]){
            swap(arr, --moreL, index);
        } else {
            index++;
        }
    }
    swap(arr, moreL, R);
    return new int[]{ lessR+1, moreL};
}

public static void process(int[] arr, int L, int R){
    if(L >= R){
        return;
    }
    int[] equalsE = partition(arr, L, R);
    process(arr, L, equalsE[0] - 1);
    process(arr, equalsE[1] + 1, R);
}

private static void swap(int[] arr, int i, int index) {
    int temp = arr[i];
    arr[i] = arr[index];
    arr[index] = 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

2 非递归实现（迭代）

2.1 定义Job内部类，标识L点与R点

//定义内部类Job
public static class Job{
    public int L;
    public int R;
    public Job(int L, int R){
        this.L = L;
        this.R = R;
    }
}
1
2
3
4
5
6
7
8
9

2.2 使用stack结构来存储和消费任务

//非递归方式
public static void quickSort2(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    Stack<Job> stack = new Stack<>();
    stack.push(new Job(0, arr.length - 1));
    while(!stack.isEmpty()){
        Job cur = stack.pop();
        int[] equals = partition(arr, cur.L, cur.R);
        if(equals[0] > cur.L){//有 < 区间
            stack.push(new Job(cur.L, equals[0] - 1));
        }
        if(equals[1] < cur.R){//有 > 区间
            stack.push(new Job(equals[1] + 1, cur.R));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.3 partition函数

//arr[L..R]范围上，拿arr[R]做划分值
//L...R < = >
public static int[] partition(int[] arr, int L, int R){
    int lessR = L - 1;
    int moreL = R;
    int index = L;
    while(index < moreL){
        if(arr[index] < arr[R]){
            swap(arr, ++lessR, index++);
        } else if(arr[index] > arr[R]){
            swap(arr, --moreL, index);
        } else {
            index++;
        }
    }
    swap(arr, moreL, R);
    return new int[]{ lessR+1, moreL};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3 定义对数器：验证结果

3.1 构造对数器

随机生成指定范围、指定长度的数组

public static boolean isEquals(int[] arr1, int[] arr2) {
    for (int i = 0; i < arr1.length; i++) {
        if(arr1[i] != arr2[i]){
            return false;
        }
    }
    return true;
}

private static int[] copyArray(int[] arr1) {
    int[] arr2 = new int[arr1.length];
    for (int i = 0; i < arr1.length; i++) {
        arr2[i] = arr1[i];
    }
    return arr2;
}

private static int[] generateRandomArray(int maxSize, int maxValue) {
    int size = (int)(Math.random() * maxSize);
    int value;
    int[] arr = new int[size];
    for (int i = 0; i < size; i++) {
        value = (int)(Math.random() * maxValue);
        arr[i] = value;
    }
    return arr;
}
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

3.2 整体代码

package com.ali.test;

import java.util.Arrays;
import java.util.Stack;

public class Test06 {
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始-----");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            quickSort1(arr1);
            quickSort2(arr2);
            if(!isEquals(arr1, arr2)){
                System.out.println("error....");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                break;
            }
        }
        System.out.println("测试结束....");
    }

    public static void quickSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    //arr[L..R]范围上，拿arr[R]做划分值
    //L...R < = >
    public static int[] partition(int[] arr, int L, int R){
        int lessR = L - 1;
        int moreL = R;
        int index = L;
        while(index < moreL){
            if(arr[index] < arr[R]){
                swap(arr, ++lessR, index++);
            } else if(arr[index] > arr[R]){
                swap(arr, --moreL, index);
            } else {
                index++;
            }
        }
        swap(arr, moreL, R);
        return new int[]{ lessR+1, moreL};
    }

    public static void process(int[] arr, int L, int R){
        if(L >= R){
            return;
        }
        int[] equalsE = partition(arr, L, R);
        process(arr, L, equalsE[0] - 1);
        process(arr, equalsE[1] + 1, R);
    }

    private static void swap(int[] arr, int i, int index) {
        int temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }




    //定义内部类Job
    public static class Job{
        public int L;
        public int R;
        public Job(int L, int R){
            this.L = L;
            this.R = R;
        }
    }
    //非递归方式
    public static void quickSort2(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        Stack<Job> stack = new Stack<>();
        stack.push(new Job(0, arr.length - 1));
        while(!stack.isEmpty()){
            Job cur = stack.pop();
            int[] equals = partition(arr, cur.L, cur.R);
            if(equals[0] > cur.L){//有 < 区间
                stack.push(new Job(cur.L, equals[0] - 1));
            }
            if(equals[1] < cur.R){//有 > 区间
                stack.push(new Job(equals[1] + 1, cur.R));
            }
        }
    }
    //构造对数器
    public static boolean isEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    private static int[] copyArray(int[] arr1) {
        int[] arr2 = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
        return arr2;
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int size = (int)(Math.random() * maxSize);
        int value;
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            value = (int)(Math.random() * maxValue);
            arr[i] = value;
        }
        return arr;
    }
}

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
122
123
124
125
126
127