C语言各种排序
算法复杂度以及稳定性分析
| 算法名称 | 平均时间 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n2) | O(1) | 是 |
| 选择排序 | O(n2) | O(1) | 否 |
| 插入排序 | O(n2) | O(1) | 是 |
| 自底向上归并排序 | O(nlog2n) | O(n) | 是 |
| 自顶向下归并排序 | O(nlog2n) | O(n) | 是 |
| 快速排序 | O(nlog2n) | O(n) | 否 |
| 堆排序 | O(nlog2n) | O(1) | 否 |
| 基数排序 | O(dn) | O(rn) | 是 |
| 希尔排序 | O(1) | 否 |
一、冒泡排序
冒泡排序算法的运作如下：（从后往前）1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void bubble_sort() { int a[] = {1, 34, 23, 55, 22, 11}; int i,j,k; for(i=0;i<5;i++) { for(j=0;j<5-i;j++) if(a[j]>a[j+1]) { k=a[j]; a[j]=a[j+1]; a[j+1]=k; printf("%dn", a[j]); // a[j] ^= a[j+1] ^= a[j]; } }
二、插入排序
直接插入排序的算法思路：
（1） 设置监视哨r[0]，将待插入纪录的值赋值给r[0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；
（4） 将r[0]插入r[j+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
27void insert_sort() { int i, j, m, tmp; int a[10] = {1, 34, 23, 55, 22, 11, 45, 67, 35, 26}; #if 1 for(i=0;i<10;i++) { m=a[i]; for(j=i-1;j >= 0;j--) { if(a[j] < m) break; else a[j+1] = a[j]; } a[j+1] = m; } #else for(i = 1; i < 10; i++) { m = 5; if(i != m){ j = i; tmp = a[i]; while(j > m){ a[j] = a[j-1]; j--; } a[j] = tmp; } }
三、快速排序
一趟快速排序的算法是：
1）设置两个变量i、j，
排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给
key，即
key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于
key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于
key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于
key,4中A[i]不大于
key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
复制代码
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
31quick_sort(int L[],int first,int end) { int pos; if(end>first) { pos=quick(first,end,L); quick_sort(L,first,pos-1); quick_sort(L,pos+1,end); } } quick(int first,int end,int L[]) { int left=first, right=end,key; key=L[first]; while(left<right) { while((left<right)&&(L[right]>=key)) { right--; printf("left:%d right:n",left); } if(left<right) { L[left++]=L[right]; // printf("left2:%d right: n",left); } while((left<right)&&(L[left]<=key)) left++; if(left<right) L[right--]=L[left]; } L[left]=key; // printf("left3:%d right: n",left); return left; }
四、选择排序
n个记录的文件的
直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出
关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void select_sort() { int t,k,i,j, d; int a[10] = {1, 34, 23, 55, 22, 11, 45, 67, 35, 26}; // printf("Please input some number that you want to sort:"); for(i=0;i<9;i++) { d=i; for(j=i+1;j<10;j++) { if(a[j] < a[d]) d = j; if(d != i) { t=a[d]; a[d]=a[i]; a[i]=t; } } }
五、希尔排序
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量=1(<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void shell_sort(int *x, int n) { int h, j, k, t; for (h=n/2; h>0; h=h/2) /*控制增量*/ { for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/ { t = *(x+j); for (k=j-h; (k>=0 && t<*(x+k)); k-=h) *(x+k+h) = *(x+k); *(x+k+h) = t; } } }
六、归并排序
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
复制代码
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复制代码void Merge(int* array, int *p_array, int bindex, int mindex, int eindex) { int mlen = eindex - bindex; //合并后的序列长度 int i = 0; //记录合并后序列插入数据的偏移 int j = bindex; //记录子序列1插入数据的偏移 int k = mindex; //记录子序列2掺入数据的偏移 while (j < mindex && k < eindex) { if (array[j] <= array[k]) { p_array[i++] = array[j]; j++; } else { p_array[i++] = array[k]; k++; } } if (j == mindex) //说明序列1已经插入完毕 while (k < eindex) p_array[i++] = array[k++]; else p_array[i++] = array[j++]; for (i = 0; i < mlen; i++) //将合并后序列重新放入array array[bindex + i] = p_array[i]; }void MergeSort(int r[],int r1[],int s,int t) { if(s==t); else { int m=(s+t)/2; MergeSort(r,r1,s,m); MergeSort(r,r1,m+1,t); Merge(r,r1,s,m+1,t+1); } }
/* int a[10] = {1, 34, 23, 55, 22, 11, 45, 67, 35, 26};
int *p = (int *)malloc(sizeof(int )*10);
MergeSort(a, p, 0, 9);
*/复制代码七、堆排序
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。复制代码//array是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度 本函数功能是：根据数组array构建大根堆 void heap_mer(int array[],int i,int nlen) { int nchild, ntmp; for(; 2*i+1 < nlen; i = nchild) { nchild = 2*i+1; if(nchild < nlen-1 && array[nchild+1] > array[nchild]) ++nchild; if(array[i] < array[nchild]) { ntmp = array[i]; array[i] = array[nchild]; array[nchild] = ntmp; } else break; } } void HeapSort(int array[],int length) { int tmp, i; //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素 //length/2-1是最后一个非叶节点，此处"/"为整除 for(i=length/2-1;i>=0;i--) heap_mer(array,i,length); //从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素 for(i=length-1;i>0;i--) { //把第一个元素和当前的最后一个元素交换， //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的 //Swap(&array[0],&array[i]); tmp=array[i]; array[i]=array[0]; array[0]=tmp; //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值 heap_mer(array,0,i); } }
最后
以上就是贪玩裙子最近收集整理的关于C语言排序算法实现的全部内容，更多相关C语言排序算法实现内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复