前面一篇文章系统介绍了快速排序算法,提到快速排序虽然平均时间复杂度为 o(n*log2(n)),效率相对比较高。但是其在特殊情况下,比如降序的情况下,效率和冒泡排序一致,这就削弱了快速排序给人的好感。然而有没有办法,能够解决这种问题,使快速排序的时间复杂度与输入序列无关呢?答案是有的,使用舍伍德概率算法能够帮助解决这个问题。
舍伍德算法是三大概率算法之一,它的实质就是通过随机概率解决问题与输入顺序的关联,从而优化问题的解决。舍伍德算法还可用于层级链表问题,后续写概率算法时会进一步提到。
思路很简单,为了使排序与输入序列顺序无关,在划分基准时,我们确定一个随机基准(low 到 high 之间的一个随机位置),将它与第一位(默认基准)进行交换,而后再进行基准位确定,进而分治快速排序其左半部分与右半部分。
- package com.fairy.InnerSort;
- import java.util.Scanner;
- /**
- * 舍伍德算法优化快速排序
- * @author Fairy2016
- *
- */
- public class QuickSort {
- //快速排序
- public static void sort(int a[], int low, int high) {
- if (low < high) {
- int base = Depart(a, low, high);
- //对基准左半边部分进行排序
- sort(a, low, base - 1);
- //对基准右半边部分进行排序
- sort(a, base + 1, high);
- }
- }
- //基准划分
- public static int Depart(int a[], int low, int high) {
- //舍伍德随机确定基准
- int d = (int) Math.random() * (high - low) + low;
- //交换默认基准与随机基准
- a[0] = a[d];
- a[d] = a[low];
- a[low] = a[0];
- while (low < high) {
- //从右向左扫描找比基准小的元素
- while (low < high && a[high] >= a[0]) high--;
- a[low] = a[high]; //赋值,更新基准位
- //从左向右扫描找比基准大的元素
- while (low < high && a[low] <= a[0]) low++;
- a[high] = a[low]; //赋值,更新基准位
- }
- //基准位最终位置已确定,是low或者high
- a[high] = a[0];
- return high;
- }
- public static void Print(int a[], int n) {
- for (int i = 1; i <= n; i++) {
- System.out.print(a[i] + " ");
- }
- }
- public static void main(String args[]) {
- int n;
- int a[];
- Scanner scanner = new Scanner(System. in );
- while (scanner.hasNext()) {
- n = scanner.nextInt();
- if (n > 0) {
- a = new int[n + 1];
- for (int i = 1; i <= n; i++) {
- a[i] = scanner.nextInt();
- }
- sort(a, 1, n);
- Print(a, n);
- }
- }
- scanner.close();
- }
- }
来源: http://www.jianshu.com/p/2c0c2415b40f