首页 > 代码库 > 希尔排序
希尔排序
介绍
先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
过程
先将要排序的一组记录按某个增量d(n/2，n为要排序数的个数)分为若干组子序列，每组中记录的下标相差d。对每组中全部元素进行直接插入排序；
然后再用一个较小的增量(d/2)对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1；
最后使用直接插入排序完成排序。
代码
#include<iostream>using namespace std;void ShellInsertSort(int a[],int n,int dk){ for (int i = dk; i < n; i++){ //若第i个元素大于第i-1个元素，直接插入。小于的话，移动有序表后插入。 if (a[i] < a[i - dk]){ int j = i - dk; int x = a[i];//赋值为哨兵，即存储待排序元素 a[i] = a[i - dk];//首先后移一个元素 //查找在有序表中的插入位置 while (x < a[j]){ a[j + dk] = a[j]; j -= dk;//元素后移 } a[j + dk] = x;//插入到正确位置 } }}void shellSort(int a[], int n){ int dk = n / 2; while (dk >= 1){ ShellInsertSort(a,n,dk); dk = dk / 2; }}int main(){ int a[] = { 3, 1, 5, 7, 2, 4, 11, 32, 5, 6 }; int n = 10; shellSort(a, n); for (int i = 0; i < n; i++){ cout << a[i] << " "; } return 0;}
时间复杂度
分析较难，比O(n*n)好，大概在O(n^1.25)
空间复杂度
O(1)
希尔排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。