C语言排序法

Word count: 3.8k   |   Reading time≈ 17 min

排序法

这篇博客介绍了多个基本的排序法

也是我常用的 最能理解的排序法

排序的基本概念

**排序:**是按照关键字的非递减或非递增顺序对一组记录重新进行排序的操作

**排序的稳定性:**假设K1=Kj，且在排序前的序列中Ri领先于Rj(即i<j)。若Ri仍领先于Rj。则这个排序法是稳定的。

内部排序和外部排序

内部排序：待排序的记录都在计算机的内存中

外部排序：待排序的数据量很大，将外部数据分块放入内存中，进行排序。

内部排序方法的分类

  • 插入类：插入排序，折半插入排序，希尔排序
  • 交换类：冒泡排序，快速排序
  • 选择类：简单选择排序，树形选择排序，堆排序
  • 归并类：2-路并排序
  • 分配类：唯一一个不需要进行关键字比较的排序方法。

几个排序法的作用总览

这是一个完整的C语言程序 经测是能够运行的

实现 

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>


#define MAXSIZE 200000

typedef struct {
	int r[MAXSIZE+1];
	int length;
} SqList;

//顺序表的初始化
int init(SqList &S);
//插入排序
void InsertSort(SqList &S);
//折半插入排序
void BInsertSort(SqList &S);
//希尔排序 希尔排序要分为两部分进行
void ShellInsert(SqList &S, int dk);
void ShellSort(SqList &S);
//上述的排序都是插入排序
//还有一个大类的排序就是接下来要设计到的 交换排序
//交换排序中的老大哥 冒泡排序
void BubbleSort(SqList &S);
//快速排序 我写的快速排序或许会与书上的不同
void FastSort(SqList &S,int left,int right);
//选择排序 选择排序才是我经常使用的排序法
void SelectSort(SqList &S);


void Print(SqList &S);


void Order();

int main() {
	SqList S;
	int order;
	Order();
	scanf("%d",&order);
	while(order!=10) {
		switch (order) {
			case 1:
				init(S);
				break;
			case 2:
				Print(S);
				break;
			case 3:
				InsertSort(S);
				break;
			case 4:
				BInsertSort(S);
				break;
			case 5:
				ShellSort(S);
				break;
			case 6:
				BubbleSort(S);
				break;
			case 7:
				FastSort(S,1,S.length);
				break;
			case 8:
				SelectSort(S);
				break;
			default:
				printf("请输入正确的序号!!!\n");
				break;
		}
		printf("请输入你要执行的程序的序号:");
		scanf("%d",&order);
	}
}


int init(SqList &S) {
	srand(time(NULL));
	printf("请输入你要创建的顺序表的长度:");
	scanf("%d",&S.length);
	int i,j;
	//初始化顺序表是从1开始的，这样就可以使r[0]作为哨兵
	for(i=1; i<=S.length; i++) {
		S.r[i] = rand()%1000 + 1;
	}
}
void InsertSort(SqList &S) {
	//对于插入排序是在排序好的顺序表中插入元素
	int i;
	int j;
	//这里的i=2是因为，对于第一个数据，是已经排好序的了的，只有一个数据的顺序串是一定是有序的
	for(i=2; i<=S.length; i++) {
		//如果要执行的那个数据小于他之前的数据，就需要对前边进行查找，找到合适的位置，把数据插入
		if(S.r[i]<S.r[i-1]) {
			//使用哨兵 来存储要实行的数据
			S.r[0] = S.r[i];
			S.r[i] = S.r[i-1];
			//进行移动 如果找到 或 到了哨兵节点 就跳出
			for(j=i-2; S.r[0] < S.r[j]; j--) {
				S.r[j+1]=S.r[j];
			}
			S.r[j+1] = S.r[0];
		}
	}
}

void Print(SqList &S) {
	int i;
	for(i=1; i<=S.length; i++) {
		printf("%d ",S.r[i]);
	}
	printf("\n");
}

void BInsertSort(SqList &S) {
	int i;
	int low;
	int high;
	int  mid;
	int j;
	for(i=2; i<=S.length; i++) {
		S.r[0] = S.r[i];
		//设计两个区间
		//在执行的目标元素之前都是排序好的
		low = 1;
		high = i-1;
		//请注意这里是 <= 不是<
		while(low <= high) {
			mid = (low+high)/2;
			//如果个mid比较大小 目标元素太大了 就提高low 反正降低high
			if(S.r[0]<S.r[mid]) {
				high = mid-1;
			} else {
				low = mid+1;
			}
		}
		//如果找到了合适的位置 就要用一般方法进行插入

		for(j=i-1; j>=high+1; j--) {
			S.r[j+1] = S.r[j];
		}
		S.r[high+1] = S.r[0];
	}
}

void Order() {
	printf("请输入你要执行的程序的序号:\n");
	printf("1.初始化一个链表\n");
	printf("2.展示链表\n");
	printf("3.插入排序给链表排序\n");
	printf("4.折半排序给链表排序\n");
	printf("5.希尔排序给链表排序\n");
	printf("6.冒泡排序给链表进行排序\n");
	printf("7.快速排序给链表进行排序\n");
	printf("8.简单排序给链表进行排序\n");
	printf("10.退出程序\n");
}
void ShellSort(SqList &S) {
	int k;
	int dt[1000];
	int i;
	printf("请输入要做几次划分:");
	scanf("%d",&k);
	//对我们的划分进行初始化 最后一个一定要为1 是非递减的输入的
	for(i=0; i<k; i++) {
		printf("请输入第%d个划分大小",i+1);
		scanf("%d",&dt[i]);
	}
	for(i=0; i<k; i++) {
		ShellInsert(S,dt[i]);
	}
}
void ShellInsert(SqList &S,int dk) {
	//对整个数组机型查分排序
	int i,j;
	for(i=dk+1; i<=S.length; i++) {
		//如果未知序列第一个元素比已经排好序的序列对应的元素小 就调换他们的位置
		if(S.r[i]<S.r[i-dk]) {
			S.r[0] = S.r[i];

			//因为可能一个划分里有多个元素 因此需要进行循环
			for(j=i-dk; j>0 && S.r[0]<S.r[j]; j-=dk) {
				S.r[j+dk] = S.r[j];
			}
			//条出循环就说明找到了位置
			S.r[j+dk] = S.r[0];
		}
	}
}


void BubbleSort(SqList &S) {
	//冒泡排序就是通过多次的相邻两个元素的比较 交换 实现将最大或最小的元素放到两边
	//不同的是 这个冒泡排序标记一个flag 如果在排序中没有出现交换 那么就证明排序已经玩成了 就不需要在继续执行了
	int i;
	int flag=1;
	int m = S.length-1;
	while((m>0)&&(flag==1)) {
		//在进行循环之前将flag表为0 检测后续是否有数据变化
		flag = 0;
		for(i=1; i<m; i++) {
			//我们执行的是从小到大排序
			if(S.r[i+1]<S.r[i]) {
				//交换两者位置 并且将flag立为0
				S.r[0] = S.r[i+1];
				S.r[i+1] = S.r[i];
				S.r[i] = S.r[0];
				flag = 1;
			}
			//最大值已经确定 不用再比较
			--m;
		}
	}
}
void FastSort(SqList &S,int left,int right) {
    int i,j,t,temp;
	if(left>right){
		return ;
	}
	temp = S.r[left];
	i = left;
	j = right;
	while(i!=j){
		while(S.r[j]>=temp && i<j){
			j--;
		}
		while(S.r[i]<=temp && i<j){
			i++;
		}
		if(i<j){
			t = S.r[i];
			S.r[i]=S.r[j];
			S.r[j] = t;
		}
	}
	S.r[left] = S.r[i];
	S.r[i] = temp;
	FastSort(S,left,i-1);
	FastSort(S,i+1,right);
	return ;
}
void SelectSort(SqList &S){
	//每次挑出一个最小值 放到指定的位置 再进行循环 纸质结束
	int i;
	int j;
	int min;
	int temp;
	for(i=1;i<=S.length;i++){
		min = i;
		for(j=i;j<=S.length;j++){
			if(S.r[j]<S.r[min]){
				//找到最小的数
				min = j;
			}
		}
		if(min != i){
			temp = S.r[i];
			S.r[i] = S.r[min];
			S.r[min] = temp;
		}
	}
}

插入排序

基本思想：每一趟将一个待排序的记录，将其关键字的大小插入到已经拍好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。

直接插入排序

直接插入排序：是最简单的插入排序，每一次进行排序都是将数据插入到已经排好序的有序表中，从而得到一个新的、记录数量增1的有序表。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void InsertSort(SqList &S) {
	//对于插入排序是在排序好的顺序表中插入元素
	int i;
	int j;
	//这里的i=2是因为，对于第一个数据，是已经排好序的了的，只有一个数据的顺序串是一定是有序的
	for(i=2; i<=S.length; i++) {
		//如果要执行的那个数据小于他之前的数据，就需要对前边进行查找，找到合适的位置，把数据插入
		if(S.r[i]<S.r[i-1]) {
			//使用哨兵 来存储要实行的数据
			S.r[0] = S.r[i];
			S.r[i] = S.r[i-1];
			//进行移动 如果找到 或 到了哨兵节点 就跳出
			for(j=i-2; S.r[0] < S.r[j]; j--) {
				S.r[j+1]=S.r[j];
			}
			S.r[j+1] = S.r[0];
		}
	}
}

算法特点:

  1. 稳定排序
  2. 算法简便、且容易实现
  3. 适合于链式存储和顺序存储结构
  4. 更适合于初始记录基本有序的情况，n较大时，算法时间复杂度较高，不宜采用
  5. 时间复杂度为O(n^2)
  6. 空间复杂度为O(1)

折半插入排序

折半插入排序能够节省插入排序的寻找过程，但是不能改变移动过程

算法实现：

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
void BInsertSort(SqList &S) {
	int i;
	int low;
	int high;
	int  mid;
	int j;
	for(i=2; i<=S.length; i++) {
		S.r[0] = S.r[i];
		//设计两个区间
		//在执行的目标元素之前都是排序好的
		low = 1;
		high = i-1;
		//请注意这里是 <= 不是<
		while(low <= high) {
			mid = (low+high)/2;
			//如果个mid比较大小 目标元素太大了 就提高low 反正降低high
			if(S.r[0]<S.r[mid]) {
				high = mid-1;
			} else {
				low = mid+1;
			}
		}
		//如果找到了合适的位置 就要用一般方法进行插入

		for(j=i-1; j>=high+1; j--) {
			S.r[j+1] = S.r[j];
		}
		S.r[high+1] = S.r[0];
	}
}

算法特点：

  1. 稳定排序
  2. 只能用顺序结构，不能用于链式结构
  3. 适合初始记录无序，n较大时的情况
  4. 时间复杂度为O(n^2)
  5. 空间复杂度为O(1)

希尔排序

希尔排序：又称“缩小增量排序”，需要移动的数据量较少。

希尔排序实际上是采用分组插入的方法，将整个待排序的记录分割成几组，对每组进行直接插入排序。在增加每组的数据量，重新分组。

希尔排序的分组，不是简单地“逐段分割”，而是将相隔某个“增量”的记录分成一组

注意：最后一次分组一定要是“1”

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
void ShellSort(SqList &S) {
	int k;
	int dt[1000];
	int i;
	printf("请输入要做几次划分:");
	scanf("%d",&k);
	//对我们的划分进行初始化 最后一个一定要为1 是非递减的输入的
	for(i=0; i<k; i++) {
		printf("请输入第%d个划分大小",i+1);
		scanf("%d",&dt[i]);
	}
	for(i=0; i<k; i++) {
		ShellInsert(S,dt[i]);
	}
}
void ShellInsert(SqList &S,int dk) {
	//对整个数组机型查分排序
	int i,j;
	for(i=dk+1; i<=S.length; i++) {
		//如果未知序列第一个元素比已经排好序的序列对应的元素小 就调换他们的位置
		if(S.r[i]<S.r[i-dk]) {
			S.r[0] = S.r[i];

			//因为可能一个划分里有多个元素 因此需要进行循环
			for(j=i-dk; j>0 && S.r[0]<S.r[j]; j-=dk) {
				S.r[j+dk] = S.r[j];
			}
			//条出循环就说明找到了位置
			S.r[j+dk] = S.r[0];
		}
	}
}

算法特点：

  1. 空间复杂度为O(1)
  2. 时间复杂度为P241 无法直接判断
  3. 算法不稳定
  4. 只能用顺序结构，不能用链式结构
  5. 最后一个增量只能是1
  6. 适合初始数据无序，n较大的情况

交换排序

交换排序的基本思想：两两比较带排序记录的关键字，一旦发现两个数据不和要求，就进行交换

交换排序有：冒泡排序和快速排序

冒泡排序

冒泡排序：是一种最简单的交换法，是相邻的数据进行交换。使最大，最小的数据跑到顺序表两端。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void BubbleSort(SqList &S) {
	//冒泡排序就是通过多次的相邻两个元素的比较 交换 实现将最大或最小的元素放到两边
	//不同的是 这个冒泡排序标记一个flag 如果在排序中没有出现交换 那么就证明排序已经玩成了 就不需要在继续执行了
	int i;
	int flag=1;
	int m = S.length-1;
	while((m>0)&&(flag==1)) {
		//在进行循环之前将flag表为0 检测后续是否有数据变化
		flag = 0;
		for(i=1; i<m; i++) {
			//我们执行的是从小到大排序
			if(S.r[i+1]<S.r[i]) {
				//交换两者位置 并且将flag立为0
				S.r[0] = S.r[i+1];
				S.r[i+1] = S.r[i];
				S.r[i] = S.r[0];
				flag = 1;
			}
			//最大值已经确定 不用再比较
			--m;
		}
	}
}

算法特点：

  1. 稳定排序
  2. 可用于顺序存储，也可用于链式存储
  3. 移动此处较多，n较大时，此算法不是采用
  4. 时间复杂度为O(n^2)
  5. 空间复杂度为O(1)

快速排序

快速排序：解决了冒泡排序的只能相邻数据进行比较的缺点，能够实现非相邻的数据进行比较。

代码实现：

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
void FastSort(SqList &S,int left,int right) {
    int i,j,t,temp;
	if(left>right){
		return ;
	}
	temp = S.r[left];
	i = left;
	j = right;
	while(i!=j){
		while(S.r[j]>=temp && i<j){
			j--;
		}
		while(S.r[i]<=temp && i<j){
			i++;
		}
		if(i<j){
			t = S.r[i];
			S.r[i]=S.r[j];
			S.r[j] = t;
		}
	}
	S.r[left] = S.r[i];
	S.r[i] = temp;
	FastSort(S,left,i-1);
	FastSort(S,i+1,right);
	return ;
}

算法特点：

  1. 算法是一个递归算法
  2. 时间复杂度为O(nlog2n)
  3. 空间复杂度为o(n)
  4. 排序方法是不稳定的
  5. 适用于顺序结构，不适合链式存储
  6. 适合于初始记录无序，n较大时的情况

选择排序

简单选择排序

简单选择排序：也称作直接选择排序

简单选择排序是我经常使用的 两个for循环就能实现

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void SelectSort(SqList &S){
	//每次挑出一个最小值 放到指定的位置 再进行循环 纸质结束
	int i;
	int j;
	int min;
	int temp;
	for(i=1;i<=S.length;i++){
		min = i;
		for(j=i;j<=S.length;j++){
			if(S.r[j]<S.r[min]){
				//找到最小的数
				min = j;
			}
		}
		if(min != i){
			temp = S.r[i];
			S.r[i] = S.r[min];
			S.r[min] = temp;
		}
	}
}

算法特点：

  1. 时间复杂度O(n^2)
  2. 空间复杂度O(1)
  3. 既可用于顺序存储结构，也可用于链式存储结构
  4. 移动记录次数较少，每次机理占用的空间不多时可用，此时比直接插入排序快
Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2015-2023 dwx
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信