C++|希尔排序——C++实现

希尔排序C++实现 C++|希尔排序——C++实现
文章图片

很有意思,有点像归并排序,但是分组的策略不同。希尔排序的分组策略是a[i+k*gap]一组,k=0,1,2…。
【C++|希尔排序——C++实现】template_head.h

#include #include "../head_file/template_head.h" #include using namespace std; void shell_sort() { cout << "Shell Sort!!!" << endl; vector sort_list = { 8,9,1,7,2,3,5,4,6,0 }; shellSort(sort_list.begin(), sort_list.end()); for (auto x : sort_list) { cout << x << " "; } cout << endl; }template void shellSort(const Iterator& begin, const Iterator& end) { shellSort(begin, end, less_{}); }template void shellSort(const Iterator& begin, const Iterator& end, Comparator lessThan) { if (begin == end) return; auto size = end - begin; for (auto gap = size / 2 ; gap > 0; gap /= 2) { for (Iterator i = begin + gap; i != end; i++) { auto tmp = std::move(*(i)); Iterator j; for (j = i; j >= begin+gap && lessThan(tmp, *(j - gap)); j -= gap) { *j = std::move(*(j - gap)); // 向后移动一个gap } *j = std::move(tmp); } }}

    推荐阅读