排序原理：
希 尔（ Shell） 排序 算法 先 将要 排序 的 一组 数 按 某个 增量 d 分成 若干 组， 每组 中 记录 的 下标 相差 d 对 每组 中 全部 元素 进行 排序， 然后 用 一个 较小 的 增量 对 它 进行 再次 分组， 并对 每个 新 组 重新 进行 排序。 当 增量 减到 1 时， 整个 要 排序 的 数 被 分成 一组， 排序 完成。 因此 希 尔 排序 实质上 是一 种 分组 插入 方法。
当 数组 初始 状态 基本 有 序时， 直接 插入排序 所需 的 比较 和 移动 次数 均 较少。 当 n 值 较小 时， n 和 n2 的 差别 也 较小， 即 直接 插入 排序 的 最好 时间 复杂度 O( n) 和 最坏 时间 复杂度 0( n2) 差别 不大。 在 希 尔 排序 开始时， 增量 较大， 分组 较多， 每组 的 记录 数目 少， 故 各组 内 直接 插入 较快， 后来 增量 d 逐渐 缩小， 分组 数 逐渐 减少， 而 各组 的 记录 数目 逐渐 增多。 但 由于 已经 按 d- 1 作为 距离 排 过 序， 数组 较 接近 于 有序 状态， 所以 新的 一 趟 排序 过程 也 较快。
另外， 由于 分组 的 存在， 相等 的 元素 可能 会 分在 不 同组， 导致 它们 的 次序 可能发生 变化， 因此 希 尔 排序 是 不稳 定的。
草稿笔记
代码实现
代码实现需要十分注意的一点，是判断的时候需要 j >= 0; 而不是 j >0; 否则对第0个元素就没有排序了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87#include <stdio.h> #include <stdlib.h> #define SUCCESS 0 #define PARAM_ERR -1 int ShellSort(int * array, int size){ if(NULL == array){ printf("%s para error", __func__); return PARAM_ERR; } int i = 0, j =0; /*插入排序使用*/ int m = 0, n = 0; /*按dist分组使用*/ int insert = 0; int dist = 0; /*希尔步距*/ #ifdef DEBUG int k = 0; /*debug 输出*/ #endif for(dist = size/2; dist > 0; dist--){ /*步距逐步减小*/ #ifdef DEBUG printf("n ======== distance = %d =============n", dist); #endif for(m =0; m < dist; m++) { //当前dist下，分别插入排序 dist -1 组 /*对每组进行插入排序*/ for(i = m; i < size ; i = i + dist) { insert = array[i]; /*有序区, 没有找到合适的位置，向后移动*/ for(j = i - dist; j >= 0; j = j - dist){ if(array[j] >= insert){ array[j + dist] = array[j]; } else { break; } } /*插入到合适的位置*/ array[j + dist] = insert; } #ifdef DEBUG printf("n ------ another group -----------n"); printf("["); for(k =m; k < size; k = k + dist){ printf(" %d ", array[k]); } printf("]n"); printf("n"); #endif } } return SUCCESS; } int main(int argc, char ** argv){ int array[10] = {7,3,5,8,0,9,1,2,4,6}; int i = 0; printf("Before sort: n"); for(i = 0; i < 10; i++){ printf(" %d ", array[i]); } printf("n"); ShellSort(array, 10); printf("after sort: n"); for(i = 0; i < 10; i++){ printf(" %d ", array[i]); } printf("n"); return 0; }
编译
gcc ShellSort.c -DDEBUG
调试输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75Before sort: 7 3 5 8 0 9 1 2 4 6 ======== distance = 5 ============= ------ another group ----------- [ 7 9 ] ------ another group ----------- [ 1 3 ] ------ another group ----------- [ 2 5 ] ------ another group ----------- [ 4 8 ] ------ another group ----------- [ 0 6 ] ======== distance = 4 ============= ------ another group ----------- [ 0 7 8 ] ------ another group ----------- [ 1 6 9 ] ------ another group ----------- [ 2 3 ] ------ another group ----------- [ 4 5 ] ======== distance = 3 ============= ------ another group ----------- [ 0 3 4 9 ] ------ another group ----------- [ 1 5 7 ] ------ another group ----------- [ 2 6 8 ] ======== distance = 2 ============= ------ another group ----------- [ 0 2 4 5 8 ] ------ another group ----------- [ 1 3 6 7 9 ] ======== distance = 1 ============= ------ another group ----------- [ 0 1 2 3 4 5 6 7 8 9 ] after sort: 0 1 2 3 4 5 6 7 8 9
最后
以上就是清新毛衣最近收集整理的关于希尔插入排序法 -- C语言的全部内容，更多相关希尔插入排序法内容请搜索靠谱客的其他文章。
发表评论 取消回复