QuickSort Dijkstra 3-Way Partitioning

思想

原始的 2-Way 快排在遇到大量重复数据时会退化为 O(n^2),为了解决这个问题,3-Way 快排被提出了。通过将区间分割为“小于”、“等于”和“大于”(基准数)三个部分,获得了趋近 O(nlogn) 的复杂度。不同于 2-Way 快排的是,我们在此选取一个基准数的值,而非一个基准元素。

(小声逼逼:当然为了方便也可以直接改进 2-Way 快排,在每一次基准数归位后遍历全区间元素,将等于基准数的元素交换到基准数旁边,也能获得等价的三个区间。当然,效率相对于 3-Way 快排有所下降,代码实现的复杂度也上升了。)

使用 i 下标表示“小于”区间的上界;使用 q 下标表示“等于”区间的上界;使用 j 下标表示“大于”区间的下界。

  1. 选取一个元素的值作为基准数值
  2. 判断 arr[q]pivot 的关系: 如果小于 pivot,交换 arr[i]arr[q]q 自增,i 自增 如果大于 pivot,交换 arr[j]arr[q]q ** 不变 **,j 自减 如果等于 pivotq 自增
  3. 重复步骤 2,直至 qj 相遇。

实现

    public static void swap(int arr[], int a, int b)
    {
        /**
         * Due to Java doesn't have reference, we can use XOR to swap the values
         */
        if (a != b)
        {
            arr[a] ^= arr[b];//a = a^b
            arr[b] ^= arr[a];//b = b^a^b = a
            arr[a] ^= arr[b];//a = a^b^a = b
        }
    }
    public static void quickSort(int f[], int lo, int hi)
    {
        if (lo >= hi)
            return;

        int pivot = f[(int)Math.random() % (hi - lo + 1) + lo];//randomize pivot

        /**
         * i "less" upper bound
         * j "more" lower bound
         * q "equal" upper bound
         * 
         * ##less## ->i ##equal## ->q ##unknown## j<- ##more##
         */

        int i = lo, j = hi, q = lo;

        //partition
        while (q <= j)
        {
            if (f[q] < pivot)
                swap(f, q, i++);
            else if (f[q] > pivot)
                swap(f, q--, j--);//the exchanged value need to be check, so we q--
            ++q;
        }
        //recursion
        quickSort(f, lo, i);//left
        quickSort(f, j+1, hi);//right
    }

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据