希尔排序,快速排序，冒泡排序的比较。

希尔排序基本思想

基本思想：

　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

　该方法实质上是一种分组插入方法。

给定实例的shell排序的排序过程

　假设待排序文件有10个记录，其关键字分别是：

49，38，65，97，76，13，27，49，55，04。

　增量序列的取值依次为：

5，3，1

　排序过程如【动画模拟演示】。

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.2.1.htm

#if0

2012-12-0918:23:18.019排序算法[974:707]before:

2012-12-0918:23:54.122排序算法[974:707]after:26.1

2012-12-0918:24:58.085排序算法[999:707]before:

2012-12-0918:25:00.967排序算法[999:707]after:2.0

2012-12-0918:40:25.880排序算法[1081:707]before:

2012-12-0918:40:30.379排序算法[1081:707]after:4.5

2012-12-0918:41:30.726排序算法[1112:707]before:

2012-12-0918:41:33.741排序算法[1112:707]after:

2012-12-0918:42:12.793排序算法[1135:707]after:

2012-12-0918:42:10.099排序算法[1135:707]before:

2012-12-0918:43:06.847排序算法[1161:707]before:

2012-12-0918:43:33.619排序算法[1161:707]after:

#endif

#import<Foundation/Foundation.h>

//#include<stdio.h>

//#include<stdlib.h>

//#include<math.h>

#defineMAX118//这里设定要对多少个元素排序

voidshellsort(intA[],intN,int*);

voidprintarray(intA[]);

voidmysort(intm[]);

voidquick_sort(intarr[],intleft,intright);

intmain(intargc,constchar*argv[])

{

@autoreleasepool{

inti,s[MAX1];

int*sed;

intsedgewick[]={//Sedgewick增量赛奇维克增量

1073643521,603906049,268386305,150958081,67084289,

37730305,16764929,9427969,4188161,2354689,

1045505,587521,260609,146305,64769,

36289,16001,8929,3905,2161,

929,505,209,109,41,

19,5,1,0};//用0标记终点

for(sed=sedgewick;*sed>MAX1;sed++)//增量必须小于元素个数,并且是小于增量中的最大的一个。

{}

for(i=0;i<MAX1;i++){

s[i]=1+(int)((float)MAX1*rand()/(RAND_MAX+1.0));

}

//}

NSLog(@"before:");

//printarray(s);

NSLog(@"======%d======",*sed);

shellsort(s,MAX1,sed);//希尔排序

//mysort(s);//冒泡排序。

//quick_sort(s,0,sizeofs/sizeof(int)-1);//快速排序。

NSLog(@"after:");

printarray(s);

//for(inti=0;i<2;i++)//这里不加{}表示他把下个for循环都包裹了。因为他包裹的是一个if语句或一个for或一个”；“结尾的语句。

////{

//for(intj=0;j<2;j++){

//NSLog(@"我");

//}

////}

}

return0;

}

voidshellsort(intv[],intn,int*sed)//v[]是数组的值，n为数组的个数。sed赛奇维克增量

{

inti,j,temp;

int*gap;

for(gap=sed;*gap>0;gap++)//看有几个赛奇维克。共10个数。2,1;

for(i=*gap;i<n;i++)//越来越多的循环。

for(j=i-*gap;j>=0&&v[j]>v[j+*gap];j-=*gap){

temp=v[j];

v[j]=v[j+*gap];

v[j+*gap]=temp;

}

}

voidmysort(intm[]){//普通的冒泡

inttemp;

for(inti=0;i<MAX1;i++){

for(intj=i;j<MAX1-1;j++){

if(m[i]>m[j]){

temp=m[i];

m[i]=m[j];

m[j]=temp;

}

}

}

}

voidquick_sort(intarr[],intleft,intright)//快速排序。

{

inti=left,j=right,temp=arr[i];

while(i<j)

{

while(i<j&&temp<=arr[j])

{

j--;//右边找到比temp小的那个数

}

arr[i]=arr[j];

while(i<j&&arr[i]<=temp)

{

i++;//左边找到比temp大的那个数

}

arr[j]=arr[i];

}

arr[i]=temp;

if(i-1>left)quick_sort(arr,left,i-1);

if(i+1<right)quick_sort(arr,i+1,right);

}

voidprintarray(inta[])

{

inti;

for(i=0;i<MAX1;i++)

printf("%d",a[i]);

printf("/n");

}