【排序算法】直接插入排序、希尔排序、冒泡排序、快速排序、归并排序_数据结构要求在一个程序中实现四种排序算法直接插入希尔冒泡快速

注：本文实现升序排序

直接插入排序

基本思想

基本思想：保持左端的数字是有序的，将未进行操作过的右端的数字 value 与左端的进行比较，如果 左端 > value，则进行交换，重复进行比较，直到左端 < value 或者 value 到达最左端，重复相同的操作，直到所有的数字完成排序

图片来自……VisuAlgo

程序

void insertSort(int r[], int n){
	for (int i = 1; i < n; i++){
		// 如果r[i]小于前者 才需要进行交换
		if (r[i-1] > r[i]){
			int value = r[i]; // 记录当前的 value
			// 其他记录向后移动
			int j;
			for (j = i-1; r[j] > value && j >= 0; j--){
				r[j+1] = r[j];
			}
			r[j+1] = value;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

C语言 for 循环语法

for ( init; condition; increment )
{
   statement(s);
}
1
2
3
4

• init 会首先被执行，且只会执行一次。这一步允许您声明并初始化任何循环控制变量。您也可以不在这里写任何语句，只要有一个分号出现即可。
• 接下来，会判断 condition。如果为真，则执行循环主体。如果为假，则不执行循环主体，且控制流会跳转到紧接着 for 循环的下一条语句。
• 在执行完 for 循环主体后，控制流会跳回上面的 increment 语句。该语句允许您更新循环控制变量。该语句可以留空，只要在条件后有一个分号出现即可。
• 条件再次被判断。如果为真，则执行循环，这个过程会不断重复（循环主体，然后增加步值，再然后重新判断条件）。在条件变为假时，for 循环终止。

算法分析

时间复杂度

$O(n^2)$

空间复杂度

$O(1)$

算法特点

• 稳定排序
• 适合初始记录基本有序

折半插入排序

基本思想

在直接插入排序中，左端是一个有序序列，所以可以使用折半查找法，查找 value 在已排好序序列中的位置，然后再进行移动。

程序

void binaryInsertSort(int r[], int n){
	for (int i = 1; i < n; i++){
		if (r[i-1] > r[i]){
			int value = r[i];
			int low = 0, high = i-1;
			// 注意等号！！！当 low==high 时，如果 r[mid] > temp, 那么 high--, 此时 low 所在位置是 value 要插入的位置；当 r[mid] < temp，那么 low++，此时 low 所在位置同样是 value 要插入的位置
			while(low <= high){
				int mid = (low + high) / 2;
				if (r[mid] > value){
					high = mid - 1;
				}else{
					low = mid + 1;
				}
			}
			for (int j = i-1; j >= low; j--){
				r[j+1] = r[j];
			}
			r[low] = value;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

算法分析

时间复杂度

$O(n^2)$

空间复杂度

$O(1)$

算法特点

• 稳定排序
• 适合初始记录无序，$n$较大的情况

希尔排序

基本思想

采用分组插入的方法，现将整个待排序记录序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插入排序，然后增加每组的数据量，重新分组。这样当经过几次分组排序后，整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

程序

// 希尔插入 （直接插入排序的 dk 等于 1）
int shellInsert(int r[], int n, int dk){
	for (int i = dk; i < n; i += dk){
		if (r[i-dk] > r[i]){
			int value = r[i];
			int j;
			for (j = i - dk; r[j] > value && j >= 0; j -= dk){
				r[j+dk] = r[j];
			}
			r[j+dk] = r[j];
		}
	}
	return r;
}
// 希尔排序
void shellSort(int r[], int n){
	int dt[3] = { 5,3,1 }; // 可以更改，公因数尽量只有 1
	//int *sSort = r;
	for (int k = 0; k < sizeof(dt) / sizeof(int); k++) {
		r  = shellInsert(r, n, dt[k]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

算法分析

算法特点

• 排序不稳定

冒泡排序

void BubbleSort(int* a, int len) {
	for (int i = 0; i < len - 1; i++) {
		int flag = 1;
		for (int j = 0; j < len - i - 1; j++) {
			if (a[j] > a[j + 1]) {
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				flag = 0;
			}
		}
		if (flag) {
			break;
		}
	}
}

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

快速排序

// 快排
int partition(vector<int> & nums, int low, int high){
    int i = rand() % (high - low + 1) + low; // 随机选择一个主元
    swap(nums[low], nums[i]);
    int pivot = nums[low];
    while (low < high){
        while(low < high && nums[high] >= pivot){
            high--;
        }
        nums[low] = nums[high];
        while(low < high && nums[low] <= pivot){
            low++;
        }
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}
void qSort(vector<int> &nums, int low, int high){
    if (low < high){
        int pivotIdx = partition(nums, low, high);
        qSort(nums, pivotIdx + 1, high);
        qSort(nums, low, pivotIdx - 1);
    }
}
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

简单选择排序

// 简单选择排序
void selectSort(int* r, int len) {
	/*
	* 每一趟从待排序的记录中选择最小的关键字，按顺序放在已排好序的序列最后，直到排完为止
	*/
	for (int i = 0; i < len - 1; i++) {
		int k = i;
		for (int j = i + 1; j < len; j++) {
			k = r[j] < r[k] ? j : k;	// 记录最小关键字的下标
		}
		if (k != i) {
			int tmp = r[k];
			r[k] = r[i];
			r[i] = tmp;
		}
	}
	printf("selectSort\n");
	for (int i = 0; i < len; i++) {
		printf("%d ", r[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

归并排序

vector<int> sortArray(vector<int>& nums) {
    vector<int> tmp(nums.size());
    // 归并排序
    mergeSort(nums, tmp, 0, nums.size() - 1);
    return nums;
}
void mergeSort(vector<int> &nums, vector<int> &tmp, int low, int high){
    if (low >= high){
        return ;
    }
    int mid = low + ((high - low) >> 1);
    mergeSort(nums, tmp, low, mid);
    mergeSort(nums, tmp, mid + 1, high);
    merge(nums, tmp, low, high);
}
void merge(vector<int> &nums, vector<int> &tmp, int low, int high){
    int mid = low + ((high - low) >> 1);
    int i = low, j = mid + 1;
    int k = low;
    // 原始：[23, 46] [13, 34]
    // [13, ...]
    // 用一个临时数组tmp暂存原始待合并数据，避免被覆盖
    for (int t = low; t <= high; t++){
        tmp[t] = nums[t];
    }
    while (i <= mid && j <= high){
        if (tmp[i] <= tmp[j]){
            nums[k++] = tmp[i++];
        }else {
            nums[k++] = tmp[j++];
        }
    }

    while (i <= mid){
        nums[k++] = tmp[i++];
    }
    while (j <= high){
        nums[k++] = tmp[j++];
    }

}
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

912. 排序数组