avatar

目录
七大排序的C语言实现

Talk is cheap, show me your code!

不要介意夹了一点C++

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
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

inline void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}

void bubbleSort(int ary[], int len) {
for(int i = 0; i < len; i++)
for(int j = 0; j < len-i; j++)
if(ary[j] > ary[j+1])
swap(ary[j], ary[j+1]);
return;
}

void selectSort(int ary[], int len) {
for(int i = 0; i < len; i++) {
int minIndex = i;
for(int j = i; j < len; j++)
if(ary[j] < ary[minIndex])
minIndex = j;
swap(ary[i], ary[minIndex]);
}
return;
}

inline void _insertSort(int ary[], int len, int gap, int startIndex) {
for(int i = startIndex + 1; i < len; i += gap)
for(int j = i-gap; j >= startIndex && ary[j] > ary[j+gap]; j -= gap)
swap(ary[j], ary[j+gap]);
return;
}

void insertSort(int ary[], int len) {
_insertSort(ary, len, 1, 0); // 起始位置为0,间隔为1的插入排序
}

void quickSort(int ary[], int len) {
if(len < 2)
// 当列表长度为1时,有序,不做任何操作
return;
if(len == 2) {
// 当列表长度为2时,比较两个元素的大小,然后调整并返回
if(ary[0] > ary[1])
swap(ary[0], ary[1]);
return;
}
int left = 0;
int right = len - 1;
while(left < right) {
// 基准值为首个元素
while(ary[right] >= ary[0] && left < right)
// 右哨兵左移,直到小于基准值
right--;
while(ary[left] <= ary[0] && left < right)
left++;
// 左哨兵右移,直到大于基准值
swap(ary[left], ary[right]); // 交换两个不符合条件的数
}
swap(ary[0], ary[right]);
// 当左哨兵和右哨兵相遇后,这个地方的数不比基准值大,所以将它与基准值交换
// 这时基准值左边的数都比基准值小,右边的都比基准值大
quickSort(ary, right);
// 对基准值左边的数组进行排序
quickSort(ary+right+1, len-right-1);
// 对基准值右边的数组进行排序
return;
}

inline void siftDown(int ary[], int len, int startIndex) {
int i = startIndex;
for(int j = i*2+1; j < len; j = j*2+1) {
// i为当前节点index, j为左子节点index
if(j+1 < len && ary[j] < ary[j+1])
// 找出左右子节点中比较大的那个
j++;
if(ary[i] < ary[j])
// 如果子节点大于父节点
swap(ary[i], ary[j]);
// 交换父子节点
else
return;
i = j; //父节点下移
}
return;
}

void heapSort(int ary[], int len) {
for(int i = (len-1) / 2; i >= 0; i--)
//建堆,复杂度O(n/2)
siftDown(ary, len, i);
while(len > 1) {
swap(ary[0], ary[--len]);
// 交换堆顶元素与最后一个元素,并将无序表长度自减
siftDown(ary, len, 0);
}
return;
}

void mergeSort(int ary[], int len) {
if(len < 2)
// 当列表长度为1时,有序,不做任何操作
return;
int mid = len / 2;
// 将数组从中间切开,分为左数组和右数组
int leftLen = mid;
int rightLen = len - mid;
mergeSort(ary, leftLen);
// 将左数组排序
mergeSort(ary+mid, rightLen);
// 将右数组排序
int i, j;
int leftAry[leftLen], rightAry[rightLen];
for(i = 0; i < leftLen; i++)
leftAry[i] = ary[i];
for(j = mid; j < len; j++)
rightAry[j-mid] = ary[j];
// 分配另外两块内存,用于存储左数组和右数组的拷贝
i = j = 0;
while(i < leftLen && j < rightLen)
ary[i+j] = (leftAry[i] < rightAry[j])?
leftAry[i++]:
rightAry[j++];
while(i < leftLen)
ary[i+j] = leftAry[i++];
while(j < rightLen)
ary[i+j] = rightAry[j++];
// 合并两个有序数组,最差复杂度为O(n)
return;
}

void shellSort(int ary[], int len) {
int gap = len;
while(gap /= 2)
for(int i = 0; i < gap; i++)
_insertSort(ary, len, gap, i);
return;
}

bool isOrdered(int ary[], int len) {
return (len < 2)? true : ((ary[0] <= ary[1]) && isOrdered(ary+1, len-1));
}

void bogoSort(int ary[], int len) {
// 彩蛋——马骝排序,复杂度O(n!)
srand(time(NULL));
while(!isOrdered(ary, len))
// 打乱数组
for(int i = 0; i < len; i++) {
int a = rand() % len;
int b = rand() % len;
swap(ary[a], ary[b]);
}
return;
}

int main() {
const int N = 1 << 10;
const int MAX_RANGE = 10000;
int ary[N];
srand(time(NULL));
printf("排序前:\n");
for(int i = 0; i < N; i++) {
ary[i] = rand() % MAX_RANGE;
printf("ary[%d]=%d\n", i, ary[i]);
}
printf("------------\n排序后:\n");
quickSort(ary, N);
for(int i = 0; i < N; i++)
printf("ary[%d]=%d\n",i,ary[i]);
printf("%s",isOrdered(ary,N) ? "有序" : "无序");
}
文章作者: LightingX
文章链接: http://lightingx.top/blog/2019/03/28/%E4%B8%83%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%9A%84C%E8%AF%AD%E8%A8%80%E5%AE%9E%E7%8E%B0/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LightingX

评论