排序算法总结(上)
算法
What’s Algorithm ?
提及“算法”，小白面对高大上说词仰慕之心油然而生 @o@
然而，算法并不神秘 = =
顾名思义，计算方法简称算法（什，什，什，什么！这么简单？→_→）
举个栗子：
从小学就接触的乘法：对 n+n+n+…+n 的简写就是一种算法（递推法^A）,
算法注定要有输入与输出：算式中的 n 即为输入，乘积即为输出。
注：
- 算法中的状态变化是不确定的
- 算法必定能在执行有限个步骤之后终止
- 某些算法加入随机输入，称为随机化算法
How to Assess Algorithm ?
对算法的评定分析主要从时间复杂度(所耗时间长短)与空间复杂度(空间开支大小)来考虑。
关于复杂度的计算需要引入如下渐近记号：
大O记号：
O(g(n)) = { f(n) : 存在正常数c和n0 ，使对所有的n >= n0，都有 0 <= f(n) <= cg(n) }
大Ω记号：
Ω(g(n)) = { f(n) : 存在正常数c和n0 ，使对所有的n >= n0，都有 0 <= cg(n) <= f(n) }
大Θ记号：
Θ(g(n)) = { f(n) : 存在正常数c1和c2和n0 ，使对所有的n >= n0，都有 0 <= c1g(n) <= f(n) <= c2g(n) }
数学证明资料：计算机算法分析之渐进记号
具体计算方式将于实例中给出 ～(~▽~)～
DIY Algorithm ！
以下给出排序算法C++代码：
1.冒泡排序（Bubble Sort）^B1
2
3
4
5
6
7
8
9
10
11
12
13template<typename T>
void bubbleSort(T arr[],int n)
{
T temp;
for(int i = 0;i < n - 1;i++)
for(int j = 0;j < n - 1 - i;j++)
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
时间复杂度分析：
考虑最坏情况–将逆序数列变为顺序（此情况下，每一次比较都需要进行交换运算） T_T
再举个栗子：数列 5 4 3 2 1 进行冒泡升序排列
第一次外层循环从第一个数5开始到倒数第二个数2结束，
共进行4次比较交换运算，5移到末尾。
第二次外层循环从第一个数4开始到倒数第三个数2结束。
共进行3次比较交换运算，4移到倒数第二个数。
……
依次推类，总比较次数为 4 + 3 + 2 + 1 = 10 次
证明：
根据数学归纳法,对于n位的数列则有比较次数为(n-1) + (n-2) + ... + 1 = n \* (n - 1) / 2 = (n^2 - n) / 2
如图
若n = 10000，则(n^2 - n) / 2 = (100000000 - 10000) / 2
相对 100000000 来说 10000 微乎其微，故总计算次数约为0.5 \* N^2
用O(N^2)就表示了其数量级（忽略前面系数0.5）
得 冒泡排序的时间复杂度为O(N^2)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//冒泡排序改进版：若遍历中得知数组有序则结束排序
template<typename T>
void bubbleSort(T arr[],int n)
{
bool flag = false;
T temp;
for(int i = 0;i < n - 1;i++)
{
flag = false;
for(int j = 0;j < n - 1 - i;j++)
if(arr[j] > arr[j + 1])
{
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
if(flag == false)
break;
}
}
改进算法后，对于一个有序数组完成一次外层循环后就会结束，共发生 N - 1 次比较，故升级版冒泡排序在最优情况下的时间复杂度为O(N)
2.插入排序(Insert Sort)1
2
3
4
5
6
7
8
9
10
11
12
13template<typename T>
void insertSort(T arr[],int n)
{
T temp;
for(int i = 1;i < n;i++)
if(arr[i] < arr[i - 1])
{
temp = arr[i];
for(int j = i - 1;j >= 0 && arr[j] > temp;j--)
arr[j + 1] = arr[j];
arr[j + 1] = temp;
}
}
资料：插入排序舞蹈
3.*归并排序（Merge Sort）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
33template<typename T>
void mergeSort(T arr[],T temp[],int start,int last)
{
if(start < last)
{
int mid = (start + last) / 2;
mergeSort(arr,temp,start,mid);
mergeSort(arr,temp,mid + 1,last);
arrUnion(arr,temp,start,mid,last);
}
}
template<typename T>
void arrUnion(T arr[],T temp[],int start,int mid,int last)
{
int i,j,k;
i = start;
j = mid + 1;
k = start;
while(i != mid + 1 && j != last + 1)
{
if(arr[i] < arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i != mid + 1)
temp[k++] = arr[i++];
while(j != last + 1)
temp[k++] = arr[j++];
for(i = start;i < last + 1;i++)
arr[i] = temp[i];
}
资料：排序动画演示
Comparison .
下面我们通过这段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
template<typename T>
void printArr(T arr[],int n);
template<typename T>
void quickSort(T arr[],int start,int last);
template<typename T>
void quickSortRand(T arr[],int start,int last);
template<typename T>
void mergeSort(T arr[],T temp[],int start,int last);
template<typename T>
void insertSort(T arr[],int n);
template<typename T>
void bubbleSort(T arr[],int n);
template<typename T>
void bubbleSortPlus(T arr[],int n);
template<typename T>
void choseSort(T arr[],int n);
int main(int argc, char * argv[])
{
clock_t start, end;
int a[N], b[N], c[N], d[N], e[N], f[N], g[N];
srand(time(NULL));
for(int i = 0;i < N;i++)
{
g[i] = f[i] = e[i] = d[i] = c[i] = b[i] = a[i] = rand()%100 + rand()%1000;
//g[i] = f[i] = e[i] = d[i] = c[i] = b[i] = a[i] = N - i;
}
start = clock();
quickSortRand(a,0,N - 1);
end = clock();
printf("随机快速排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
//printArr(a,N);
start = clock();
quickSort(b,0,N - 1);
end = clock();
printf("快速排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
//printArr(b,N);
int* temp = (int*)malloc(sizeof(int) * N);
start = clock();
mergeSort(c,temp,0,N - 1);
end = clock();
printf("归并排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
//printArr(c,N);
free(temp);
start = clock();
insertSort(d,N);
end = clock();
printf("插入排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
//printArr(d,N);
start = clock();
bubbleSort(e,N);
end = clock();
printf("冒泡排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
//printArr(e,N);
start = clock();
bubbleSortPlus(f,N);
end = clock();
printf("升级版冒泡排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
//printArr(f,N);
start = clock();
choseSort(g,N);
end = clock();
printf("选择排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
//printArr(g,N);
return 0;
}
template<typename T>
void quickSort(T arr[],int start,int last)
{
if(start < last)
{
T temp;
int i = start;
int j = last;
while(i != j)
{
while(arr[j] >= arr[start] && j != i)
j--;
while(arr[i] <= arr[start] && i != j)
i++;
if(i != j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
quickSort(arr, start, i - 1);
quickSort(arr, i + 1, last);
}
}
template<typename T>
void quickSortRand(T arr[],int start,int last)
{
if(start < last)
{
T temp;
int i = start;
int j = last;
int pos = rand() % (last - start) + start;
temp = arr[start];
arr[start] = arr[pos];
arr[pos] = temp;
while(i != j)
{
while(arr[j] >= arr[start] && j != i)
j--;
while(arr[i] <= arr[start] && i != j)
i++;
if(i != j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
quickSortRand(arr, start, i - 1);
quickSortRand(arr, i + 1, last);
}
}
template<typename T>
void mergeSort(T arr[],T temp[],int start,int last)
{
if(start < last)
{
int mid = (start + last) / 2;
mergeSort(arr,temp,start,mid);
mergeSort(arr,temp,mid + 1,last);
int i,j,k;
i = start;
j = mid + 1;
k = start;
while(i != mid + 1 && j != last + 1)
{
if(arr[i] < arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i != mid + 1)
temp[k++] = arr[i++];
while(j != last + 1)
temp[k++] = arr[j++];
for(i = start;i < last + 1;i++)
arr[i] = temp[i];
}
}
template<typename T>
void insertSort(T arr[],int n)
{
T temp;
for(int i = 1;i < n;i++)
if(arr[i] < arr[i - 1])
{
temp = arr[i];
for(int j = i - 1;j >= 0 && arr[j] > temp;j--)
arr[j + 1] = arr[j];
arr[j + 1] = temp;
}
}
template<typename T>
void bubbleSort(T arr[],int n)
{
T temp;
for(int i = 0;i < n - 1;i++)
for(int j = 0;j < n - 1 - i;j++)
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
template<typename T>
void bubbleSortPlus(T arr[],int n)
{
bool flag = true;
T temp;
for(int i = 0;i < n - 1 && flag;i++)
{
flag = false;
for(int j = 0;j < n - 1 - i;j++)
if(arr[j] > arr[j + 1])
{
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
template<typename T>
void choseSort(T arr[],int n)
{
T temp;
for(int i = 0;i < n - 1;i++)
for(int j = i + 1;j < n;j++)
if(arr[i] > arr[j])
{
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
template<typename T>
void printArr(T arr[],int n)
{
for(int i = 0;i < n;i++)
printf("%d ", arr[i]);
printf("\n");
}
执行条件：
编译程序VC 6.0
数组成员 5000
执行结果：
随机快速排序用时0.001000sec
快速排序用时0.001000sec
归并排序用时0.002000sec
插入排序用时0.033000sec
冒泡排序用时0.090000sec
升级版冒泡排序用时0.089000sec
选择排序用时0.083000sec
下面我们通过这段JAVA语言代码比较排序速度，直观感受时间复杂度。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//Test.java
package pers.cz.sortcompare;
import java.util.Random;
import pers.cz.sortcompare.Sort;
public class Test {
public static void main(String[] args) {
final int n = 1000;
int[] a = new int[n];
int[] b = new int[n];
int[] c = new int[n];
int[] d = new int[n];
int[] e = new int[n];
int[] f = new int[n];
int[] g = new int[n];
long start, end;
Random rand = new Random();
for (int i = 0; i < a.length; i++) {
g[i] = f[i] = e[i] = d[i] = c[i] = b[i] = a[i] = rand.nextInt();
}
start = System.currentTimeMillis();
Sort.QuickSort(a, 0, n - 1);
end = System.currentTimeMillis();
System.out.print("QuickSort cost time(sec):");
System.out.println(end - start);
//PrintArrData(a);
start = System.currentTimeMillis();
Sort.QuickSortRand(b, 0, n - 1);
end = System.currentTimeMillis();
System.out.print("QuickSortRand cost time(sec):");
System.out.println(end - start);
//PrintArrData(b);
start = System.currentTimeMillis();
int[] temp = new int[n];
Sort.MargeSort(c, 0, n - 1, temp);
temp = null;
end = System.currentTimeMillis();
System.out.print("MargeSort cost time(sec):");
System.out.println(end - start);
//PrintArrData(c);
start = System.currentTimeMillis();
Sort.InsertSort(d);
end = System.currentTimeMillis();
System.out.print("InstertSort cost time(sec):");
System.out.println(end - start);
//PrintArrData(d);
start = System.currentTimeMillis();
Sort.BubbleSortPlus(e);
end = System.currentTimeMillis();
System.out.print("BubbleSortPlus cost time(sec):");
System.out.println(end - start);
//PrintArrData(e);
start = System.currentTimeMillis();
Sort.BubbleSort(f);
end = System.currentTimeMillis();
System.out.print("BubbleSort cost time(sec):");
System.out.println(end - start);
//PrintArrData(f);
start = System.currentTimeMillis();
Sort.ChoseSort(g);
end = System.currentTimeMillis();
System.out.print("ChoseSort cost time(sec):");
System.out.println(end - start);
//PrintArrData(g);
}
static void PrintArrData(int[] arr) {
for (int value : arr) {
System.out.println(value);
}
System.out.println();
}
}
1 | //Sort.java |
执行条件：
编译程序NetBeans IDE 8.1
数组成员 1000
执行结果：
QuickSort cost time(sec):1
QuickSortRand cost time(sec):0
MargeSort cost time(sec):1
InstertSort cost time(sec):5
BubbleSortPlus cost time(sec):14
BubbleSort cost time(sec):18
ChoseSort cost time(sec):9
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可
