No testdata at current.

No submission language available for this problem.

👉基础排序练习

基础算法——排序 I

排序，狭义上讲即将序列有序化。

例如：3 5 6 8 1 变为 1 3 5 6 8 升序或 8 6 5 3 1 降序。

本笔记主要简单介绍四种基础排序算法，熟练掌握的前提是对数组有一定的熟练度。

1. 桶排序
2. 冒泡排序
3. 选择排序
4. 插入排序

一、桶排序

桶排序是计数数组的一种应用排序。

核心思路：令 cnt[i] 记录 i 出现的次数，对于 cnt[] 下标本身就有序，因此可以借 cnt[] 数组的下标有序性，对 i 出现的次数进行处理

应用条件：被排序的数据必须在一个合理的范围内。若数据最值差异太大，将无法开辟计数数组空间进行计数。

#include <iostream>
using namespace std;


int main() {

	//      下标 0  1  2  3  4  5  6  7  8  9  10
	int a[11] = {0, 9, 9, 4, 5, 0, 9, 1, 2, 4, 5}; // 数组 
	int n = 10; // 这里只考察 1~10 下标元素，共 10 个
	
	/* 由于是实验性代码，因此规定数据范围在 0 ~ 10，因此 int cnt[11]; 足够使用了 */
	int cnt[11] = {0}; // 从 0 开始记，因此要初始化；当然也可以放到全局区域
	for (int i = 1;  i <= n; i ++) {
		cnt[ a[i] ] ++; // 记录 a[i] 这个数出现的次数
	}

	// 从小到大输出：下标 i 从小到大遍历，i 出现过 cnt[i] 次，就输出 cnt[i] 次
	// cout << "从小到大：";
	for (int i = 0; i <= 10; i ++) { // 因为数字范围现在规定为 0~10
		for (int j = 1; j <= cnt[i]; j ++) {
			cout << i << ' ';
		}
	}
	cout << endl;

	// 从大到小输出：下标 i 从大到小遍历，i 出现过 cnt[i] 次，就输出 cnt[i] 次
	// cout << "从大到小：";
	for (int i = 10; i >= 0; i --) { // 因为数字范围现在规定为 0~10
		for (int j = 1; j <= cnt[i]; j ++) {
			cout << i << ' ';
		}
	}
	cout << endl;

    return 0;
}

---

若需要排序的数据出现最值差异过大，且未给出实际范围时，桶排序便不可使用。（桶排序是典型的用存储空间换时效的算法，但当它无法使用是，便只能使用时间换空间算法）

二、冒泡排序

冒泡排序是基于比较的算法。

核心思想：相邻位置上的数据进行比较，按升序或降序要求有选择进行交换。

例：将 4 3 9 2 0 升序排序

位置 (1, 2) 比较：3 4 9 2 0

位置 (2, 3) 比较：3 4 9 2 0

位置 (3, 4) 比较：3 4 2 9 0

位置 (4, 5) 比较：3 4 2 0 9

从左往右一趟就像冒泡一样，将一个最值（数据）的位置确定，并发现 5 个数据比较了 4 次（因为 5 个数据间隔为 4）。

朴素逻辑：一趟确定一个数据的位置，n 趟可以确定 n 个数据的位置。

#include <iostream>
using namespace std;

int main() {

	//      下标 0  1  2  3  4  5  6  7  8  9  10
	int a[11] = {0, 9, 9, 4, 5, 0, 9, 1, 2, 4, 5}; // 数组 
	int n = 10; // 这里只考察 1~10 下标元素，共 10 个
	
	for (int i = 1; i <= n; i ++) { // n 趟
		for (int j = 1; j <= n - 1; j ++) { // 每趟比较 n - 1 次
			// 若后面的更小，则交换后为升序（反之为降序）
			if (a[j] > a[j + 1]) { 
				int t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}
	}

	for (int i = 1; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	
    return 0;
}

优化逻辑1：n 个位置，若其中 n - 1 个位置都是正确的，剩下的一个必然正确。因此只需要用 n - 1 趟确定 n - 1 个位置即可

优化逻辑2：最值已经排好后，将不会再变动，因此也不需要比较。因此每一趟都可以比前一趟最后少比一次最后的位置。

优化逻辑3：在某一趟中，若序列未发生变动（没有发生交换），说明序列已然有序，可以提前结束排序动作。（因此，若对已然有序的序列进行冒泡排序操作，最少比较 n - 1 次便可确定是否有序）

// 优化后
#include <iostream>
using namespace std;

int main() {

	//      下标 0  1  2  3  4  5  6  7  8  9  10
	int a[11] = {0, 9, 9, 4, 5, 0, 9, 1, 2, 4, 5}; // 数组 
	int n = 10; // 这里只考察 1~10 下标元素，共 10 个
	

	// 优化1：n -  趟
	for (int i = 1; i <= n - 1; i ++) { 
		// 优化2：每趟比较 n - i 次(第一次 n - 1 次，此后每次少一次相当于 n - i 次)
		// 优化3：设计 ok 标记判断是否有交换发生
		bool ok = true;
		for (int j = 1; j <= n - i; j ++) { 
			// 若后面的更小，则交换后为升序（反之为降序）
			if (a[j] > a[j + 1]) { 
				int t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
				ok = false;
			}
		}

		if (ok) {
			// ok 未被改变，则说明 23 未被执行，即未有交换发生，可以提前结束排序
			break;
		}
	}

	for (int i = 1; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	
    return 0;
}

---

三、选择排序

核心思想：每次从未排序中选择一个最值放到未排序部分的第一个位置。

该算法的前置内容：数组中找最值的位置。

例：将 4 3 9 2 0 升序排序（加粗表示序列被选择后，还未有序的部分）

位置 (1, 5) 未排序，找最小 0：0 3 9 2 4

位置 (2, 5) 未排序，找最小 2：0 2 9 3 4

位置 (3, 5) 未排序，找最小 3：0 2 3 9 4

位置 (4, 5) 未排序，找最小 4：0 2 3 4 9

构建逻辑：每次选择一个最值，共 n 个数据，选择 n - 1 次即可。（最后一个必然在正确的位置）

#include <iostream>
using namespace std;

int main() {

	//      下标 0  1  2  3  4  5  6  7  8  9  10
	int a[11] = {0, 9, 9, 4, 5, 0, 9, 1, 2, 4, 5}; // 数组 
	int n = 10; // 这里只考察 1~10 下标元素，共 10 个
	

	// 选择 n - 1 次
	for (int i = 1; i <= n - 1; i ++) { 
		// i ~ n 是未排序的部分
		// 找到最值的位置存到 k，最终换到 i	
		int k = i; 
		for (int j = i + 1; j <= n; j ++) {
			if (a[j] < a[k]) {
				k = j;
			}
		}
		// 将最值换到未排序的第一个位置，即 i 
		swap(a[i], a[k]);
	}

	for (int i = 1; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	
    return 0;
}

---

四、插入排序

核心思路：从未排序的部分，往有序的部分从后向前插入。

例：将 4 3 9 2 0 升序排序

假定第一个位置已经有序：4 3 9 2 0

位置 (2, 5) 未有序，3 向前插：3 4 9 2 0

位置 (3, 5) 未有序，9 向前插：3 4 9 2 0

位置 (4, 5) 未有序，2 向前插：2 3 4 9 0

位置 (5, 5) 未有序，0 向前插：0 2 3 4 9

构建逻辑：（对代码构建能力需要熟练度要求）从第 2 个数据开始，从后向前进行插入比较，若前面的需要让位则直接让位交换即可。

#include <iostream>
using namespace std;

int main() {

	//      下标 0  1  2  3  4  5  6  7  8  9  10
	int a[11] = {0, 9, 9, 4, 5, 0, 9, 1, 2, 4, 5}; // 数组 
	int n = 10; // 这里只考察 1~10 下标元素，共 10 个
	
	// 从第 2 个位置开始 
	for (int i = 2; i <= n; i ++) { 
		int j = i;
		// 只要前面有比 a[j] 大的，就让位交换
		/* 若代码构建能力强，可以优化为数据移动而不是交换 */
		while (j > 1 && a[j - 1] > a[j]) {
			swap(a[j - 1], a[j]);
			j --;
		}
	}

	for (int i = 1; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	
    return 0;
}

// for 写法
#include <iostream>
using namespace std;

int main() {

	//      下标 0  1  2  3  4  5  6  7  8  9  10
	int a[11] = {0, 9, 9, 4, 5, 0, 9, 1, 2, 4, 5}; // 数组 
	int n = 10; // 这里只考察 1~10 下标元素，共 10 个
	
	// 从第 2 个位置开始 
	for (int i = 2; i <= n; i ++) { 
		// 只要前面有比 a[j] 大的，就让位交换
		/* 若代码构建能力强，可以优化为数据移动而不是交换 */
		for (int j = i; j > 1 && a[j - 1] > a[j]; j --) {
			swap(a[j - 1], a[j]);
		}
	}

	for (int i = 1; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	
    return 0;
}

---