快速排序的运行时间可以在实践中通过利用插入的快速运行时间排序，当其输入近排序的优势得到改善。 当快速排序的呼吁比k个元素少一个子阵列，让它简单地返回不排序的子数组。顶层调用快速排序的回报，运行插入排序整个阵列上完成分类处理后。

The running time of quick sort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. When quicksort is called on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top level call to quicksort returns, run insertion sort on the entire array to finish the sorting process.

认为，这种排序算法为O（NK + N的log（n / k））的预期时间。应该如何K为采摘，无论在理论上还是在实践中？

Argue that this sorting algorithm runs in O(nk + n log (n/k)) expected time. How should k be picked, both in theory and in practice?

推荐答案

粗略地说：

快速排序是 O（N日志（N））

由于停止时，子列表是长度为k的，快速排序部分变成 O（N日志（N / K）），因为深，你必须去用K的因子降低。

By stopping when the sub-lists are of length k, the quicksort part becomes O(N log(N/K)) because the depth you have to go to is reduced by a factor of K.

插入排序通常是为O（n ^ 2）因为你顶多移动的每个元素n / 2次平均，和1/2的因素是忽略。

The insertion sort would normally be O(n^2) because you move each element at most n/2 times on average, and the factor of 1/2 is ignored.

由于插入排序现在是固定长度阵列上，你只移动的每个元素最多k个位置。这会导致你的操作是插入排序部分 O（NK）。

Because the insertion sort is now on a fixed length array, you only move each element at most k places. This results in the insertion sort part of your operation being O(NK).

在理论上，较大的K值可以较快排序，但依赖于被分类为大项的数目。在实践中，k的最佳值将取决于n的值，并且可以通过微分函数在k-治疗N作为一个恒定的角度来找到。

In theory, larger values of K give faster sorts, but that relies on the number of items being sorted being large. In practise, the best value of k will depend on the value of n and can be found by differentiating the function in terms of k treating n as a constant.

这个答案可能需要一些去肉出来，正式证明，如果它是一门功课的问题作为桑德兰建议。

This answer will probably need some fleshing out and formal proof if it is a homework question as Delan suggests.