希尔排序又称为 缩小增量排序 ,由D.L.Shell在1959年提出而得名。
该算法先取一个小于数据表中元素个数 n 的整数gap, 并以此作为第一个间隔,将数据分为gap个子序列,所有距离为gap的对象存放在同一个子序列中,于是数据表中的元素就被分成了gap个组,分组确定后,在每一个小组中进行直接插入排序(参考 直接插入排序与二分插入排序的C++实现 ),局部排序完成后,缩小gap, 重复上述步骤,直至取到gap=1时,完成最后一次直接插入排序。
为什么这个算法会起作用: 开始的时候gap较大,子序列中的数据较少,所以最开始的时候算法运行较快,随着算法进行,gap 逐渐变小,子序列中元素的个数也就越来越多,所以排序工作可能会变慢,但是由于前面已经完成了部分排序工作,因而在很大程度上减轻了后来的工作量,于是最终总体的排序速度还是比较快的。
数据表:
第一轮:数据表共有6个元素,初始化gap = 6, 第一轮取取gap = MT(gap/2)=3,注意这里 MT(X)表示取不小于X的最小整数,即向上取整 !
第二轮:gap = MT(gap/2)=2;
第三轮:gap = MT(gap/2) = 1,但是由于第二轮结束后数据表实际上已经有序了,因此第三轮做的事几乎为0.
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 ShellSort 11 { 12 private: 13 unsigned len; 14 vector<T> list; 15 public: 16 /* 17 * Construction function 18 */ 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 function 26 */ 27 void shellSort() 28 { 29 int insertNum; 30 unsigned gap = len/2; // initial increment 31 while(gap) // while gap>=1 32 { 33 for (unsigned i = gap; i < len; ++i) // Insertsort within subsequence 34 { 35 insertNum = list[i];//Target number to be inserted into the subsequence 36 unsigned j = i; 37 while (j >= gap && insertNum < list[j-gap])//Find position 38 { 39 list[j] = list[j - gap]; 40 j -= gap; 41 } 42 list[j] = insertNum; 43 }//end for 44 gap /= 2; 45 }//end while(gap) 46 }// end shellSort 47 48 /* 49 * Display the sorted result 50 */ 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 #endif 62 63 //shellSortTest 64 #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 }
左飞:C++数据结构原理与经典问题求解