概述
本实验旨在评估不同排序算法的时间复杂度。
本实验使用了C++语言实现冒泡排序、插入排序、归并排序以及快速排序四种常见的排序算法。通过度量在不同的数据规模下，使用不同的排序算法所耗时间，评估不同算法对数组排序的时间复杂度。
实验结果是：在十万数量级下，冒泡排序以及插入排序已经分别消耗了32s和17s。在百万数量级下的排序时间已经超出可以等待的时间范围，因此在百万数量级只评估归并排序和快速排序两种方法。
在数据规模较小时（数组大小<=1000)，四种排序算法时间差异不大。
在数据规模较大时（数组大小>=10000），归并排序和快速排序相较于冒泡排序和插入排序要快100倍以上。
实验设计
算法实现原理
冒泡排序
每一次循环将最小（或最大）的数上升（或下沉）交换到数组的头部（尾部）。
在每一次循环后，前i个数（或后i个数）是有序的。
插入排序
每一次循环将无序的单个数字插入到有序的位置。
在每一次循环后，前i个数（或后i个数）是有序的。
归并排序
整体使用递归的思想，先进行二分分隔，对每一个最小单元进行比较。
在每一个最小单元是有序的情况下，进行比较和合并。
快速排序
整体使用递归的思想。
先确定一个哨兵数字，第一轮排序过后，在它左侧的数字都比它小，它右侧的数字都比它大（或相等）。
在每一轮排序过后，哨兵数字在整体当中的位置即被确定。
此后再分别对哨兵数字左右两侧的数组选择哨兵数字，排序…
算法设计与分析
在算法设计与分析里面详细解释算法的细节，核心代码或伪代码，并对算法的时间复杂度进行分析
冒泡排序
1
2
3
4
5
6
7
8
9
10
11// Bubble sort
int *bubbleSort(int array[], int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array[j], array[j + 1]);
}
}
}
return array;
}每一次i循环把最大值下沉到数组最后。
总共需要比较约$n^2$次（双层for循环），时间复杂度$O(n^2)$。
插入排序
1
2
3
4
5
6
7
8
9
10
11// Insertion sort
int *insertionSort(int array[], int size) {
for (int i = 1; i < size; i++) {
int j = i;
while (j > 0 && array[j] < array[j - 1]) {
swap(array[j], array[j - 1]);
j--;
}
}
return array;
}每一次i循环确定前第i个值是有序的，把第i个值通过逐个比较插入到前面的有序数组之中。
总共需要比较约$n^2$次（双层for循环），时间复杂度$O(n^2)$。
归并排序
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// Merge sort
int *mergeSort(int array[], int size) {
if (size <= 1) {
return array;
}
int mid = size / 2;
int *left = new int[mid];
int *right = new int[size - mid];
for (int i = 0; i < mid; i++) {
left[i] = array[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = array[i];
}
mergeSort(left, mid);
mergeSort(right, size - mid);
int i = 0, j = 0, k = 0;
while (i < mid && j < size - mid) {
if (left[i] < right[j]) {
array[k++] = left[i++];
} else {
array[k++] = right[j++];
}
}
while (i < mid) {
array[k++] = left[i++];
}
while (j < size - mid) {
array[k++] = right[j++];
}
return array;
}通过递归将数组一层层分隔成左右两部分，直到每一块只有一个数的时候进行合并。
合并的时候使用双指针进行比较。总共分成$\lg n$层，每一层合并需要比较$n$次，时间复杂度为$O(n\lg n)$。
快速排序
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// Quick sort
int *quickSort(int array[], int size) {
if (size <= 1) {
return array;
}
int pivot = array[0];
int i = 1, j = size - 1;
while (i <= j) {
while (i <= j && array[i] < pivot) {
i++;
}
while (i <= j && array[j] > pivot) {
j--;
}
if (i <= j) {
swap(array[i], array[j]);
i++;
j--;
}
}
array[0] = array[j];
array[j] = pivot;
quickSort(array, j);
quickSort(array + j + 1, size - j - 1);
return array;
}把数组第一个值作为哨兵数，使用双指针进行比较。i和j分别表示比哨兵数小的最大值和比哨兵数大的最小值，直到i和j相遇。将i和j位置上的数进行互换，直到i和j相遇时，i左侧没有比哨兵数大的值和j右侧没有比哨兵数小的值。
在这一轮结束后，哨兵数的位置已经确定。再分别对哨兵数左右两侧的数组进行递归排序。
实验结果说明与分析
实验设置
输入
无
输出
- 目前测试的数据规模
- 目前使用的排序算法
- 所耗时间
实验结果以及相应的分析
1 | Array size: 10 |
可以看到数据量在10000的时候，冒泡和插入排序已经使用了100-200ms了，但与此同时归并和快速排序不到2ms。
在数据量到100000的时候，冒泡和插入排序已经使用了数十秒，但归并和快速排序不到20ms。
在更多数据量的时候，使用归并和快速排序算法速度更快。
总结
通过此实验，了解了四种常见的排序算法（冒泡、插入、归并、快速排序）的时间复杂度和评估方法。
通过直观的时间测量了解了不同的排序算法的适用范围和优劣。
代码开源在：https://gitee.com/littlebear0729/data-structure-and-algorithm