首页 > 代码库 > 经典排序算法学习笔记四——希尔排序
经典排序算法学习笔记四——希尔排序
一、希尔排序
| 数据结构 | 数组 |
|---|---|
| 最差时间复杂度 | 根据步长序列的不同而不同。已知最好的：O(n*log ^{2}n) |
| 最优时间复杂度 | O(n) |
| 平均时间复杂度 | 根据步长序列的不同而不同。 |
| 最差空间复杂度 | O(n) |
1、算法思想：
- 先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；
- 然后取d2<d1，重复上述分组和排序操作；
- 直至di=1，即所有记录放进一个组中排序为止。
我是栗子，栗子，栗子
| 假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样： 13 14 94 33 8225 59 94 65 2345 27 73 25 3910 然后我们对每列进行排序： 10 14 73 25 2313 27 94 33 3925 59 94 65 8245 将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序： 10 14 7325 23 1327 94 3339 25 5994 65 8245 排序之后变为： 10 14 1325 23 3327 25 5939 65 7345 94 8294 最后以1步长进行排序（此时就是简单的插入排序了）。 |
2、伪代码：
input: an array a of length n with array elements numbered 0 to n − 1inc ← round(n/2)while inc > 0 do: for i = inc .. n − 1 do: temp ← a[i] j ← i while j ≥ inc and a[j − inc] > temp do: a[j] ← a[j − inc] j ← j − inc a[j] ← temp inc ← round(inc / 2)
3、实现：
1 #include <stdio.h> 2 #include <stdlib.h> 3 void shell_sort(int arr[], int len) { 4 int gap, i, j,n=0; 5 int temp; 6 for (gap = len /2; gap > 0; gap /= 2){ 7 for (i = gap; i < len; i++) {//gap=1时就是直接插入排序了，首先要理解插入排序 8 temp = arr[i]; 9 for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)10 arr[j + gap] = arr[j];11 arr[j + gap] = temp;12 }13 n++;14 printf("\n第%d次sorted:\n",n);15 printf("gap=%d\n",gap);16 for (i = 0; i < len; i++)17 printf("%d ", arr[i]);18 }19 }20 int main() {21 int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };22 int len = (int) sizeof(arr) / sizeof(*arr);23 int i;24 printf("before shell_sort:\n");25 for (i = 0; i < len; i++)26 printf("%d ", arr[i]);27 shell_sort(arr, len);28 printf("\n最后结果:\n");29 for (i = 0; i < len; i++)30 printf("%d ", arr[i]);31 system("pause");32 return 0;33 }
经典排序算法学习笔记四——希尔排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。