排序算法实现总结_排序算法实现与性能分析、评测:编写程序,实现上述冒泡排序、简单选择排序、简单插

一、 插入排序

设有数据{a1, a2, a3, …,an}。从低向上进行排序。假设a1, a2, a3, …, ai 已经排序完成， 需要将a(i-1) 插入到合适的位置；

具体实现代码如下：

void InsertSort(int *arr, int len)
{
   
	for(int i = 1; i < len; i++){
   
		int tmp = arr[i];
		int j = i-1;
		while(j >= 0 && arr[j] >= tmp){
   
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = tmp;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、 合并排序

使用分治思想设计排序算法， 将原问题分解成2个子问题求解，递归调用自身求得子问题的解之后，合并子问题的解，可以得到原问题的解；
原问题经过二分之后，在递归树中存在logn个子问题，对于每一个子问题都要进行merge合并操作，每次合并操作的时间代价是n；因此， 时间复杂度是nlogn;
合并排序的代码如下：

void Merge(int* arr, int *tmpArr, int low, int pivot, int high) {
   
	int i = low, j = pivot + 1;
	int index = low;
	while (i <= pivot && j <= high) {
   
		if (arr[i] < arr[j])
			tmpArr[index++] = arr[i++];
		else
			tmpArr[index++] = arr[j++];
	}

	while (i <= pivot)
		tmpArr[index++] = arr[i++];
	while (j <= high)
		tmpArr[index++] = arr[j++];

	for (int i = low; i <= high; i++)
		arr[i] = tmpArr[i];
}

void MergeSort(int* arr, int *tmpArr, int low, int high) {
   
	
	if (low < high) {
   
		int pivot = (high + low)
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