科技 · 编程
C++ 数组与排序算法
通过冒泡排序、选择排序和插入排序，理解 C++ 数组在基础排序算法中的实际应用。
本系列为 C++ 的入门学习者服务，旨在于为此前无 C++ 基础的学习者简单介绍关于 C++ 语言基础的部分知识，如果已入门 C++，则不需要阅读本系列。
4.1 排序问题
排序是数据处理中经常使用的一种重要运算。其功能是将数据元素的无序序列调整为有序序列。
- 数据元素一般包含多个数据项，排序时可选择其中一个可排序的数据项作为依据，称为排序关键字
- 可以保证排序结果唯一性的关键字称为主关键字(次关键字)
- 从小到大排序称升序，反之称为降序
4.2 常用排序算法
1. 冒泡排序 (Bubble Sort)
(1) 基本思想
按关键字两两比较一组元素，如果发现逆序则交换，从而依次将最大数向右移，每一次当整个循环完成后，都将当次比较的元素中的最大数交换到末端，而后只用比较除了最大数（即数组最末尾的数）外的 n-1 个数，直到所有的对象都排好序为止。
(2) 算法示例
对序列 { 21,25,49,25,16,8 } 内的元素采用冒泡排序算法进行从小到大排序。
冒泡排序示意图
(3) 代码示例
for(int i = 0; i < n; i++) //每次大循环都缩减一个比较对象个数（即每次循环都确定比较组中的末对象）{ int change = 0; //规定还未发生交换 for(int j = 0; j < n-1-i; j++) //从0位置到(n-1)-i位置依次进行比较交换，从而将较大数依次右移，整个循环结束后最大数将被放到(n-1)-i位置 { if(a[j] > a[j+1]) //比较前一项和后一项的大小 { int temp = a[j]; //缓存较大项 a[j] = a[j+1]; //将较小项放到前面 a[j+1] = temp; //将较大项放到后面 change = 1; //发生交换 } } if (!change) break; //当一次交换都不发生的时候，说明已经排序完成}2. 选择排序 (Selection Sort)
(1) 基本思想
每一次从待排序的记录中选出关键字最小的元素，顺序放在已排好的子序列后面，直到全部记录排序完成。
即：第 1 轮遍历整个序列，找到序列中最小的数据，将该数据与第 1 个数据进行交换，至此一轮结束，最小的数据被交换到最前面；然后缩小遍历范围，按照同样的方法继续下一轮，直至最后一个数据。
(2) 算法示例
对序列 { 21,25,49,25,16,8 } 内的元素采用选择排序算法进行从小到大排序。
选择排序示意图
(3) 代码示例
int i, j, k, temp;for (i = 0; i < n; i++) //每次大循环都缩减一个比较对象个数（即每次循环都确定比较组中的首对象）{ k = i; //规定最小项的位置 temp = a[i]; //规定最小项的大小 for (j = i + 1; j < n; j++) //从(i+1)位置到(n-1)位置依次与最小项k位置进行比较，找出比较组中的最小数 { if (a[j] < temp) //比较定义的较小项a[k]和当前小循环项a[j]的大小，找出新的较小项 { k = j; //更新较小项的位置 temp = a[j]; //更新较小项的大小 } } if (k != i) //如果最小项和当前大循环项不相等 { temp = a[i]; //缓存较大项 a[i] = a[k]; //将较小项放到当前大循环项的位置 a[k] = temp; //将较大项放到原来较小项的位置 }}3. 插入排序 (Insertion Sort)
(1) 基本思想
将 n 个元素的序列分为已有序和无序两个部分，每次处理就是将无序序列的第 1 个元素与有序序列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序序列的合适位置中。
注：插入排序包括直接插入排序和对半插入排序。
(2) 直接插入排序
① 算法过程
当插入第 i 位置的元素时，前面第 0 到 i-1 的位置都已排好序，将第 i 位置的元素从后向前与前面的元素进行比较，找到第 1 个比它小的，则将第 i 位置的元素插入到该元素之后。
② 算法示例
对序列 { 21,25,49,25,16,8 } 内的元素采用直接插入排序算法进行从小到大排序。
直接插入排序示意图
③ 代码示例
for (i = 1; i < n; i++) //从第二项开始建立比较组，其中前面的项是有序数列，第i项就是无序项{ temp = a[i]; //缓存无序项 for (j = i; j > 0; j--) //从(无序项-1)的位置开始比较 { if (temp < a[j - 1]) //向前一项依次比较，若前一项比无序项大 a[j] = a[j - 1]; //则将前一项往后移到无序项的位置进行覆盖，同时前一项的原位置空出 else break; //一直到有序项中的某一个前一项比无序项小，则最后剩余一个空位置 } a[j] = temp; //则当前空位置就应该放入无序项，第i项无序项的排序完成}4.3 三种排序方式的比较
1. 冒泡排序
- 优点：可利用原来数据排列的部分有序性，是一种稳定排序
- 缺点：比较慢，每次只能移动相邻两个数据
2. 选择排序
-
优点：程序可读性比较高，易于理解
-
缺点：以前所做的工作和序列的部分有序性完全不能利用，效率比较低
3. 插入排序
-
优点：是稳定排序，速度比较快
-
缺点：比较次数无法确定，比较次数越少，插入点后的移动越多