shell排序算法真的优势明显？

Question

这是shell排序算法

#include<stdio.h>
int v[6] = {1,4,6,2,10,8};
int i;
shellsort(int v[],int n)
{
    int gap, i, j, temp;
    for(gap = n/2;gap > 0;gap = gap/2){
        for(i = gap;i < n;i++){
            for(j = i - gap;j >= 0 && v[j] > v[j + gap];j = j - gap){
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }
}
int main()
{
    shellsort(v,6);
    for(i = 0;i < 6;i++){
        printf("%d\t",v[i]);
    }
}

这是冒泡排序算法

#include<stdio.h>
int v[6] = {1,4,6,2,10,8};
int i;
bublesort(int v[],int n)
{
    int i,j,t;
    for(i=0;i<n-1;i++)//n个数的数列总共扫描n-1次
    {
        for(j=0;j<n-i-1;j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束
        {
            if(v[j]>v[j+1])//后一位数比前一位数小的话，就交换两个数的位置（升序）
            {
               t=v[j+1];
               v[j+1]=v[j];
               v[j]=t;
            }
        }
    }
}
int main()
{
    bublesort(v,6);
    for(i = 0;i < 6;i++){
        printf("%d\t",v[i]);
    }
}

看这时间岂不是差不多？

Answer 1

你这6个数字能看出什么大小呢...你这个耗时可不只是执行排序需要的时间. 你用一个100万个数的数组输进去你就知道了, 冒泡是n², 100万是1e6, 这里冒泡是1e12的量级, 而shell最坏情况是n², 最好n, 平均大概是n的1.4次左右, 这里也就是1e8