sort

在学习排序的过程中可以参考可视化的数据结构网站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
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
您的支持将鼓励我继续创作!