将插入排序与快速排序函数关系结合起来

Question

混合排序： 数组A从int到int的元素索引，我们最初用快速排序方法对A []进行排序，最初将数据放在数组的末尾，然后递归调用快速排序，但是数组中的元素数量是小于t，然后我们停止调用快速排序并通过插入排序对元素的其余部分进行排序，混合函数应该只返回调用插入排序的次数。 main函数打印出调用插入排序的次数。

我写了几次这段代码，但是函数关系总是如此混乱，我无法诊断出大量的bug信息。而且我不知道为什么它在实践中比与randomized_quick_sort结合更快。谢谢

#include<stdio.h>
#include<stdlib.h>
// hybrid quick sort
int hybridsort(int A[], int p, int q, int t);

int  main() {
  int n = 9, t = 3;
  int A[9] = {1, 8, 6, 3, 2, 7, 4, 9, 10};

  for(int i = 0; i < 9; i++)printf(" %d", A[i]);
  printf("\n");

  int res = hybridsort(A, 0, n - 1, t);// rest
  printf("No. of calls = %d\n",res);

  for(int i = 0; i< 9; i++)printf("%d", A[i]);
  printf("\n");

  return 0;
}
int hybridsort(int A[], int p, int r, int t){
  int n, count;
  count = 0;
  int i, j, key;
  n = p - r + 1;
  // if No.elements < t, # of insertion sort gets called
  if(n >= t && p > r ){
      quicksort(A, p, r);
    }
    else{
      // insertionsort
      count = count + 1;
      for(j = 1; j < 6; j++){
      key = A[j];
      i = j - 1;
      while(i > -1 && A[i] > key){
      A[i + 1] = A[i];
      i = i - 1;
    }
    A[i + 1] = key;
   }

 }
}

return count;
}
void quicksort(int A[], int p, int r){
  int q ;
  if(p < r){

    q = partition(A, p,r);
    quicksort(A, p, q - 1);
    quicksort(A, q + 1, r);
  }
}

int partition(int A[], int p, int r){
  int x, i, j, tmp;
  x = A[r];//pivot
  i = p - 1;
  for(j = p; j < r; j++){
    if(A[j] <= x){
      i += 1;
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }

  }
  tmp = A[i + 1];
  A[i + 1] = A[r];
  A[r] = tmp;
  return i + 1 ;// pivot index position after sorting

}

Answer 1

示例混合快速+插入排序。主程序将调用QuickSort（），它将调用InsertionSort以获得<= 32的子数组。

void InsertionSort(int a[], size_t lo, size_t hi)
{
size_t i = lo+1;
size_t j;
int t;
    while(i <= hi){
        t = a[i];
        j = i;
        while((j > lo) && a[j-1] > t){
            a[j] = a[j-1];
            j -= 1;
        }
    a[j] = t;
    i += 1;
    }
}

void QuickSort(int a[], size_t lo, size_t hi)
{
    if(lo >= hi)
        return;
    if((hi-lo) < 32){
        InsertionSort(a, lo, hi);
        return;
    }
    int pivot = a[lo + (hi - lo) / 2];
    int t;
    size_t i = lo - 1;
    size_t j = hi + 1;
    while(1)
    {
        while (a[++i] < pivot);
        while (a[--j] > pivot);
        if (i >= j)
            break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    QuickSort(a, lo, j);
    QuickSort(a, j + 1, hi);
}