遞歸到小的子區(qū)間時(shí)，可以考慮使用插入排序
當(dāng)數(shù)組遞歸到一定程度后，所進(jìn)行排序的數(shù)據(jù)個(gè)數(shù)較小，在這個(gè)時(shí)候使用插入排序的效率反而會(huì)比繼續(xù)快排遞歸的效率要高

代碼實(shí)現(xiàn)：

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

? ? // 小區(qū)間優(yōu)化，小區(qū)間不再遞歸分割排序，降低遞歸次數(shù)
? ? if ((end - begin + 1) > 10)
? ? {
? ? ? ? int keyi = PartSort3(a, begin, end);//調(diào)用前后指針快排

? ? ? ? // [begin, keyi-1] keyi [keyi+1, end]
? ? ? ? QuickSortOp(a, begin, keyi - 1);
? ? ? ? QuickSortOp(a, keyi + 1, end);
? ? }
? ? else//當(dāng)排序的數(shù)據(jù)個(gè)數(shù)小于或等于10個(gè)時(shí)，使用插入排序
? ? {
? ? ? ? InsertSort(a + begin, end - begin + 1);
? ? }
}

為了驗(yàn)證這種排序是否有優(yōu)化效果，我們可以將兩種排序進(jìn)行比較：

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:%d\n", end1 - begin1);
? ? printf("QuickSort:%d\n", end2 - begin2);
? ??
? ? free(a1);
? ? free(a2);
}

代碼實(shí)現(xiàn)：

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);
}