java - 快速排序3有什么问题

Question

我的三向分区快速排序出了什么问题？当输入数据小于100000时正常工作。当输入数据 = 100000 时，它的工作时间约为 9 秒。 我使用 Dijkstra 3 路分区。如果输入数据由大量相同元素组成，则一切正常，当输入数据随机时，工作速度太慢。

 static void randomizedQuickSort(int[] a, int l, int r) {
    if (l >= r) {
        return;
    }

    int[] m = Partition3(a, l, r);
    randomizedQuickSort(a, l, m[0] - 1);
    randomizedQuickSort(a, m[1] + 1, r);
}

private static int[] Partition3(int[] nums, int l, int r) {
    Random random = new Random();
    int k = random.nextInt(r - l + 1) + l;
    int mid = nums[k];
    int m1 = 0;
    int i = 0;
    int m2 = r;


    while (m1 <= m2) {
        if (nums[m1] < mid) {
            swap(nums, i, m1);
            i++;
            m1++;
        } else if (nums[m1] > mid) {
            swap(nums, m1, m2);
            m2--;
        } else {
            m1++;
        }
    }

    return new int[]{i, m2};
}

Answer 1

你做错了什么，因为交换次数是 O(n^2) 如果你计算对 swap 的调用次数，你会得到类似的结果(第一个数字是元素的数量)

10000: Took 0.078000 seconds, and 33432534 swaps
20000: Took 0.291000 seconds, and 166934755 swaps
40000: Took 1.102000 seconds, and 702291723 swaps
80000: Took 4.482000 seconds, and 2837543629 swaps
160000: Took 17.590000 seconds, and 11373050608 swaps

问题出在线条

int m1 = 0;
int i = 0;

每次排序时从数组开头开始排序。

int m1 = l; // sort from the start of the section.
int i = l;

完整版是......

public static void main(String[] args) {
    for (int t = 100_000;  t <= 100_000_000; t *= 10) {
        int[] nums = new int[t];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = random.nextInt();
        }
        long start = System.currentTimeMillis();
        swaps = 0;
        randomizedQuickSort(nums, 0, nums.length - 1);
        long time = System.currentTimeMillis() - start;
        for (int i=0;i<nums.length-1;i++)
            if (nums[0] > nums[1])
                throw new AssertionError();
        System.out.printf("%d: Took %f seconds, and %d swaps%n", t, time / 1e3, swaps);
    }
}

static void randomizedQuickSort(int[] a, int l, int r) {
    if (l >= r) {
        return;
    }

    long m = Partition3(a, l, r);
    int m0 = (int) (m >> 32);
    int m1 = (int) m;
    randomizedQuickSort(a, l, m0 - 1);
    randomizedQuickSort(a, m1 + 1, r);
}

static final Random random = new Random();
static long swaps = 0;

private static long Partition3(int[] nums, int l, int r) {
    int k = random.nextInt(r - l + 1) + l;
    int mid = nums[k];
    int m1 = l;
    int i = l;
    int m2 = r;


    while (m1 <= m2) {
        if (nums[m1] < mid) {
            swap(nums, i, m1);
            i++;
            m1++;
        } else if (nums[m1] > mid) {
            swap(nums, m1, m2);
            m2--;
        } else {
            m1++;
        }
    }

    return ((long) i << 32) | m2;
}

private static void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
    swaps++;
}

打印

100000: Took 0.018000 seconds, and 2032183 swaps
1000000: Took 0.168000 seconds, and 24872604 swaps
10000000: Took 1.709000 seconds, and 287681791 swaps
100000000: Took 19.015000 seconds, and 3353327832 swaps