优化快速排序

• 下载 优化快速排序 - 940 B

引言

在生产力方面，总是需要关注两个变量：时间和空间。就计算而言，这些是速度和内存。快速排序作为最快的排序算法，已经被人研究了近50年，所以在直接提高其速度方面，已经没有太多可以做的了。然而，仍然有几种方法可以优化它，使其能够更好地利用其内存。

背景

只需要对排序算法有良好的兴趣，并理解快速排序。

变更

static void OptimizedQuickSort(ref int[] Arr, int Left, int Right)
{
    int Pivot;
    Pivot = Q_Sort(ref Arr, Left, Right);
    if(Left < Pivot - 1)
    {
        OptimizedQuickSort(ref Arr, Left, Pivot - 1);
    }
    if(Right > Pivot + 1)
    {
        OptimizedQuickSort(ref Arr, Pivot + 1, Right);
    }
}  

static int Q_Sort(ref int[] Arr, int Left, int Right)
{
    int Pivot;
    Pivot = Arr[Left];
    while(Left < Right)
    {
        while((Arr[Right] >= Pivot) && (Left < Right))
        {
            Right--;
        }
        if(Left != Right)
        {
            Arr[Left] = Arr[Right];
            Left++;
        }
        while((Arr[Left] <= Pivot) && (Left < Right))
        {
            Left++;
        }
        if(Left != Right)
        {
            Arr[Right] = Arr[Left];
            Right--;
        }
    }   
    Arr[Left] = Pivot;
    return Left;
}  

我做的最大的改变是将快速排序分成两个函数，这样乍一看，它看起来有点像归并排序。这样做的好处是，与其让每次递归都复制相同的代码并占用更多内存，不如重用相同的代码。
注意：这段代码只有在单线程运行时才能正常工作。如果您想在多线程上使用快速排序，请使用标准版本。

由于算法被分割开来，我们在Q_Sort中不需要临时左侧和右侧变量，因为它们保留在调用它们的原始函数中，所以我们只需要在Q_Sort 中使用的变量是Pivot。

接下来，如果您查看OptimizeQuickSort，您会看到我替换了

if(Left < Pivot)   &&    if(Right > Pivot)  

用

if(Left < Pivot - 1)   &&    if(Right > Pivot + 1)   

我的理由是，如果左侧和枢轴之间只有一个变量，那么该变量必须大于左侧。更重要的是，它必须是大于左侧且小于枢轴的唯一变量，因此没有理由对其进行排序。枢轴和右侧的情况也是如此。

End

好了，我说的就这么多。只是我认为可以改进快速排序的一些方面，至少在管理内存方面。我想补充的是，我已经看到许多其他方法可以使快速排序更有效，但几乎所有这些优势都只适用于那些语言，利用其特性，而我希望致力于整体设计。

如果有人能看到任何进一步改进我所做工作的办法，或者您认为这浪费时间，请告诉我。

John

历史

• 2011年1月6日：初始发布