首页 > 代码库 > 希尔排序的C++实现
希尔排序的C++实现
1.原理介绍
希尔排序又称为缩小增量排序，由D.L.Shell在1959年提出而得名。
该算法先取一个小于数据表中元素个数 n 的整数gap, 并以此作为第一个间隔，将数据分为gap个子序列，所有距离为gap的对象存放在同一个子序列中，于是数据表中的元素就被分成了gap个组，分组确定后，在每一个小组中进行直接插入排序（参考直接插入排序与二分插入排序的C++实现），局部排序完成后，缩小gap, 重复上述步骤，直至取到gap=1时，完成最后一次直接插入排序。
为什么这个算法会起作用：开始的时候gap较大，子序列中的数据较少，所以最开始的时候算法运行较快，随着算法进行，gap 逐渐变小，子序列中元素的个数也就越来越多，所以排序工作可能会变慢，但是由于前面已经完成了部分排序工作，因而在很大程度上减轻了后来的工作量，于是最终总体的排序速度还是比较快的。
2.举例说明
数据表：
第一轮：数据表共有6个元素，初始化gap = 6, 第一轮取取gap = MT(gap/2)=3,注意这里MT(X)表示取不小于X的最小整数，即向上取整！
第二轮：gap = MT(gap/2)=2;
第三轮：gap = MT(gap/2) = 1,但是由于第二轮结束后数据表实际上已经有序了，因此第三轮做的事几乎为0.
3.C++实现
1 #ifndef SHELLSORT_H 2 #define SHELLSORT_H 3 #include <vector> 4 #include <iostream> 5 using std::vector; 6 using std::cout; 7 using std::endl; 8 9 template <typename T>10 class ShellSort11 {12 private:13 unsigned len;14 vector<T> list;15 public:16 /*17 * Construction function18 */19 ShellSort(vector<T> _list, unsigned _len)20 {21 for (unsigned i = 0; i < _len; ++i) list.push_back(_list[i]);22 this->len = _len;23 }24 /*25 * Shellsort function26 */27 void shellSort()28 {29 int insertNum;30 unsigned gap = len/2; // initial increment31 while(gap) // while gap>=132 {33 for (unsigned i = gap; i < len; ++i) // Insertsort within subsequence34 {35 insertNum = list[i];//Target number to be inserted into the subsequence36 unsigned j = i;37 while (j >= gap && insertNum < list[j-gap])//Find position38 {39 list[j] = list[j - gap];40 j -= gap;41 }42 list[j] = insertNum;43 }//end for44 gap /= 2;45 }//end while(gap)46 }// end shellSort47 48 /*49 * Display the sorted result50 */51 void out()52 {53 for (unsigned i = 0; i < len; ++i)54 {55 cout << list[i] << " ";56 if ((i + 1) % 18 == 0) cout << endl;57 }58 cout << endl;59 }60 };61 #endif62 63 //shellSortTest64 #include "ShellSort.h"65 #include <vector>66 using namespace std;67 68 const unsigned numEle = 8;69 int data[numEle] = {1,5,7,3,8,2,6,4};70 71 72 int main()73 {74 vector<int> testData;75 for (unsigned i = 0; i < numEle; ++i) testData.push_back(data[i]);76 77 ShellSort<int> test(testData, numEle);78 test.shellSort();79 test.out();80 return 0;81 }
4.参考文献
左飞：C++数据结构原理与经典问题求解
希尔排序的C++实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。