服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|JavaScript|易语言|

服务器之家 - 编程语言 - JAVA教程 - Java编程实现快速排序及优化代码详解

Java编程实现快速排序及优化代码详解

2021-02-27 14:19GoldArowana JAVA教程

这篇文章主要介绍了Java编程实现快速排序及优化代码详解,具有一定借鉴价值,需要的朋友可以了解下。

普通快速排序

找一个基准值base,然后一趟排序后让base左边的数都小于base,base右边的数都大于等于base。再分为两个子数组的排序。如此递归下去。

?
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
public class quicksort {
    public static <t extends comparable<? super t>> void sort(t[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    public static <t extends comparable<? super t>> void sort(t[] arr, int left, int right) {
        if (left >= right) return;
        int p = partition(arr, left, right);
        sort(arr, left, p - 1);
        sort(arr, p + 1, right);
    }
    private static <t extends comparable<? super t>> int partition(t[] arr, int left, int right) {
        t base = arr[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (base.compareto(arr[i]) > 0) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, left, j);
        return j;
        //返回一躺排序后基准值的下角标
    }
    public static void swap(object[] arr, int i, int j) {
        if (i != j) {
            object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    private static void printarr(object[] arr) {
        for (object o : arr) {
            system.out.print(o);
            system.out.print("\t");
        }
        system.out.println();
    }
    public static void main(string args[]) {
        integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printarr(arr);
        //3  5  1  7  2  9  8  0  4  6
        sort(arr);
        printarr(arr);
        //0  1  2  3  4  5  6  7  8  9
    }
}

快速排序优化:随机选取基准值base

在数组几乎有序时,快排性能不好(因为每趟排序后,左右两个子递归规模相差悬殊,大的那部分最后很可能会达到o(n^2))。

解决:基准值随机地选取,而不是每次都取第一个数。这样就不会受“几乎有序的数组”的干扰了。但是对“几乎乱序的数组”的排序性能可能会稍微下降,至少多了排序前交换的那部分,乱序时这个交换没有意义...有很多“运气”成分..

?
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
public class quicksort {
    public static <t extends comparable<? super t>> void sort(t[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    public static <t extends comparable<? super t>> void sort(t[] arr, int left, int right) {
        if (left >= right) return;
        int p = partition(arr, left, right);
        sort(arr, left, p - 1);
        sort(arr, p + 1, right);
    }
    private static <t extends comparable<? super t>> int partition(t[] arr, int left, int right) {
        //排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
        //就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
        swap(arr,left,(int)(math.random()*(right - left + 1)+left));
        t base = arr[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (base.compareto(arr[i]) > 0) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, left, j);
        return j;
        //返回一躺排序后,基准值的下角标
    }
    public static void swap(object[] arr, int i, int j) {
        if (i != j) {
            object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    private static void printarr(object[] arr) {
        for (object o : arr) {
            system.out.print(o);
            system.out.print("\t");
        }
        system.out.println();
    }
    public static void main(string args[]) {
        integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printarr(arr);
        //3  5  1  7  2  9  8  0  4  6
        sort(arr);
        printarr(arr);
        //0  1  2  3  4  5  6  7  8  9
    }
}

快速排序继续优化:配合着使用插入排序

快排是不断减小问题规模来解决子问题的,需要不断递归。但是递归到规模足够小时,如果继续采用这种 不稳定+递归 的方式执行下去,效率不见得会很好。

所以当问题规模较小时,近乎有序时,插入排序表现的很好。java自带的arrays.sort()里经常能看到这样的注释:“use insertion sort on tiny arrays”,“insertion sort on smallest arrays”

?
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
public class quicksort {
    public static <t extends comparable<? super t>> void sort(t[] arr) {
        sort(arr, 0, arr.length - 1, 16);
    }
    /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时,采用插入排序优化
   * @param <t>  泛型,待排序可比较类型
   */
    public static <t extends comparable<? super t>> void sort(t[] arr, int left, int right, int k) {
        // 规模小时采用插入排序
        if (right - left <= k) {
            insertionsort(arr, left, right);
            return;
        }
        int p = partition(arr, left, right);
        sort(arr, left, p - 1, k);
        sort(arr, p + 1, right, k);
    }
    public static <t extends comparable<? super t>> void insertionsort(t[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            t cur = arr[i];
            int j = i - 1;
            for (; j >= 0 && cur.compareto(arr[j]) < 0; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = cur;
        }
    }
    private static <t extends comparable<? super t>> int partition(t[] arr, int left, int right) {
        //排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
        //就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
        swap(arr, left, (int) (math.random() * (right - left + 1) + left));
        t base = arr[left];
        int j = left;
        for (int i = left + 1; i <= right; i++) {
            if (base.compareto(arr[i]) > 0) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, left, j);
        return j;
        //返回一躺排序后,基准值的下角标
    }
    public static void swap(object[] arr, int i, int j) {
        if (i != j) {
            object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    private static void printarr(object[] arr) {
        for (object o : arr) {
            system.out.print(o);
            system.out.print("\t");
        }
        system.out.println();
    }
    public static void main(string args[]) {
        integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printarr(arr);
        //3  5  1  7  2  9  8  0  4  6
        sort(arr);
        printarr(arr);
        //0  1  2  3  4  5  6  7  8  9
    }
}

快速排序继续优化:两路快排

在最开始的普通快速排序说过,让基准值base左边的都比base小,而base右边的都大于等于base。等于base的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。总之就会聚集到一边。这样在数组中重复数字很多的时候,就又会导致两边子递归规模差距悬殊的情况。这时想把等于base的那些数分派到base两边,而不是让他们聚集到一起。

(注:测试代码的时候,最好把插入排序那部分注视掉,向我下面代码中那样...不然数据量小于k=16的时候执行的是插入排序.....)

?
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
public class quicksort {
    public static <t extends comparable<? super t>> void sort(t[] arr) {
        sort(arr, 0, arr.length - 1, 16);
    }
    /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时,采用插入排序优化
   * @param <t>  泛型,待排序可比较类型
   */
    public static <t extends comparable<? super t>> void sort(t[] arr, int left, int right, int k) {
        // 规模小时采用插入排序
        //    if (right - left <= k) {
        //      insertionsort(arr, left, right);
        //      return;
        //    }
        if (left >= right) return;
        int p = partition(arr, left, right);
        sort(arr, left, p - 1, k);
        sort(arr, p + 1, right, k);
    }
    public static <t extends comparable<? super t>> void insertionsort(t[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            t cur = arr[i];
            int j = i - 1;
            for (; j >= 0 && cur.compareto(arr[j]) < 0; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = cur;
        }
    }
    private static <t extends comparable<? super t>> int partition(t[] arr, int left, int right) {
        //排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
        //就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
        swap(arr, left, (int) (math.random() * (right - left + 1) + left));
        t base = arr[left];
        //基准值,每次都把这个基准值抛出去,看成[left+1.....right]左闭右闭区间的排序
        int i = left + 1;
        //对于上一行提到的[left+1.....right]区间,i表示 [left+1......i)左闭右开区间的值都小于等于base。
        int j = right;
        //对于上二行提到的[left+1.....right]区间,j表示 (j......right]左开右闭区间的值都大于等于base。
        while (true) {
            //从左到右扫描,扫描出第一个比base大的元素,然后i停在那里。
            while (i <= right && arr[i].compareto(base) < 0) i++;
            //从右到左扫描,扫描出第一个比base小的元素,然后j停在那里。
            while (j >= left && arr[j].compareto(base) > 0) j--;
            if (i > j) {
                //虽说是i>j,但其实都是以j=i-1为条件结束的
                break;
            }
            swap(arr, i++, j--);
        }
        swap(arr, left, j);
        return j;
        //返回一躺排序后,基准值的下角标
    }
    public static void swap(object[] arr, int i, int j) {
        if (i != j) {
            object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    private static void printarr(object[] arr) {
        for (object o : arr) {
            system.out.print(o);
            system.out.print("\t");
        }
        system.out.println();
    }
    public static void main(string args[]) {
        integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printarr(arr);
        //3  5  1  7  2  9  8  0  4  6
        sort(arr);
        printarr(arr);
        //0  1  2  3  4  5  6  7  8  9
    }
}

快速排序继续优化:两路快排 不用swap,用交换

上面的两路在找到大于base的值和小于base的值时,用的是swap()方法来进行交换。两数交换涉及到第三个变量temp的操作,多了读写操作。接下来用直接赋值的方法,把小于的放到右边,大于的放到左边,当i和j相遇时,那个位置就是base该放的地方。至此一趟完成。递归即可。

?
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 <t extends comparable<? super t>> void sort(t[] arr) {
        sort(arr, 0, arr.length - 1, 16);
    }
    /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时,采用插入排序优化
   * @param <t>  泛型,待排序可比较类型
   */
    public static <t extends comparable<? super t>> void sort(t[] arr, int left, int right, int k) {
        // 规模小时采用插入排序
        //    if (right - left <= k) {
        //      insertionsort(arr, left, right);
        //      return;
        //    }
        if (left >= right) return;
        int p = partition(arr, left, right);
        sort(arr, left, p - 1, k);
        sort(arr, p + 1, right, k);
    }
    public static <t extends comparable<? super t>> void insertionsort(t[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            t cur = arr[i];
            int j = i - 1;
            for (; j >= 0 && cur.compareto(arr[j]) < 0; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = cur;
        }
    }
    private static <t extends comparable<? super t>> int partition(t[] arr, int left, int right) {
        //排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
        //就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
        swap(arr, left, (int) (math.random() * (right - left + 1) + left));
        t base = arr[left];
        //基准值,每次都把这个基准值抛出去,看成[left+1.....right]左闭右闭区间的排序
        int i = left;
        //对于上一行提到的[left+1.....right]区间,i表示 [left+1......i)左闭右开区间的值都小于等于base。
        int j = right;
        //对于上二行提到的[left+1.....right]区间,j表示 (j......right]左开右闭区间的值都大于等于base。
        while (i < j) {
            //从右到左扫描,扫描出第一个比base小的元素,然后j停在那里。
            while (j > i && arr[j].compareto(base) > 0) j--;
            arr[i] = arr[j];
            //从左到右扫描,扫描出第一个比base大的元素,然后i停在那里。
            while (i < j && arr[i].compareto(base) < 0) i++;
            arr[j] = arr[i];
        }
        arr[j] = base;
        return j;
        //返回一躺排序后,基准值的下角标
    }
    public static void swap(object[] arr, int i, int j) {
        if (i != j) {
            object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    private static void printarr(object[] arr) {
        for (object o : arr) {
            system.out.print(o);
            system.out.print("\t");
        }
        system.out.println();
    }
    public static void main(string args[]) {
        integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printarr(arr);
        //3  5  1  7  2  9  8  0  4  6
        sort(arr);
        printarr(arr);
        //0  1  2  3  4  5  6  7  8  9
    }
}

快速排序继续优化:当大量数据,且重复数多时,用三路快排

把数组分为三路,第一路都比base小,第二路都等于base,第三路都大于base。

用指针从前到后扫描,如果:

1.cur指向的数小于base,那么:交换arr[cur]和arr[i]的值,然后i++,cur++。

2.cur指向的数等于base,那么:cur++

3.cur指向的数大于base,那么:交换arr[cur]和arr[j]的值,然后j--。

当cur>j的时候说明三路都已经完成。

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
public class quicksort {
    public static <t extends comparable<? super t>> void sort(t[] arr) {
        sort(arr, 0, arr.length - 1, 16);
    }
    /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时,采用插入排序优化
   * @param <t>  泛型,待排序可比较类型
   */
    public static <t extends comparable<? super t>> void sort(t[] arr, int left, int right, int k) {
        // 规模小时采用插入排序
        //    if (right - left <= k) {
        //      insertionsort(arr, left, right);
        //      return;
        //    }
        if (left >= right) return;
        int[] ret = partition(arr, left, right);
        sort(arr, left, ret[0], k);
        sort(arr, ret[1], right, k);
    }
    public static <t extends comparable<? super t>> void insertionsort(t[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            t cur = arr[i];
            int j = i - 1;
            for (; j >= 0 && cur.compareto(arr[j]) < 0; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = cur;
        }
    }
    /**
   * @param arr  待排序的数组
   * @param left 待排序数组的左边界
   * @param right 待排序数组的右边界
   * @param <t>  泛型
   * @return
   */
    private static <t extends comparable<? super t>> int[] partition(t[] arr, int left, int right) {
        //排序前,先让基准值和随机的一个数进行交换。这样,基准值就有随机性。
        //就不至于在数组相对有序时,导致左右两边的递归规模不一致,产生最坏时间复杂度
        swap(arr, left, (int) (math.random() * (right - left + 1) + left));
        t base = arr[left];
        //基准值,每次都把这个基准值抛出去,看成[left+1.....right]左闭右闭区间的排序
        //三路快排分为下面这三个路(区间)
        int i = left;
        // left表示,[lleft...left) 左闭右开区间里的数都比base小
        int j = right;
        // left表示,(rright...right] 左开右闭区间里的数都比base大
        int cur = i;
        //用cur来遍历数组。[left...cur)左闭右开区间里的数都等于base
        while (cur <= j) {
            if (arr[cur].compareto(base) == 0) {
                cur++;
            } else if (arr[cur].compareto(base) < 0) {
                swap(arr, cur++, i++);
            } else {
                swap(arr, cur, j--);
            }
        }
        return new int[]{i - 1, j + 1};
        //[i...j]都等于base,子问题就只需要解决i左边和j右边就行了
    }
    public static void swap(object[] arr, int i, int j) {
        if (i != j) {
            object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    private static void printarr(object[] arr) {
        for (object o : arr) {
            system.out.print(o);
            system.out.print("\t");
        }
        system.out.println();
    }
    public static void main(string args[]) {
        integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
        printarr(arr);
        //3  5  1  7  2  9  8  0  4  6
        sort(arr);
        printarr(arr);
        //0  1  2  3  4  5  6  7  8  9
    }
}

总结

以上就是本文关于java编程实现快速排序及优化代码详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://www.cnblogs.com/noKing/p/7922397.html

延伸 · 阅读

精彩推荐