数据结构之快速排序优化

递归到小的子区间时，可以考虑使用插入排序
当数组递归到一定程度后，所进行排序的数据个数较小，在这个时候使用插入排序的效率反而会比继续快排递归的效率要高

代码实现：

void QuickSortOp(int* a, int begin, int end)
{
    if (begin >= end)
        return;

    // 小区间优化，小区间不再递归分割排序，降低递归次数
    if ((end – begin + 1) > 10)
    {
        int keyi = PartSort3(a, begin, end);//调用前后指针快排

        // [begin, keyi-1] keyi [keyi+1, end]
        QuickSortOp(a, begin, keyi – 1);
        QuickSortOp(a, keyi + 1, end);
    }
    else//当排序的数据个数小于或等于10个时，使用插入排序
    {
        InsertSort(a + begin, end – begin + 1);
    }
}

为了验证这种排序是否有优化效果，我们可以将两种排序进行比较：

void TestOP()
{
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);

    for (int i = N – 1; i >= 0; –i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
    }

    int begin1 = clock();
    QuickSortOp(a1, 0, N – 1);
    int end1 = clock();

    int begin2 = clock();
    QuickSort(a2, 0, N – 1);
    int end2 = clock();

    printf(“QuickSortOp:%dn”, end1 – begin1);
    printf(“QuickSort:%dn”, end2 – begin2);
    
    free(a1);
    free(a2);
}

代码实现：

void QuickSortNonR(int* a, int begin, int end)
{
    ST st;
    STInit(&st);
    STPush(&st, end);
    STPush(&st, begin);
    while (!STEmpty(&st))
    {
        int left = STTop(&st);
        STPop(&st);

        int right = STTop(&st);
        STPop(&st);

        int keyi = PartSort1(a, left, right);
        // [lefy,keyi-1] keyi [keyi+1, right]
        if (keyi + 1 < right)
        {
            STPush(&st, right);
            STPush(&st, keyi + 1);
        }

        if (left < keyi – 1)
        {
            STPush(&st, keyi – 1);
            STPush(&st, left);
        }
    }

    STDestroy(&st);
}