在学习排序的过程中可以参考可视化的数据结构网站VISUALGO
Bubble sort 冒泡排序
优点：已经排好序列的部分不用发生交换
Select sort 选择排序
Insert sort 插入排序
Merge sort 归并排序
思想
分而治之思想(Divede and Conquer)
- 分:将一组待排序数列分成两个（一分为二）待排序数列进行排序，再将待排序的两个子序列进行分割，直到子序列只有一个元素
- 治:对每一个子序列进行归并排序
- 归并方法：将两个序列的头元素进行比较，将头元素较大的复制到新的序列，若一列数组没有数则将另一列数组的数都复制到新序列后面，将归并好的这一个新的序列放回原序列
伪代码：
split each element into partitions of size 1
recursively merge adjancent partitions //递归
for i = leftPartStartIndex to rightPartLastIndex inclusive
if leftPartHeadValue <= rightPartHeadValue
copy leftPartHeadValue
else: copy rightPartHeadValue
copy elements back to original arrayc++数组
1 | void mergeSort(int * unsorted, int begin, int middle, int end) { |
2 | int *temp = new int[end - begin + 1]; |
3 | int p = begin, q = middle + 1, i = 0; |
4 | // 当一列序列的头还没有被比完 |
5 | while (p <= middle && q <= end) { |
6 | //若子序列头元素大放进新序列 |
7 | if (unsorted[p] <= unsorted[q]) { |
8 | temp[i++] = unsorted[p++]; |
9 | } else { |
10 | temp[i++]= unsorted[q++]; |
11 | } |
12 | } |
13 | // 将剩下的数放进另一个序列 |
14 | while (p <= middle) { |
15 | temp[i++] = unsorted[p++]; |
16 | } |
17 | while (q <= end) { |
18 | temp[i++] = unsorted[q++]; |
19 | } |
20 | // 将临时数组放回原数组 |
21 | for (p = 0; p < i; p++) { |
22 | unsorted[begin + p] = temp[p]; |
23 | } |
24 | delete[] temp; |
25 | } |
26 | void merge(int *unsorted, int begin, int end) { |
27 | // 递归的终止条件是开始回到结束，即序列大小为1时 |
28 | if (begin < end) { |
29 | int middle = (begin + end) / 2; |
30 | merge(unsorted, begin, middle); // 一分为二 |
31 | merge(unsorted, middle + 1, end); |
32 | mergeSort(unsorted, begin, middle, end); // 递归 |
33 | } |
34 | } |
35 | int main() { |
36 | int *arrs = new int [1000001]; |
37 | int i; |
38 | for(i = 0; i< 1000001;i++){ |
39 | arrs[i] = rand() % 1000000; |
40 | } |
41 | |
42 | clock_t start, finish; |
43 | double total_time; |
44 | start = clock(); |
45 | |
46 | merge(arrs, 0, 1000000); |
47 | |
48 | finish =clock(); |
49 | total_time=(double)(finish-start)/CLOCKS_PER_SEC; |
50 | |
51 | std::cout << "\nfinish in " << total_time << " s" << std::endl; |
52 | return 0; |
53 | } |
100万的数据大概0.3秒完成排序
finish in 0.332392 s