「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项无序项的排序完成
}