复制代码
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/** * * 插入排序 * 直接查找排序 * 折半插入排序 * 希尔排序 * * ①算法思想 * * ②算法设计 * */ #include <stdio.h> #include <iostream> #include <cstdio> #include <malloc.h> #include <cstdlib> #define MaxSize 20 #define INF 999999 //1、直接插入排序(链表的形式之前习题中已写过) //排成增序 void InsertSort(int arr[],int n){ int i,j; for(i = 2;i <= n ;i ++){ //0的位置不存放元素,0的位置是“哨兵”,要进入有序区的元素直接被覆盖就行,因为哨兵存储了被覆盖的元素。 if(arr[i] < arr[i - 1]){ arr[0] = arr[i]; for (j = i - 1;arr[0] < arr[j]; --j) { arr[j + 1] = arr[j]; } arr[j + 1] = arr[0]; } } } //2、折半查找排序 //排成增序 void InsertSortByBinary(int arr[],int n){ int i,j,low,high,mid; for (i = 2; i <= n; ++i) { arr[0] = arr[i]; low = 1; high = i - 1;//有序区是1到 i - 1 while(low <= high){//注意插入和查找的区别,就算mid==key,也不能停下来 mid = (low + high) / 2; if(arr[mid] > arr[0]) high = mid - 1; else low = mid + 1;//arr[mid]==arr[0]的情况时,让low=mid+1,而不是high=mid-1,保证了稳定性 } for (j = i - 1; j >= low; j--) {//把low换成high + 1 是一样的 arr[j + 1] = arr[j]; } arr[low] = arr[0];//把low换成high + 1 是一样的 } } //3、希尔排序 //排成增序 void ShellSort(int arr[],int n){ int dk,i,j;//dk为每次的增量,一般一开始取长度的一半 for (dk = n / 2; dk >= 1 ; dk /= 2) { //直接插入排序 //直接插入排序里,默认第一个元素是有序的(arr[0]不算是第一个元素,还是放哨兵),从第二个元素开始排序, //这里是一样的,这里的第一个元素是这个增量序列的第一个,第二个元素是这个增量序列的第二个 for (i = dk + 1;i <= n; ++i) {//++i说明一次性对此前增量状态下的所有的子表里的元素进行直接插入 if(arr[i] < arr[i-dk]){//i - dk 是有序区的最后一个 arr[0] = arr[i]; for (j = i - dk;j > 0 && arr[0] < arr[j] ; j -= dk) { arr[j + dk] = arr[j]; } arr[j + dk] = arr[0]; } } } }
最后
以上就是羞涩钢笔最近收集整理的关于插入排序(直接插入、折半插入、希尔)的全部内容,更多相关插入排序(直接插入、折半插入、希尔)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复