当前位置:   article > 正文

希尔排序以及对希尔排序增量的讨论和与插入排序的对比_希尔排序不同增量对比

希尔排序不同增量对比
概要:

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:
  1. 1,插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。这是为啥呢?点击去看看,
  2. 2,但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
基本思想:

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量
 为1
,即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法;一般的初次取序列的一半为增量,以后每次减半,直到增量为1。
如图(声明下图实在网上找到的,他画得好)


代码:

  1. void ShellSort2(int arr[], int n) {
  2. int tab = n / 2;//初始增量
  3. while (tab >= 1) {
  4. //对每组进行分组
  5. for (int i = 0; i < tab; i++) {
  6. //arr[i],arr[i+tab],arr[i+2*tab].....进行插入排序
  7. for (int j = i + tab; j < n; j += tab) {
  8. int k;
  9. T e = arr[j];
  10. for (k = j; k >= tab&& e<arr[k - tab]; k -= tab)
  11. arr[k] = arr[k - tab];
  12. arr[k] = e;
  13. }
  14. }
  15. tab /= t;
  16. }
  17. }

对希尔排序增量的讨论

这里添加三个方法:generaRandomArray:生成随机数组,copyArray:复制数组,testSort:测试运行时间

  1. //生成n个的随机数组,,每个元素的范围{RangeL,RangeR}
  2. int * generateRandromArray(int n, int rangel, int rangeR) {
  3. int *arr = new int[n];
  4. srand(time(0));
  5. for (int i = 0; i < n; i++) {
  6. arr[i] = rand() % (rangeR - rangel + 1) + rangel+1;
  7. }
  8. return arr;
  9. }
  10. //数组赋值
  11. int * copyArray(int arr[], int n) {
  12. int * temp = new int[n];
  13. for (int i = 0; i < n; i++)
  14. temp[i] = arr[i];
  15. return temp;
  16. }
  17. void testSort(string sortName, void(*sort)(int[], int n, int t), int arr[], int n, int t) {
  18. clock_t startTime = clock();//开始时间
  19. sort(arr, n, t);//运行函数
  20. clock_t endTime = clock();//结束时间
  21. cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC<<" s" << endl;//打印时间
  22. }

并把上述希尔排序的函数该为一下代码,方便更改增量:

  1. void ShellSort2(T arr[], int n,int t) {//t表示初始增量
  2. int tab = n / t;
  3. while (tab >= 1) {
  4. //对每组进行分组
  5. for (int i = 0; i < tab; i++) {
  6. //arr[i],arr[i+tab],arr[i+2*tab].....进行插入排序
  7. for (int j = i + tab; j < n; j += tab) {
  8. int k;
  9. T e = arr[j];
  10. for (k = j; k >= tab&& e<arr[k - tab]; k -= tab)
  11. arr[k] = arr[k - tab];
  12. arr[k] = e;
  13. }
  14. }
  15. tab /= t;
  16. }
  17. }


在main函数中:

  1. int main() {
  2. int n = 1000000;
  3. int *arr = generateRandromArray(n, 0, n);//生成随机数组
  4. int *arr1,*arr2,*arr3,*arr4,*arr5;
  5. //复制数组
  6. arr1 =copyArray(arr, n);
  7. arr2 =copyArray(arr, n);
  8. arr3 =copyArray(arr, n);
  9. arr4 =copyArray(arr, n);
  10. arr5 =copyArray(arr, n);
  11. testSort("希尔排序 2 :", ShellSort2, arr, n, 2);
  12. testSort("希尔排序 3 :", ShellSort2, arr1, n, 3);
  13. testSort("希尔排序 4 :", ShellSort2, arr2, n, 4);
  14. testSort("希尔排序 5 :", ShellSort2, arr3, n, 5);
  15. testSort("希尔排序 10 :", ShellSort2, arr4, n, 10);
  16. testSort("希尔排序100 :", ShellSort2, arr5, n, 100);
  17. return 0;
  18. }

运行结果:

为了对比,我多运行几次,随机取三个结果。

结果1:


结果2:


结果3:


通过三次对比发现,当增量为5的时候效率是最好的。这个也说不准,反正5过后,10,100,效率就原来越低,这也说明了希尔排序是插入排序的一种“缩小增量的排序”

希尔排序与插入排序的对比:

利用上述代码,用100000数据量(上面是1000000),把增量改变为n(就是插入排序了)与增量为5的希尔排序做对比:

代码:

  1. int main() {
  2. int n = 1000000;
  3. int *arr = generateRandromArray(n, 0, n);//生成随机数组
  4. int *arr1,*arr2,*arr3,*arr4,*arr5;
  5. //复制数组
  6. arr1 =copyArray(arr, n);
  7. arr2 =copyArray(arr, n);
  8. arr3 =copyArray(arr, n);
  9. testSort("希尔排序 n :", ShellSort2, arr, n, n);
  10. testSort("希尔排序 5 :", ShellSort2, arr3, n, 5);
  11. return 0;
  12. }
结果:

look! 多少倍,自己体会吧微笑

总结:

好好领悟,多练习!






声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/786857
推荐阅读
相关标签
  

闽ICP备14008679号