Java 快速排序

Question

我正在使用 Java 实现快速排序，要求如下:

Use recursion (in your quicksort implementation) down to a stopping case of a partition of size k or smaller. For these partitions, use an insertion sort to finish.

我对如何实现这个甚至它的要求感到困惑。这是我对普通快速排序的看法。我该如何修改它以满足要求？

public static void quick_srt(int array[],int low, int n){
    int lo = low;
    int hi = n;
    if (lo >= n) {
      return;
    }

    int mid = array[(lo + hi) / 2];

    while (lo < hi) {
      while (lo<hi && array[lo] < mid) {
        lo++;
      }
      while (lo<hi && array[hi] > mid) {
        hi--;
      }

      if (lo < hi) {
        int T = array[lo];
        array[lo] = array[hi];
        array[hi] = T;
      }
    }

    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
    quick_srt(array, low, lo);
    quick_srt(array, lo == low ? lo+1 : lo, n);
}

Answer 1

分区大小为hi - lo。所以你可以添加类似的东西，

int k = 7;
// ...
if (hi - lo < k) {
    insertion_srt(array, lo, hi);
    return;
}

在 int mid 之前。实现 insertion_srt(int[], int, int) 留给读者作为练习。