排序算法总结

发表于 更新于 分类于 阅读次数： 本文字数： 5.6k 阅读时长 ≈ 10 分钟

辅助函数

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

// 交换函数
void swap(vector<int>& nums, int x, int y) {
	int tmp = nums[x];
	nums[x] = nums[y];
	nums[y] = tmp;
}

// 测试函数
void test(vector<int>& nums) {
	for (auto i : nums) cout << i << ' ';
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/* 
选择排序
在每一轮找到最小的值插入到数组前面
时间复杂度 O(n^2)
空间复杂度 O(1)
稳定性 无
*/
void selectionSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n - 1; ++i) {
		int min_el = INT_MAX, min_index = -1;
		for (int j = i; j < n; ++j) {
			if (nums[j] < min_el) {
				min_el = nums[j];
				min_index = j;
			}
		}
		swap(nums, i, min_index);
	}
}

冒泡排序

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

/*
冒泡排序
两两比较大小 大的数字往后移
时间复杂度 O(n^2)
空间复杂度 O(1)
*/
void bubbleSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n - 1; ++i)
		for (int j = 0; j < n - i; ++j) {
			if (j + 1 < n && nums[j] > nums[j + 1]) swap(nums, j, j + 1);
		}
}

直接插入排序

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

/*
直接插入排序
依次选择最小的值插入到数组前面
时间复杂度 O(n^2)
空间复杂度 O(1)
稳定性 有
*/
void insertSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 1; i < n; ++i)
		for (int j = i - 1; j >= 0 && nums[j + 1] < nums[j]; --j)
			swap(nums, j + 1, 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

/*
二分插入排序
根据前面数组的有序性 二分查找最小的值插入到数组前面
时间复杂度 O(n^2)
空间复杂度 O(1)
稳定性 有
*/
int lower_bound(vector<int>& nums, int start, int end, int x) {
	int l = start, r = end;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (x > nums[mid]) l = mid + 1;
		else r = mid - 1;
	}
	return l;
}

void insertSort_2(vector<int>& nums) {
	int n = nums.size();
	if (n <= 1) return;
	// 前2个元素按从小到大排序
	if (nums[1] < nums[0]) swap(nums, 0, 1);
	for (int i = 2; i < n; ++i) {
		int pos = lower_bound(nums, 0, i - 1, nums[i] + 1);
		pos = pos == n ? n - 1 : pos;
		int x = nums[i];
		// 插入元素
		for (int j = i - 1; j >= pos; --j) {
			swap(nums, j, j + 1);
		}
	}
}

希尔排序

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

/*
希尔排序
对子表进行插入排序
时间复杂度(n^2)
空间复杂度O(1)
稳定性 无
*/
void shellSort(vector<int>& nums, int d) {
	int n = nums.size();
	while (d >= 1) {
		// 以下为插入排序的流程 不过步长改为了d
		for (int i = d; i < n; ++i) {
			for (int j = i - d; j >= 0 && nums[j + d] < nums[j]; j -= d) {
				swap(nums, j + d, j);
			}
		}
		d /= 2;
	}
}

快速排序

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

/*
快速排序
时间复杂度 O(n*log n)
空间复杂度 O(log n)
稳定性 无
*/
// 快速排序 第一种写法
void quickSort(vector<int>& nums, int start, int end) {
	if (start >= end) return;
	int left = start, right = end, pivot = nums[start];
	while (left < right) {
		// 移动右指针 直到遇到小于pivot的元素
		for (; left < right && nums[right] >= pivot; )  --right;
		// 处理比pivot小的元素
		nums[left] = nums[right];
		// 移动左指针 直到遇到大于pivot的元素
		for (; left < right && nums[left] <= pivot; ) ++left;
		// 处理比pivot大的元素
		nums[right] = nums[left];
	}
	// 归位pivot
	nums[left] = pivot;
	quickSort(nums, start, left - 1);
	quickSort(nums, left + 1, end);
}
// 快速排序 第二种写法
void quickSort2(vector<int>& nums, int l, int r) {
	if (l >= r) return;
	int pivot = nums[l], slow = l;
	for (int i = l; i <= r; ++i) {
		if (nums[i] <= pivot) {
			swap(nums, i, slow);
			++slow;
		}
	}
	swap(nums, slow - 1, l);
	quickSort2(nums, l, slow - 2);
	quickSort2(nums, slow, r);
}

堆排序

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
54
55
56
57
58
59
60

/*
堆排序
时间复杂度 O(n*log n)
空间复杂度 O(1)
稳定性 无
*/
// 向上调整
void heapInsert(vector<int>& heap, int i) {
	while (i >= 1 && heap[i] > heap[(i - 1) / 2]) {
		swap(heap, i, (i - 1) / 2);
		i = (i - 1) / 2;
	}
}

// 向下调整
void heapify(vector<int>& heap, int i, int size) {
	int l = 2 * i + 1;
	while (l < size) {
		// 从左右孩子中选出最大的孩子
		int mx = l + 1 < size && heap[l] < heap[l + 1] ? l + 1 : l;
		// 比较最大的孩子与当前元素
		if (heap[i] >= heap[mx]) break;
		// 如果当前元素比最大的孩子小 则向最大的孩子移动
		swap(heap, i, mx);
		// 更新 i, l
		i = mx;
		l = 2 * i + 1;
	}

}

// 建堆 自下而上
void build_bottom(vector<int>& ns) {
	int n = ns.size();
	for (int i = n - 1; i >= 0; --i) {
		heapify(ns, i, n);
	}
}

// 建堆 自上而下
void build_top(vector<int>& ns) {
	int n = ns.size();
	for (int i = 0; i < n; ++i) {
		heapInsert(ns, i);
	}
}

void heapSort(vector<int>& nums, void(*build)(vector<int>& ns)) {
	int n = nums.size(), last = n;
	// 建堆 
	build_bottom(nums);
	// 大数归位
	while (last > 1) {
		swap(nums, 0, last - 1);
		--last;
		heapify(nums, 0, last);
	}
}

归并排序

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

/*
归并排序
递归将数组分成两部分 分别将这两部分排序好 再合并 最后将辅助数组里面的值刷回原数组
时间复杂度 O(n*log n)
空间复杂度 O(n)
稳定性 有
*/

void merge(vector<int>& nums, int l, int mid, int r) {
	vector<int> help((int)nums.size(), 0); // 辅助数组
	int i = l, a = l, b = mid + 1;
	while (a <= mid && b <= r) {
		help[i++] = nums[a] <= nums[b] ? nums[a++] : nums[b++];
	}
	// 必有一个指针越界 要么是a 要么是b
	while (a <= mid) {
		help[i++] = nums[a++];
	}
	while (b <= r) {
		help[i++] = nums[b++];
	}
	// 将辅助数组中的数据刷回原数组
	for (int j = l; j <= r; ++j) {
		nums[j] = help[j];
	}
}

void mergeSort(vector<int>& nums, int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	mergeSort(nums, l, mid);
	mergeSort(nums, mid + 1, r);
	merge(nums, l, mid, r);
}

桶排序（基数排序）

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

/*
桶排序 (基数排序)
时间复杂度 O(n)
空间复杂度 O(n + k) k为桶的数量
稳定性 有
*/
// 十进制
int BASE = 10;
// 计数位数
int countDigit(int x) {
	int cnt = 0;
	while (x > 0) {
		x /= BASE;
		++cnt;
	}
	return cnt;
}

void radixSort(vector<int>& nums) {
	int min_el = INT_MAX, max_el = INT_MIN, n = nums.size();
	// 获取最小值和最大值
	for (auto i : nums) {
		min_el = min(min_el, i);
		max_el = max(max_el, i);
	}
	// bits：nums中最大值的位数
	int bits = countDigit(max_el);
	// 将nums中的所有值减去最小值
	for (int i = 0; i < n; ++i) nums[i] -= min_el;
	vector<int> help(n, 0);
	// 桶排序
	for (int offset = 1, i = 0; i < bits; ++i, offset *= BASE) {
		vector<int> cnts(BASE, 0);
		// 统计各个位数的次数
		for (auto num : nums) cnts[(num / offset) % BASE]++;
		// 计算前缀位数次序和
		for (int j = 1; j < BASE; ++j) cnts[j] += cnts[j - 1];
		// 倒序遍历nums 插入对应位置的元素到help中
		for (int j = n - 1; j >= 0; --j) {
			help[--cnts[(nums[j] / offset) % BASE]] = nums[j];
		}
		// 将help数组中的值刷入nums中
		for (int j = 0; j < n; ++j) nums[j] = help[j];
	}
	// 还原数组
	for (int i = 0; i < n; ++i) nums[i] += min_el;
}