常见排序算法

在学习排序的过程中可以参考可视化的数据结构网站VISUALGO

Bubble sort 冒泡排序

优点:已经排好序列的部分不用发生交换

Select sort 选择排序

Insert sort 插入排序

Merge sort 归并排序

思想

分而治之思想(Divede and Conquer)

  1. :将一组待排序数列分成两个(一分为二)待排序数列进行排序,再将待排序的两个子序列进行分割,直到子序列只有一个元素
  2. :对每一个子序列进行归并排序
  3. 归并方法:将两个序列的头元素进行比较,将头元素较大的复制到新的序列,若一列数组没有数则将另一列数组的数都复制到新序列后面,将归并好的这一个新的序列放回原序列

伪代码
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 array
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
void mergeSort(int * unsorted, int begin, int middle, int end) {
int *temp = new int[end - begin + 1];
int p = begin, q = middle + 1, i = 0;
// 当一列序列的头还没有被比完
while (p <= middle && q <= end) {
//若子序列头元素大放进新序列
if (unsorted[p] <= unsorted[q]) {
temp[i++] = unsorted[p++];
} else {
temp[i++]= unsorted[q++];
}
}
// 将剩下的数放进另一个序列
while (p <= middle) {
temp[i++] = unsorted[p++];
}
while (q <= end) {
temp[i++] = unsorted[q++];
}
// 将临时数组放回原数组
for (p = 0; p < i; p++) {
unsorted[begin + p] = temp[p];
}
delete[] temp;
}
void merge(int *unsorted, int begin, int end) {
// 递归的终止条件是开始回到结束,即序列大小为1时
if (begin < end) {
int middle = (begin + end) / 2;
merge(unsorted, begin, middle); // 一分为二
merge(unsorted, middle + 1, end);
mergeSort(unsorted, begin, middle, end); // 递归
}
}
int main() {
int *arrs = new int [1000001];
int i;
for(i = 0; i< 1000001;i++){
arrs[i] = rand() % 1000000;
}
clock_t start, finish;
double total_time;
start = clock();
merge(arrs, 0, 1000000);
finish =clock();
total_time=(double)(finish-start)/CLOCKS_PER_SEC;
std::cout << "\nfinish in " << total_time << " s" << std::endl;
return 0;
}

100万的数据大概0.3秒完成排序

finish in 0.332392 s
您的支持将鼓励我继续创作!