5

I'm trying to write a quicksort for my own edification. I'm using the pseudocode on wikipedia as a guide. My code works. It seems like it should run in O(n log n) time. I tried actually timing my code to check the complexity (i.e., when I double the input size, does the run time increase by approximately n log n), but I'm still not sure.

My code seems pretty simple. I do the sort in-place. Other implementations I've seen use a partition function, which I don't have. This makes me think that I've implemented some other sorting algorithm. Is this a quicksort algorithm?

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

private static void QuickSortInPlace(int[] arr, int left, int right)
{
    if (left < right)
    {
        //move the middle int to the beginning and use it as the pivot
        Swap(arr, left, (left + right) / 2);

        int pivotIndex = left;
        int pivot = arr[pivotIndex];
        int min = left + 1;
        int max = right;

        for (int i = min; i <= max; i++)
        {
            if (arr[i] > pivot)
            {
                Swap(arr, i, max);
                max--; //no longer need to inspect ints that have been swapped to the end
                i--; //reset the loop counter to inspect the new int at the swapped position
            }
        }

        //move pivot to its sorted position
        Swap(arr, max, pivotIndex);

        //recurse on the sub-arrays to the left and right of the pivot
        QuickSortInPlace(arr, left, max - 1);
        QuickSortInPlace(arr, max + 1, right);
    }
}

Second version based on Dukeling's response.

public static void QuickSortInPlace3(int[] arr, int min, int max)
{
    if (min < max)
    {
        int pivotIndex = min;
        int pivot = arr[pivotIndex];

        int left = min;
        int right = max;

        while (left <= right)
        {
            while (arr[left] < pivot)
                left++;

            while (arr[right] > pivot)
                right--;

            if (left <= right)
            {
                Swap(arr, left, right);
                left++;
                right--;
            }
        }

        QuickSortInPlace3(arr, min, right);
        QuickSortInPlace3(arr, left, max);
    }
}
4

1 回答 1

4

是的，它绝对足够接近快速分类来分类，或者至少是一个小变种。

您正在对数据进行分区，只是没有单独的功能。

你确实发生了一些奇怪的事情。

通常，使用快速排序的就地变体，您在左索引小于枢轴时增加左索引，然后在右索引较大时减小右索引，然后交换两者（仅执行涉及 2 个元素的交换，它们都是在错误的一边）。

然而，你只是增加了左边，所以你可以从右边交换已经更大的元素。尽管渐近运行时间应该相同，但这可能会导致不必要的交换次数更多。

这是“正常”变体的一些伪代码：（取自Rosetta Code）

while left ≤ right
    while array[left] < pivot
        left := left + 1
    while array[right] > pivot
        right := right - 1
    if left ≤ right
        swap array[left] with array[right]
        left := left + 1
        right := right - 1
于 2014-04-23T15:43:51.827 回答