1. 前言

本篇内容主要讲第二种排序类型，即由数值找排名排序法。

2. 相关排序算法

相关排序算法目前只有一种，即插入排序算法。

2.1 插入排序2.1.1 算法模型

插入排序的算法模型和上一篇中的最值法相似，同样分无序区和有序区。

插入排序算法模型

2.1.2 计算过程

插入排序计算过程如下：

将待排序数据视为无序区，有序区默认为空；从无序区取出任意一个数，和有序区内容逐个比较，按顺序插入到有序区数组中。重复执行，直到无序区为空，算法结束。2.1.3 编码实现

项目地址：

核心代码如下：

/** * @brief insertSort_putResultInOriginArray *  插入排序，结果存储在原数组中。排序后的数据会覆盖原数组中数据。 * @param unordered_area 无序区数据指针 * @param data_count 需要排序的数据个数 */void insertSort_putResultInOriginArray(int unordered_area[], size_t data_count){    if (data_count < 0)        return;    // 取无序区数据，插入有序区    for (int i = 0; i < data_count; i++)    {        // 无序区数据索引，因为有序区从右向左生长，所以无序区需要从右向左取数。        int unordered_area_data_index = data_count - 1 - i;        // 取出无序区右端第一个未排序数据        int unordered_area_data = unordered_area[unordered_area_data_index];        // 有序区起始地址（初始时有序区为空）        int *ordered_area_left = &unordered_area[unordered_area_data_index + 1];        int *first_bigger_data = ordered_area_left;        // 当前有序区数据个数        int ordered_area_data_count = i + 1;        // 下面遍历有序区，通过比较找到合适位置插入        // 我们要实现从左到右按从小到大排序，        // 只要将当前未排序数据，插入到第一个比当前未排序数据大的数的左边即可。        // 如果没有比当前未排序数据大的有序数，则将当前未排序数插入到有序区最右侧。        bool find_bigger_one = false;        for (int j = 0; j < ordered_area_data_count; j++)        {            if (first_bigger_data[j] > unordered_area_data)            {                first_bigger_data = &first_bigger_data[j];                find_bigger_one = true;                break;            }        }        if (find_bigger_one)        {            // 把此未排序数据插入到第一个比当前未排序数据大的数的左边            // 左边的数左移一位            for (int *ptr = ordered_area_left; ptr < first_bigger_data; ptr++)            {                *(ptr - 1) = *ptr;            }            // 插入当前未排序数到有序区            *(first_bigger_data - 1) = unordered_area_data;        }        else        {            // 将有序区全部左移一位            for (int k = 0; k < ordered_area_data_count; k++)            {                ordered_area_left[k - 1] = ordered_area_left[k];            }            // 插入当前未排序数到有序区右端第一个位置            ordered_area_left[ordered_area_data_count - 1] = unordered_area_data;        }    }    // 此时无序区为空，打印有序区    qDebug("插入排序后的数据为:");    for (int j = 0; j < data_count; j++)    {        printf("%d ", unordered_area[j]);    }    printf("\n");}

插入排序需要对数据频繁插入，使用数组效率较低，所以实现时，为了提高效率可以使用链表等数据结构。算法在最终结束时，才能知道待排序数据的最大值或最小值。

2.1.5 时间复杂度

取第1个数，插入最多需要遍历0次有序区；取第2个数，插入最多需要遍历1次有序区；依次类推： 总遍历次数为： 所以时间复杂度的数量级为，即时间复杂度为。

3. 结语

本篇文章只包含一个算法，相对来说比较简单，读者在了解算法思想的基础上，尽量自己动手编写调试一遍算法代码。算法并不是一成不变的，只要理解了算法的原理，就可以根据需要对算法进行合理优化和改进。

下一篇我们将研究整体局部排序法涉及的相关算法。

本文原创发布于Qt未来工程师，后续内容已在公众号中发布，敬请关注。