“为什么对于小规模元素列表来说，插入排序比快速排序更好？”这个问题的出现是因为作者在对比排序算法性能时发现，对于大于4个元素的数组，从快速排序切换到插入排序（尽管大家都说插入排序更好）实际上会降低性能（使用C语言的递归快速排序）。而对于这些数组，可以使用一个大小相关的最优排序算法进行排序。

但是需要注意的是，O(n...)只是比较次数（在这个特定情况下），而不是算法的速度。速度取决于具体的实现，例如快速排序函数是否递归以及如何快速处理函数调用。

最后但并非最不重要的是，大O符号只是一个上界。如果算法A需要10000nlogn次比较，而算法B需要10n^2次比较，那么第一个是O(nlogn)，第二个是O(n^2)。然而，第二个（可能）会更快。

对于好奇的人来说，当n大约等于9000时，O(N^2)的算法将比O(N log N)的算法更快。

大O符号不是一个上界。它描述了一个函数的渐近行为。

这就是20000000次比较和100000次比较。不可能。

可以查看Wolfram Alpha网站或者使用命令echo "10000 * 9000 * l(9000) ; 10 * 9000 * 9000" | bc -l来进行验证。

不对。它没有刻画渐近行为，它只是描述渐近行为。例如，任何O(n^2)算法也自动是O(n^3)。而f(n) = O(n^2)意味着存在某个k，使得|f(n)| <= k n^2。它是一个上界。

我错了。我以为你在谈论快速排序和插入排序。

来自维基百科的解释是：“大O符号根据函数的增长率进行刻画”。我们说的是同样的事情，只是在争论语义。

来自同一篇文章的同一段落：描述函数的大O符号通常只提供了函数增长速度的一个上界。

我们说的是同样的事情，只是在争论语义。

O(n)表示问题的规模足够大时的性能特征，忽略了常数因子和性能的增加偏移量。这是重要的，因为常数因子和开销在处理器和实现之间可以有很大的差异：在6502机器上运行单线程基本程序的性能将与在Intel i7级处理器上运行的C程序实现的相同算法非常不同。请注意，实现优化也是一个因素：即使所有其他因素都相同，对细节的关注通常可以获得重大的性能提升！

然而，常数因子和开销仍然很重要。如果您的应用程序确保N永远不会变得很大，那么O(N^2)与O(NlogN)的渐近行为并不起作用。

插入排序简单，并且对于小列表而言，通常比同样实现的快速排序或归并排序更快。这就是为什么实际的排序实现通常会在“基本情况”下退回到类似插入排序的方法，而不是一直递归到单个元素的原因。

问题的原因是：插入排序对于小规模的元素列表更好，因为快速排序在递归函数调用方面有额外的开销。插入排序比快速排序更稳定，需要更少的内存。

解决方法是：对于小规模的元素列表，使用插入排序而不是快速排序。插入排序不需要递归函数调用，因此在处理小规模数据时更快。此外，插入排序更稳定，即相同元素的顺序不会改变。插入排序还需要更少的内存。

插入排序的时间复杂度为O(n^2)，而快速排序的时间复杂度为O(nlogn)。因此，对于小规模的元素列表，插入排序更快。

插入排序的实现代码如下所示：

public void insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

快速排序的实现代码如下所示：

public void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int pivot = partition(array, low, high);
        quickSort(array, low, pivot - 1);
        quickSort(array, pivot + 1, high);
    }
}
public int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            swap(array, i, j);
        }
    }
    swap(array, i + 1, high);
    return i + 1;
}
public void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

对于小规模的元素列表，插入排序比快速排序更好。插入排序更快，更稳定，并且需要更少的内存。因此，在处理小规模数据时，选择插入排序可以提高效率。