排序算法（Sorting Algorithm） 的作用在于对于给定的一个元素序列，输出满足某种顺序的该序列的一个排列。
代码实现 —— 数最小值
数组最小值
首先，如何找到n个元素的最小值，并记录它的位置？
最开始，我们默认最小值出现在数组的第1位，所以，用于记录最小值位置的变量min_pos初始值为1。
然后，枚举数组中的每个元素，并且将当前记录的最小值和枚举到的第i个元素作比较，如果当前枚举到的元素更小，说明最小值不可能出现在原来的min_pos位置，而更有可能出现的位置i。所以，将min_pos更新为i。
当扫描完整个元素后，min_pos中的位置就是最小值出现的位置。
#include <bits/stdc++.h> using namespace std; int a[1010]; int n; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; //注意：为保持认知一致，我们直接从数组第2个元素开始。数组第二个元素索引为1，不是从索引为0的元素开始哦。 int min_pos = 1; // 设置最小值位置的初始值为0，即a[1] = 0 for (int i = 2; i <= n; ++i) { if (a[i] < a[min_pos]) // 比较当前枚举到的元素与当前记录位置的元素 min_pos = i; // 如果当前记录位置的元素更小，则更新最小值出现的位置 } cout << "minimum value = " << a[min_pos] << endl; // 输出最小值 cout << "minimum value pos = " << min_pos << endl; // 输出最小值的位置 return 0; } int main() { int min_pos = 1; // 设置最小值位置的初始值为0，即a[1] = 0 for (int i = 2; i <= n; ++i) { // TODO 请补全代码找到最小值 if(a[i]<a[min_pos]) // 比较当前枚举到的元素与当前记录位置的元素 min_pos = i; // 如果当前记录位置的元素更小，则更新最小值出现的位置 } cout << "minimum value = " << a[min_pos] << endl; // 输出最小值 cout << "minimum value pos = " << min_pos << endl; // 输出最小值的位置 return 0; }
代码实现 —— 实现选择排序
实现选择排序
所以，给定长度为n的序列，我们现在用之前描述的选择排序过程用C++语言实现出来，将序列从小到大排序。
最外层用for循环枚举当前应该归位的第i个元素；
内层用上一步方法的寻找最小值位置，找出第i位一直到第n位的最小值，并且将其与原来的第i位元素交换。
具体实现代码如下：
#include <bits/stdc++.h> using namespace std; int a[1010]; int n; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; // 选择排序过程 for (int i = 1; i < n; ++i) { // 枚举应该归位的第i个元素，这里因为前n-1位归为以后， // 第n位也会归位，所以我们只枚举到n-1。 int min_pos = i; // 将最小值位置设置为当前范围i~n的首位 for (int j = i + 1; j <= n; ++j) { // 将第i个元素和剩下的元素相比较 if (a[j] < a[min_pos]) { // 如果当前元素小于之前维护的最小值 min_pos = j; // 更改最小值出现的位置 } } swap(a[i], a[min_pos]); // 将最小值与第i个位置交换 } // 输出 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; return 0; }
总结
选择排序的基本思路是：
按照1~n的顺序，将每个元素依次归位。
当归位第i个元素时，我们需要选择出第i个元素到第n个元素的最小值，并且与第i个位置的元素交换。此时，1~i的元素分别为第1小到第i小的元素。
当第n个元素归位完毕以后，整个序列的排序过程结束。
冒泡排序：
基本思想
试想一下，如果在上体育课的时候，通常学生都会随意站成一列，但是体育老师会帮忙调整学生的站位使得最终顺序是按照身高排序的。那么，回忆一下体育老师是如何调整顺序的呢？
假设体育老师想将学生从左到右按照身高从矮到高排序。通常情况下，他会从左到右扫视学生的身高。如果左边有一个同学，个子比右边的同学高，他就要将其进行调整。具体调整方法是：
如果一个同学比他右边的同学高，就让这两个同学交换位置。
如果交换过后，这个同学仍然比新的右边的同学高，那么继续交换，直到他不在比右边的同学高。
这样进行了若干次以后，队列就按照身高排好序了。
我们发现，这里我们使用了将原问题转换为规模更小的子问题的思路。
所以在选择排序的过程，相当于每次将当前序列未排序部分的最小元素归位，将未排序的序列长度缩小一位。同样，如果我们能够通过某种方式，把序列中的最大值移动到序列最后面，也可以起到将未排序序列长度缩小一位的效果。
所以，这节课我们设计的排序过程分为两步：
通过“体育老师交换方法”，使得每次我们都能把最大值移动到序列的最后一位。
利用上面的步骤进行问题转换，将未排序的序列长度缩减一个。
这就是冒泡排序的具体思路，而上面提到的“将最大值移动到最后一位”的操作，就叫做冒泡操作。
冒泡排序的思路
总结冒泡排序的思路：
冒泡排序分为n-1个阶段。
在第1个阶段，通过“冒泡”，将前n个元素的最大值移动到序列的最后一位。此时只剩前n-1个元素未排序。
在第i个阶段，此时序列前n-i+1个元素未排序。通过“冒泡”，我们将前n-i+1个元素中的最大值移动到最后一位。此时只剩前n-i个元素未排好序。
最终到第n-1个阶段，前2个元素未排序。将其中的较大值移动到后一位，则整个序列排序完毕。
单独冒泡：
if (a[i] > a[i + 1]) swap(a[i], a[i + 1])；
单独的冒泡过程：
#include <bits/stdc++.h> #define N 1010 using namespace std; int n, a[N]; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; // 冒泡阶段：连续交换过程 for (int i = 1; i < n; ++i) // 枚举两两交换的前一个元素序号 if (a[i] > a[i + 1]) swap(a[i], a[i + 1]); // 如果前一个元素大于后一个，就进行交换 // 输出 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << endl; return 0; }
完整的冒泡过程：
#include <bits/stdc++.h> #define N 1010 using namespace std; int n, a[N]; int main() { // 输入 cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; // 冒泡排序 for (int i = 1; i < n; ++i) { // 一共n-1个阶段，在第i个阶段，未排序序列长度从n-i+1到n-i。 for (int j = 1; j <= n - i; ++j) // 将序列从1到n-i+1的最大值，移到n-i+1的位置 if (a[j] > a[j + 1]) // 其中j枚举的是前后交换元素的前一个元素序号 swap(a[j], a[j + 1]); } // 输出 for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << endl; return 0; }
复杂度分析
从代码中，我们可以看到冒泡排序的主干部分有两层循环，并且每一层的循环次数都在O(n)O(n)左右的数量级。
所以完整的冒泡排序时间复杂度是O(n^2)O(n2)。
总结
冒泡排序和选择排序一样，都是将原问题转换为长度减一的子问题的过程。
冒泡排序分为n-1个阶段，每个阶段通过“冒泡”的过程，将未排序序列中的最大值移动到最后一位。
冒泡的过程，具体是通过一段连续交换过程使得最大元素被“传送”到最后一位。
练习4·代码题
明明的随机数_冒泡排序
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入描述：
每组输入有2行，第1行为1个正整数，表示所生成的随机数的个数N，第2行有N个用空格隔开的正整数，为所产生的随机数。
输出描述：
每组输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
示例 1：
输入：
10 20 40 32 67 40 20 89 300 400 15
输出：
8 15 20 32 40 67 89 300 400
代码：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 110 using namespace std; int a[N], n, cnt; int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); // TODO 请补全下述代码，使用冒泡排序完成排序 for (int i=1; i<n; i++){ for (int j=0; j<n-i; j++){ if (a[j]>a[j+1]) swap(a[j] , a[j+1]); } } cnt = 0; for (int i = 0; i < n; ++i) if (i == 0 || a[i] != a[i - 1]) a[cnt++] = a[i]; printf("%d\n", cnt); for (int i = 0; i < cnt; ++i) printf("%d ", a[i]); return 0; }
