[原创]感谢燕子,关于shell的本质
上次燕子的话真的雾啊(她说:shell是辅助排序),今天翻了翻借来的书，无意看到了关于shell的链表版本，它提示用冒泡排序..这下，我似乎了解到了shell的本质.....下面仅个人观点，如有错误请指出...其实shell的本质就是辅助排序,可以是一些基本排序的扩展....一下子就多了许多排序的变种，但是效率却不彰....我做了测试代码，只有基于插入的希尔效率才有所提高，而其他的O(n^2)排序甚至比扩展前还差...
测试的一组数据:
程序代码：/*最好情况下 冒泡排序: 350ms 希尔冒泡: 4346ms 选择排序: 391ms 希尔选择: 791ms 插入排序: 0ms 希尔插入: 0ms 平均情况 冒泡排序: 3495ms 希尔冒泡: 7421ms 选择排序: 410ms 希尔选择: 801ms 插入排序: 271ms 希尔插入: 0ms 最坏情况 冒泡排序: 6209ms 希尔冒泡: 10665ms 选择排序: 391ms 希尔选择: 801ms 插入排序: 611ms 希尔插入: 0ms*/
代码如下:
/********************************************************
** Highlight software by yzfy(雨中飞燕) http:// *
*********************************************************/
#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]]
)