网站建站常见问题,网站排名突然下降,wordpress制作app插件,济南造价工程信息网希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是#xff1a;先选定一个整数#xff0c;把待排序文件中所有记录分成个gap组#xff0c;所有距离为的记录分在同一组内#xff0c;并对每一组内的记录进行排序。然后#xff0c;取#xff0c;重复上述分组和排序…希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个gap组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。
实现
希尔排序是对直接插入排序的一个优化希尔排序分为预排和正式排序两个阶段预排是把n个数分成gap组每个组执行一遍直接插入排序但是每次end不再是end--或者end1,而是end-gap和a[endgap]tmp。
gap我们初始给它赋值为n也就是分成n组每组一个数这样的话也就相当于直接插入排序因为直接插入排序我们是每次挪一个位置和Tmp比较。 for (int i 0; i n - gap; i)
{int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;
}
上述操作也就是把直接插入排序的1换成了gap而已而这也就相当于gap等于1时候的预排如果这样操作的话就和直接插入排序没有任何区别所以我们把gapn后第一次预排之前要 gapgap/31这个操作就是把n个数据分成3组1是为了保证让gap不为0,如果gap2,2/30,那分成0组是什么意思我把n个数据分成3组进行一次预排第一次预排之后每一组肯定都是有序的这时gap再进行一次 gapgap/31;也就是再把他划分为更少的组而我们使gapgap/31这个加1还有最重要的目的就是一定会使gap1所有我们当gap1时不再往下划分Gap,这个时候就是正式排序
void ShellSort(int* a, int n)//希尔排序
{int gap n;while (gap 1){.......}
}
gap越小分的组越少预排的结果越接近有序的。当gap1时进行的是预排序当gap1,进行的是正式排序。这就是希尔排序。
测试
#includestdio.h
int main()
{int a[] { 6,1,2,7,9,3,4,5,10,8 };int n sizeof(a) / sizeof(a[0]);ShelltSort(a, n);for (int i 0; i n; i){printf(%d , a[i]);}return 0;
}时间复杂度
希尔排序的时间复杂度非常难计算我们只需要记住它大概在O(N^1.3)左右就可以了。
性能测试
我们使用c语言随机生成的随机数对这两个排序进行性能测试我们测试的是1000000个随机数由于C语言生成的随机数只能有30000多个所以我们在每个随机数后面再加上第几次循环的i可以大大减少重复的数据
#includestdio.h
#includetime.h
#includestdlib.h
srand(time(0));
const int N 1000000;
int* a1 (int*)malloc(sizeof(int)*N);
int* a2 (int*)malloc(sizeof(int) * N);
for (int i 0; i N; i)
{a1[i] rand()i;a2[i] a1[i];}
int begin1 clock();
InsertSort(a1, N);
int end1 clock();int begin2 clock();
ShellSort(a2, N);
int end2 clock();printf(InsertSort:%d\n, end1 - begin1);
printf(ShellSort:%d\n, end2 - begin2);free(a1);
free(a2); 结果如上由此可以看出希尔排序无非就是比直接插入排序多了多次预排直接的差异竟然如此之大。
源代码
void ShellSort(int* a, int n)//希尔排序
{int gap n;while (gap 1){gap gap/31;//1保证最后一次gap为1也就是进行直接插入排序gap越小预排的结果越接近有序for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
