【Java】数据结构-快速排序（完整代码）

admin
admin
admin
102503
文章
87
评论
2022年1月10日03:31:03评论9 views字数 4932阅读16分26秒阅读模式

快速排序执行耗时结果截图

image-20210630045234675

快速排序执行（完整代码）

QuickSort.java（进行了三层优化之后的算法时间进行比较）

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    private QuickSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        Random rnd = new Random();
        sort(arr, 0, arr.length-1, rnd);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l , int r, Random rnd){

        if(l >= r) return;

        int p = partition(arr, l , r, rnd);
        sort(arr, l, p-1, rnd);
        sort(arr, p+1 , r, rnd);
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random rnd){

        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r-l+1);
        swap(arr, l , p);
        // arr[l+1...j] < v; arr[j+1...i] >v
        int j=l;
        for(int i = l + 1; i<= r; i++){
            if(arr[i].compareTo(arr[l]) < 0){
                j ++;
                swap(arr, j, i);
            }
        }
        swap(arr, l,j);
        return j;

    }

    public static <E extends Comparable<E>> void sort2ways(E[] arr){
        Random rnd = new Random();
        sort2ways(arr, 0, arr.length-1, rnd);
    }

    private static <E extends Comparable<E>> void sort2ways(E[] arr, int l , int r, Random rnd){

        if(l >= r) return;

        int p = partition2(arr, l , r, rnd);
        sort2ways(arr, l, p-1, rnd);
        sort2ways(arr, p+1 , r, rnd);
    }

    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random rnd){

        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r-l+1);
        swap(arr, l , p);
        // arr[l+1...j] < v; arr[j+1...i] >v
//        int j=l;
//        for(int i = l + 1; i<= r; i++){
//            if(arr[i].compareTo(arr[l]) < 0){
//                j ++;
//                swap(arr, j, i);
//            }
//        }
//        swap(arr, l,j);
//        return j;

        // arr[l+1...i-1] <= v; arr[j+1...r] >= v
        int i = l+1 , j = r;
        while(true){

            while(i <= j && arr[i].compareTo(arr[l]) < 0)
                i ++;
            while(j >= i && arr[j].compareTo(arr[l]) > 0)
                j --;

            if(i >= j) break;

            swap(arr, i , j);
            i ++;
            j --;
        }
        swap(arr, l , j);
        return j;
    }

    public static <E extends Comparable<E>> void sort3ways(E[] arr){
        Random rnd = new Random();
        sort3ways(arr, 0, arr.length-1, rnd);
    }

    private static <E extends Comparable<E>> void sort3ways(E[] arr, int l , int r, Random rnd){

        if(l >= r) return;

        //生成[l,r]之间的随机索引
        int p = l + rnd.nextInt(r-l+1);
        swap(arr, l , p);

        // arr[l + 1, lt] < v, arr[lt + 1, i - 1] == v , arr[gt, r] > v
        int lt = l , i = l + 1, gt = r + 1; //初始空区间
        while(i < gt){

            if(arr[i].compareTo(arr[l])<0){
                lt ++;
                swap(arr, i , lt );
                i ++;
            }
            else if(arr[i].compareTo(arr[l])>0){
                gt --;
                swap(arr, i, gt);
            }
            else{ // arr[i] == arr[l]
                i ++;
            }
        }
        swap(arr,l ,lt);
        // arr[l, lt - 1 ] < v, arr[lt , gt - 1] == v, arr[gt, r ] > v
        sort3ways(arr, l , lt-1, rnd);
        sort3ways(arr, gt , r, rnd);
    }


    private static <E> void swap(E[] arr, int i , int j){

        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }



    public static void main(String[] args) {

        int n = 10000000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);

        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("QuickSort2", arr2);

        arr = ArrayGenerator.generateOrderedArray(n);
        arr2 = Arrays.copyOf(arr, arr.length);

        SortingHelper.sortTest("QuickSort", arr);
        SortingHelper.sortTest("QuickSort2", arr2);

        arr = ArrayGenerator.generateRandomArray(n, 1);
        arr2 = Arrays.copyOf(arr, arr.length);
        Integer[] arr3 = Arrays.copyOf(arr, arr.length);
        SortingHelper.sortTest("QuickSort2", arr2);
        SortingHelper.sortTest("QuickSort3", arr3);





    }
}

ArrayGenerator.java(生成随机n个元素的数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
import java.util.Random;

public class ArrayGenerator {

    private ArrayGenerator(){}

    public static Integer[] generateOrderedArray(int n){

       Integer[] arr = new Integer[n];
       for(int i = 0; i < n ; i++)
           arr[i] = i;
       return arr;
    }

    // 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
    public static Integer[] generateRandomArray(int n, int bound){

        Integer[] arr = new Integer[n];
        Random rnd = new Random();
        for(int i = 0 ; i < n; i++)
            arr[i] = rnd.nextInt(bound); //从0到bound前闭后开
        return arr;
    }
}

SortingHelper.java（辅助进行算法时间输出的）

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

    private SortingHelper(){} //私有类

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){

        for(int i = 1; i< arr.length; i++)
            if (arr[i - 1].compareTo(arr[i]) > 0)
            return false;
        return true;
    }

    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
        long startTime = System.nanoTime();
        if(sortname.equals("SelectionSort")) {
            SelectionSort.sort(arr);
        } else if(sortname.equals("InsertionSort"))
            InsertionSort.sort(arr);
        else if(sortname.equals("InsertionSort2"))
            InsertionSort.sort2(arr);
        else if(sortname.equals("MergeSort"))
            MergeSort.sort(arr);
        else if(sortname.equals("MergeSort2"))
            MergeSort.sort2(arr);
        else if(sortname.equals("MergeSort3"))
            MergeSort.sort3(arr);
        else if(sortname.equals("MergeSort4"))
            MergeSort.sort4(arr);
        else if(sortname.equals("MergeSortBU"))
            MergeSort.sortBU(arr);
        else if(sortname.equals("QuickSort"))
            QuickSort.sort(arr);
        else if(sortname.equals("QuickSort2"))
            QuickSort.sort2ways(arr);
        else if(sortname.equals("QuickSort3"))
            QuickSort.sort3ways(arr);
        long endTime = System.nanoTime();

        double time = (endTime - startTime) / 1000000000.0; //纳米要/9个零

        if(!SortingHelper.isSorted(arr))
            throw new RuntimeException(sortname + "failed");
        System.out.println(String.format("%s , n = %d : %f s ", sortname, arr.length, time));
    }
}

我的个人博客

孤桜懶契：http://gylq.github.io

FROM:gylq.gitee Author:孤桜懶契

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月10日03:31:03
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   【Java】数据结构-快速排序（完整代码）http://cn-sec.com/archives/729946.html

发表评论

匿名网友 填写信息