C++中怎么实现希尔排序-创新互联
这篇文章给大家介绍C++ 中怎么实现希尔排序,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。
创新互联建站是一家企业级云计算解决方案提供商,超15年IDC数据中心运营经验。主营GPU显卡服务器,站群服务器,成都二枢服务器租用托管,海外高防服务器,机柜大带宽,动态拨号VPS,海外云手机,海外云服务器,海外服务器租用托管等。希尔排序算法
定义:
希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。
算法思想:
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰好被分为一组,算法终止。
时间复杂度:
O(N)
空间复杂度:
O(1)
性能:
希尔排序为不稳定算法(一次插入排序是稳定的,不会改变相同元素的相对顺序,但是在不同的插入排序中,相同的元素可能在各自的插入排序中移动,会打乱其稳定性)
优势:
希尔排序不需要大量的辅助空间,比直接插入排序时间要快,并且代码很好实现。
缺点:
虽然希尔排序相对于直接插入排序要优化很多,但是O(N)的算法依旧效率不是很高,并且希尔排序不稳定。
代码实现:
#include#include #include using namespace std; //希尔排序,从小到大排 void ShellSort(int* arr, int len) { assert(arr); int gap = 3; //先给一个初始组间距,gap为1时即为直接插入排序 for (gap = 3; gap > 0; --gap) //不断缩小组间距,直到gap=1 { for (int i = 0; i < len; ++i) { for (int j = i + gap; j < len; j = j + gap) { if (arr[j-gap] > arr[j]) { int temp = arr[j]; //将arr[j]处的值先保存起来 arr[j] = arr[j-gap]; arr[j-gap] = temp; } } } } }
#include "ShellSort.h" void TestShellSort() { int arr[] = { 100, 2,888, 6, 10, 5, 3, 666, 78, 9, 10000, 45, 67, 33 }; int len = sizeof(arr) / sizeof(arr[0]); cout << "未排序序列:" << ""; for (int i = 0; i < len; ++i) { cout << arr[i] << "->"; } cout << endl; ShellSort(arr, len); cout << "已排序序列:" << ""; for (int j = 0; j < len; ++j) { cout << arr[j] << "->"; } cout << endl; } int main() { TestShellSort(); system("pause"); return 0; }
关于C++ 中怎么实现希尔排序就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页题目:C++中怎么实现希尔排序-创新互联
网页URL:http://scyanting.com/article/gihdp.html