首页 > 代码库 > 数据结构 - 希尔排序(Shell's Sort) 具体解释 及 代码(C++)
数据结构 - 希尔排序(Shell's Sort) 具体解释 及 代码(C++)
数据结构 - 希尔排序(Shell‘s Sort) 具体解释 及 代码(C++)
本文地址: http://blog.csdn.net/caroline_wendy/article/details/24363981
希尔排序(Shell‘s Sort), 又称"缩小增量排序"(Diminishing Increment Sort), 是插入排序的一种.
主要思想是: 先将整个记录, 通过间隔分成若干个子序列, 分别进行插入排序, 待整个序列基本有序时, 再进行一次插入排序.
由于插入排序时, 有可能反复移动数据, 希尔排序, 是一次移动较多的距离(间隔),降低反复移动, 所以减少了时间复杂度.
时间复杂度约为: O(n^(3/2)).
代码例如以下:
/* * InsertionSort.cpp * * Created on: 2014.4.23 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <iostream> #include <deque> using namespace std; void print(const std::deque<int>& L) { for (auto i : L) { std::cout << i << " "; } std::cout << std::endl; } void ShellInsert (std::deque<int>& L, int dk) { for(std::size_t i=dk; i<L.size(); ++i) { if(L[i] < L[i-dk]) { int temp = L[i]; int j; for(j=i-dk; j>=0&&(temp<L[j]); j-=dk) L[j+dk] = L[j]; L[j+dk] = temp; } } std::cout << "dlta " << dk << " : "; print(L); } void ShellSort(std::deque<int>& L, std::deque<int> dlta) { for(std::size_t k=0; k<dlta.size(); ++k) ShellInsert(L, dlta[k]); } int main(void) { std::deque<int> L = {49, 38, 65, 97, 76, 13, 27, 49, 55, 04}; std::deque<int> dlta = {5, 3, 1}; ShellSort(L, dlta); print(L); }
输出:
dlta 5 : 13 27 49 55 4 49 38 65 97 76 dlta 3 : 13 4 49 38 27 49 55 65 97 76 dlta 1 : 4 13 27 38 49 49 55 65 76 97 4 13 27 38 49 49 55 65 76 97
数据结构 - 希尔排序(Shell's Sort) 具体解释 及 代码(C++)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。