C中的混合quicksort+insertion排序

Question

我被要求做两个版本的混合快速排序；

当元素小于10个调用插入排序以对每个subproblem

• When排序元素小于10时，停止快速排序，并对整个未排序的数组使用插入排序。

这是我第一次练习的快速代码。我似乎找不到每个人之间的编码差异。我知道这是一个很小的区别。我试了很多次

void quickSort(int array[], int start, int finish){
    int pivot;
    if ( low < high ){
        pivot = partition(A, start, finish);
        if ((high - low) < 10){
            insertionSort(A, start, finish);
        }
        quickSort(A, low, pivot - 1);
        quickSort(A, pivot + 1, high);
    }
}

Answer 1

第一个选项是插入排序小分区，因为它们是在递归quickSort函数中找到的：

void quickSort(int *A, int low, int high) {
    if ((high - low) < 10) { // insertionSort small partitions
        insertionSort(A, low, high);
        return;
    }
    if (low < high) {
        int pivot = partition(A, low, high);
        quickSort(A, low, pivot - 1);
        quickSort(A, pivot + 1, high);
    }
}

第二个选项是在递归期间忽略小分区。这使得数组成为一系列小的、几乎排序的分区。最后的插入排序然后完成对数组的排序。此示例将递归部分移动到它自己的助手函数中。

void quickSort_helper(int *A, int low, int high) {
    if ((high - low) > 10) { // ignore small partitions
        int pivot = partition(A, low, high);
        quickSort_helper(A, low, pivot - 1);
        quickSort_helper(A, pivot + 1, high);
    }
}

void quickSort(int *A, int low, int high) {
    quickSort_helper(A, low, high);
    insertionSort(A, low, high);
}

请注意，我还没有测试过这段代码，但它显示了总体思路。