算法导论 - 快速排序

老王

对于包含n个数的输入数组来说，快速排序是一种最坏情况时间复杂度为                              的排序算法，虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，它的期望时间复杂度是 ，而且 中隐含的常数因子非常小。快速排序属于原址排序，甚至在虚存环境中也能很好地工作。

与归并排序一样，快速排序也使用了分治思想。下面是对一个典型的数组A[p…r]进行快速排序的三步分治过程：

●  分解：数组A[p…r]被划分为两个（可能为空）子数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的每一个元素都小于等于A[q]，而A[q]也小于等于A[q+1…r]中的每个元素，其中，计算下标q也是划分过程的一部分；

●  解决：通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序；

●  合并：因为子数组都是原址排序的，所以不需要合并操作，数组A[p…r]已经有序。

[C++] 纯文本查看 复制代码

#include <stdio.h>

size_t Partition(int arrInt[], size_t nStart, size_t nEnd)
{
    int      nPivot = arrInt[nEnd];
    intptr_t nIndex = nStart - 1;
    int nTemp1, nTemp2;

    for (size_t i = nStart; i < nEnd; i++)
    {
        if (arrInt[i] <= nPivot)
        {
            nIndex++;

            nTemp1         = arrInt[nIndex];
            arrInt[nIndex] = arrInt[i];
            arrInt[i]      = nTemp1;
        }
    }

    nTemp2             = arrInt[nIndex + 1];
    arrInt[nIndex + 1] = arrInt[nEnd];
    arrInt[nEnd]       = nTemp2;

    return nIndex + 1;
}

void QuickSort(int arrInt[], size_t nStart, size_t nEnd)
{
    if (nStart < nEnd)
    {
        size_t nPartition = Partition(arrInt, nStart, nEnd);
        if (nPartition > 0)
            QuickSort(arrInt, nStart, nPartition - 1);
        QuickSort(arrInt, nPartition + 1, nEnd);
    }
}

int main()
{
    int arrInt[] = { 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, -1, -2, -3, -4, -5 };
    size_t nCount = sizeof(arrInt) / sizeof(arrInt[0]);

    QuickSort(arrInt, 0, nCount - 1);

    for (size_t i = 0; i < nCount; i++)
        printf("%d\n", arrInt[i]);

    return 0;
}