[原创]感谢燕子,关于shell的本质

上次燕子的话真的雾啊(她说:shell是辅助排序),今天翻了翻借来的书，无意看到了关于shell的链表版本，它提示用冒泡排序..这下，我似乎了解到了shell的本质.....下面仅个人观点，如有错误请指出...
   其实shell的本质就是辅助排序,可以是一些基本排序的扩展....一下子就多了许多排序的变种，但是效率却不彰....我做了测试代码，只有基于插入的希尔效率才有所提高，而其他的O(n^2)排序甚至比扩展前还差...
测试的一组数据:

代码如下:
/********************************************************
** Highlight software by yzfy(雨中飞燕) http://yzfy.org *
*********************************************************/
#include <ctime>
#include<cstdlib>
#include<fstream>
#include <string>
using namespace std;

ofstream out("tae.out");
#define OutPut(s) out<<s;
//时间测试
void test(void (*func)(int* ,int,int =1,int=0),int* arr,int size_a)
{
    clock_t start = clock();
    func(arr,size_a);
    out<<clock()-start<<"ms"<<endl;
}
//初始化数组
void intiArray(int* arr,int size_a,int c)
{
    int i;
    switch(c)
    {
    case 1:  for(i=0;i<size_a;++i) arr[i]=i;
            break;
    case -1:  for(i=0;i<size_a;++i) arr[i]=size_a-i;
            break;
    case 0:  srand((unsigned)time(0));
            for(i=0;i<size_a;++i) arr[i]= rand()%10000001;
            break;
    }
}
//冒泡排序
void bubbleSort(int* arr,int size_a,int inc =1,int start=0)
{
    for(int i=0;i<size_a;++i)
    for(int j=start;j<size_a-1-i;j+=inc)
        if( arr[j]>arr[j+1] ) swap(arr,j,j+1);
}
//基于冒泡排序的希尔排序
void shellBubble(int* arr,int size_a,int,int)
{
    int inc = size_a;
    do
    {
        inc=inc/3+1;
        for(int s=0;s<inc;++s)  //排序子表
            bubbleSort(arr,size_a,inc,s);
    }while(inc>1);
}
//选择排序
void selectSort(int* arr,int size_a,int inc =1,int start=0)
{
    for(int i=start;i<size_a-1;i+=inc)
    {
        int min = i;
        for(int j=i+inc;j<size_a;j+=inc)
            if(arr[min]>arr[j]) min=j;
        swap(arr,i,min);
    }
}
//基于选择排序的希尔排序
void shellSelect(int* arr,int size_a,int,int)
{
    int inc = size_a;
    do
    {
        inc=inc/3+1;
        for(int s=0;s<inc;++s)  // 排序子表
            selectSort(arr,size_a,inc,s);
    }while(inc>1);
}
//插入排序
void insertSort(int* arr,int size_a,int inc=1,int start=0)
{
    for(int i=start+inc;i<size_a;i+=inc)
    {
        int key = (i)[arr];
        int j=i-inc;
        for(;j>=start&&arr[j]>key;j-=inc)
            arr[j+inc]=arr[j];
        arr[j+inc]=key;
    }
}
//基于插入排序的希尔排序
void shellInsert(int* arr,int size_a,int,int)
{
    int inc=size_a;
    do
    {
        inc=inc/3+1;
        for(int s=0;s<inc;++s)  //排序子表
            insertSort(arr,size_a,inc,s);
    }while(inc>1);
}
int main(void)
{
    #ifndef N
    #define N 100000
    #endif

    int array[N];
    //1代表最好情况，-1代表最坏情况，0代表平均情况

    //最好情况
    OutPut("   最好情况下") out<<endl;
    OutPut("冒泡排序: ")
    intiArray(array,N,1);
    test(bubbleSort,array,N);
    OutPut("希尔冒泡: ")
    intiArray(array,N,1);
    test(shellBubble,array,N);
    OutPut("选择排序: ");
    intiArray(array,N,1);
    test(selectSort,array,N);
    OutPut("希尔选择: ");
    intiArray(array,N,1);
    test(shellSelect,array,N);
    OutPut("插入排序: ");
    intiArray(array,N,1);
    test(insertSort,array,N);
    OutPut("希尔插入: ");
    intiArray(array,N,1);
    test(shellInsert,array,N);
    //平均情况
    OutPut("   平均情况") out<<endl;
    OutPut("冒泡排序: ")
    intiArray(array,N,0);
    test(bubbleSort,array,N);
    OutPut("希尔冒泡: ")
    intiArray(array,N,0);
    test(shellBubble,array,N);
    OutPut("选择排序: ");
    intiArray(array,N,0);
    test(selectSort,array,N);
    OutPut("希尔选择: ");
    intiArray(array,N,0);
    test(shellSelect,array,N);
    OutPut("插入排序: ");
    intiArray(array,N,0);
    test(insertSort,array,N);
    OutPut("希尔插入: ");
    intiArray(array,N,0);
    test(shellInsert,array,N);
    //最坏情况
    OutPut("   最坏情况") out<<endl;
    OutPut("冒泡排序: ")
    intiArray(array,N,-1);
    test(bubbleSort,array,N);
    OutPut("希尔冒泡: ")
    intiArray(array,N,-1);
    test(shellBubble,array,N);
    OutPut("选择排序: ");
    intiArray(array,N,-1);
    test(selectSort,array,N);
    OutPut("希尔选择: ");
    intiArray(array,N,-1);
    test(shellSelect,array,N);
    OutPut("插入排序: ");
    intiArray(array,N,-1);
    test(insertSort,array,N);
    OutPut("希尔插入: ");
    intiArray(array,N,-1);
    test(shellInsert,array,N);
    return 0;
}
再次感谢燕子.....

[[it] 本帖最后由 中学者 于 2008-5-10 16:23 编辑 [/it]]
----------------解决方案--------------------------------------------------------
燕子啊？？？怎么加上code 标签就不高亮啊?bug?
----------------解决方案--------------------------------------------------------
中学者，一万个数能比个什么出来，要像我一样，拿十万个数字才有效果……本来是想100W的，但是因为有简单排序，懒得等那么长时间，就10W了事了……
发现自己的帖子居然没人顶呢，就顶顶你的吧………………
----------------解决方案--------------------------------------------------------
你要问静夜思，而不是燕子……
----------------解决方案--------------------------------------------------------
电脑又老又慢，似乎测不了那么多啊~
----------------解决方案--------------------------------------------------------
code标签的目的就是让它里面的所有UBB标签失效

[color=white]
----------------解决方案--------------------------------------------------------
个人理解,shell排序就是插入排序的优化,
他利用了插入排序的两个特点
1.对比较少量的数据,排序速度很快
2.对基本有序的数据,排序速度很快
----------------解决方案--------------------------------------------------------
No, Shell排序必须要和另一种排序进行组合，否则Shell排本身不能一定保证最后的结果完全有序

[color=white]
----------------解决方案--------------------------------------------------------
我比较同意燕子观点..Shell只是满足增量有序..但是要怎么有序..还是要其它方法辅助的....
----------------解决方案--------------------------------------------------------
shell排序只是一种优化,是需要其它排序方法辅助的,而且这种辅助的方法,只能是插入排序,否则就如楼主所测试的结果,不仅不是优化,反而是.....(呃,优化的反义词是什么呢??? )
----------------解决方案--------------------------------------------------------