时间戳

首页 > 解决方案 > 当数组中有很多重复时优化快速排序

java - 当数组中有很多重复时优化快速排序

问题描述

我根据以下情况提出了过去一年的问题：

当要排序的项目列表包含大量重复值时，我们可以通过将所有等于枢轴的值分组到中间来改进快速排序，然后递归地快速排序左边的值和右边的值。对分区方法进行必要的更改以实现此目的。

这是当前使用的实现：

// Quick Sort algorithm
public class QuickSort {

    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length-1);
    }

    private static void quickSort(int[] a, int i, int j) {
        if (i < j) {
            int pivotIdx= partition(a, i, j);
            quickSort(a, i, pivotIdx-1);
            quickSort(a, pivotIdx+1, j);
        }
    }

    private static void swap(int[] a, int pos1, int pos2) {
        int temp = a[pos1];
        a[pos1] = a[pos2];
        a[pos2] = temp;
    }

    private static int partition(int[] a, int i, int j) {
        // partition data items in a[i..j]
        int p = a[i]; // p is the pivot, the i-th item
        int m = i;    // Initially S1 and S2 are empty

        for (int k=i+1; k<=j; k++) { // process unknown region
            if (a[k] < p) { // case 2: put a[k] to S1
                m++;
                swap(a,k,m);
            }
        }

        swap(a,i,m); // put the pivot at the right place
        return m;    // m is the pivot's final position
    }

    public static void printArray(int[] a) {
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 7, 12, 3, 5, -6, 3, 8, 2, 10, -3 };

        printArray(arr);
        quickSort(arr);
        printArray(arr);
    }
}

我对这里介绍的快速排序算法有一些基本的了解，但我真的不明白这个问题是否真的给了我关于如何实现算法的提示，因为在我看来快速排序必须遍历列表以制作 2 个分区和动态决定位置 X 放置枢轴的位置，在此实现中，枢轴被选为输入数组的最左侧元素。如果这个位置 X 是动态决定的，你究竟如何将元素“分组等于枢轴”到中间，以及它究竟如何改进算法？

标签： javaalgorithmsortingquicksort

解决方案

主要思想是使用三向分区策略来解决这个问题。有关详细信息，请参阅荷兰国旗问题。

如果您有很多重复元素，那么您的快速排序将尝试将每个重复元素分别放置在正确的位置。但你不需要这样做。

让我们看一个我在上述声明中声称的例子：

假设你有一个像{4,6,4,3,4,2,5,4,1,4}. 在这个数组中，元素4重复 5 次。并且当应用快速排序并放置4在正确的位置时，您会将数组划分为 2 部分，以便左侧部分包含所有小于或等于4（但没有特定顺序）的元素，右侧部分包含所有元素大于4。但那是天真的方法。

让我们看看如何改进这一点（假设我们有很多重复的元素）

当您的快速排序找到4并将数组分区以将其放置4在正确的位置时，您还可以跟踪所有相等的元素（数组中等于 的其他元素4）以及左侧较小的元素和右侧的较大元素。

因此，当分区而不是具有 2 个索引left和right（子数组 0left包含小于或等于枢轴的所有元素和子数组left包含right大于枢轴的所有元素并且right是len(array)-1尚未探索的元素）时，您可以有3个指标，描述如下：

  • [0,left)- 元素小于枢轴的子数组
  • [left, mid)- 元素等于枢轴的子数组
  • [mid, right]- 元素大于枢轴的子数组
  • [right, len(array))- 尚待探索的元素。

这样，您修改后的快速排序将只使用较少的次数（具体来说，等于数组中唯一元素的计数）。正因为如此，递归调用的数量将会减少。

因此，此解决方案利用了存在许多重复项的特定输入的情况（因此数组中的重复元素越多，此修改后的快速排序变体将执行得越好）

给我看一些代码。

import java.util.Arrays;
import java.util.stream.IntStream;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 4, 1, 2, 4, 3, 5, 6, 2, 2, 2, 1, 1, 1};
        quickSort(arr);
        System.out.print("Sorted array: ");
        Arrays.stream(arr).forEach(i -> System.out.print(i + " "));
        System.out.println();
    }

    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        if (start > end)
            return; // base condition

        System.out.print("Recursive call on: ");
        IntStream
                .rangeClosed(start, end)
                .map(i -> arr[i])
                .forEach(i -> System.out.print(i + " "));
        System.out.println();

        int n = arr.length;
        if (start < 0 || start >= n || end < 0 || end >= n)
            throw new IllegalArgumentException("the indices of the array are not valid");

        int pivot = arr[end];
        /*
            [start,left) - sub-array with elements lesser than pivot
            [left, mid) - sub-array with elements equal to pivot
            [mid, right] - sub-array with elements greater than pivot
            [right, end) - elements yet to be explored.
         */
        int left = start, mid = start, right = start;

        while (right != end) {
            if (arr[right] < pivot) {
                swap(arr, left, right);
                swap(arr, mid, right);
                left++;
                right++;
                mid++;
            } else if (arr[right] == pivot) {
                swap(arr, mid, right);
                mid++;
                right++;
            } else if (arr[right] > pivot) {
                right++;
            }
        }

        swap(arr, mid, right);
        System.out.println("Placed " + pivot + " at it's correct position");
        System.out.println();
        quickSort(arr, start, left - 1);
        quickSort(arr, mid + 1, end);
    }

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

上述代码的输出是：

Recursive call on: 2 3 4 1 2 4 3 5 6 2 2 2 1 1 1 
Placed 1 at it's correct position

Recursive call on: 2 4 3 5 6 2 2 2 3 4 2 
Placed 2 at it's correct position

Recursive call on: 4 3 5 3 4 6 
Placed 6 at it's correct position

Recursive call on: 4 3 5 3 4 
Placed 4 at it's correct position

Recursive call on: 3 3 
Placed 3 at it's correct position

Recursive call on: 5 
Placed 5 at it's correct position

Sorted array: 1 1 1 1 2 2 2 2 2 3 3 4 4 5 6

上面的输出清楚地表明，在将枢轴放置在正确的位置之后，我们递归了两个不同的数组，但是这两个数组中没有一个包含前一个枢轴。（这是优化）

推荐阅读