递归到小的子区间时,可以考虑使用插入排序
当数组递归到一定程度后,所进行排序的数据个数较小,在这个时候使用插入排序的效率反而会比继续快排递归的效率要高
代码实现:
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:%d\n", end1 - begin1);
? ? printf("QuickSort:%d\n", 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);
}