c - 使用插入排序和快速排序

Question

为什么大多数人对元素少于n的子数组使用插入排序来优化快速排序？我编写了一个插入排序函数和希尔排序函数，并使用一些具有 10、50、100 个元素的随机数组来调用它们。看来shell排序更快(我只用clock()测量了时间；我不知道这是否是一个好方法)。如果它比插入排序更快，为什么没有更多的人使用希尔排序呢？我的插入排序函数有错误吗？

我的代码:

double insertionSort(int *a, int size)
{
    clock_t start, end;
    int i, temp, pos;

    start = clock();

    for (i = 1; i < size; i++) {
        temp = a[i];
        pos = i - 1;

        while (pos >= 0 && a[pos] > temp) {
            a[pos + 1] = a[pos];
            pos--;
        }

        a[pos + 1] = temp;

     }

     end = clock();

     return (double)(end - start) / CLOCKS_PER_SEC * 1000;
}

double shellSort(int *a, int size)
{
    int gaps[8] = {701, 301, 132, 57, 23, 10, 4, 1};
    int i, k , temp, pos;
    clock_t start, end;

    start = clock();

    for (i = 0; i < 8; i++)
        for (k = gaps[i]; k < size; k++) {
            temp = a[k];
            pos = k - gaps[i];
            while (pos >= 0 && a[pos] > temp) {
                a[pos + gaps[i]] = a[pos];
                pos -= gaps[i];
            }
            a[pos + gaps[i]] = temp;
        }

    end = clock();

    return (double)(end - start) / CLOCKS_PER_SEC * 1000;
}

5 的输出:

Insertion Sort : Sorted in 0.002000 milliseconds
Shell Sort : Sorted in 0.001000 milliseconds

10 的输出:

Insertion Sort : Sorted in 0.004000 milliseconds
Shell Sort : Sorted in 0.001000 milliseconds

50 的输出:

Insertion Sort : Sorted in 0.007000 milliseconds
Shell Sort : Sorted in 0.007000 milliseconds

100 的输出:

Insertion Sort : Sorted in 0.015000 milliseconds
Shell Sort : Sorted in 0.014000 milliseconds

200 的输出:

Insertion Sort : Sorted in 0.040000 milliseconds
Shell Sort : Sorted in 0.028000 milliseconds

Answer 1

检查此链接

enter link description here

排序算法最坏情况时间平均情况时间

插入 O(n^2) O(n^2)

快速排序 O(n^2) O(nlogn)