希尔排序,快速排序，冒泡排序的比较。
希尔排序基本思想
基本思想：
先取一个小于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");
}