一、排序概念的介绍
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的 - 内部排序：数据元素全部放在内存中的排序
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内存和外存之间移动数据的排序
二、直接插入排序
2.1 原理
例如，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序
具体步骤如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5
例如，对数组[4, 2, 5, 1, 6, 3]进行排序，使用直接插入排序，如下：（升序）
动图演示：（数据不和上面相同）
- 时间复杂度最好情况下为
O(N)，此时待排序列为升序，或者说接近升序 - 时间复杂度最坏情况下为
O(N^2)，此时待排序列为逆序，或者说接近逆序 - 总的来说，直接插入排序的时间复杂度为
O(N^2) - 在原有的数组上操作，空间复杂度为
O(1)
2.2 代码实现（C/C++）
C语言代码如下：（升序）
// 直接插入排序
void InsertSort(int* arr, int n) // arr:需要排序的数组; n:数组的大小
{
for (int i = 0; i < n-1; ++i) // 达到n-1时，数组已经有序，无需再遍历最后一次，避免多余的循环
{
// [0, end]有序，把end+1位置的值插入，保持有序
int end = i; // 记录有序序列的最后一个下标
int tmp = arr[end + 1]; // 保存等待插入的值
while (end >= 0)
{
if (arr[end] > tmp) // arr[end]比要插入的数大，向后移动
{
arr[end + 1] = arr[end]; // 向后移，进行覆盖，tmp已经保存被覆盖的值
--end; // 迭代
}
else // arr[end]比要插入的数小，已有序，跳出循环
{
break;
}
}
arr[end + 1] = tmp; // 进行插入
}
}
C++代码：（升序）
// 直接插入排序
void InsertSort(vector<int>& arr)
{
int n = arr.size();
for (int i = 0; i < n - 1; ++i) // 达到n-1时，数组已经有序，无需再遍历最后一次，避免多余的循环
{
// [0, end]有序，把end+1位置的值插入，保持有序
int end = i; // 记录有序序列的最后一个下标
int tmp = arr[end + 1]; // 保存等待插入的值
while (end >= 0)
{
if (arr[end] > tmp) // arr[end]比要插入的数大，向后移动
{
arr[end + 1] = arr[end]; // 向后移，进行覆盖，tmp已经保存被覆盖的值
--end; // 迭代
}
else // arr[end]比要插入的数小，已有序，跳出循环
{
break;
}
}
arr[end + 1] = tmp; // 进行插入
}
}
2.3 特性总结
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：
O(N^2) - 空间复杂度：
O(1)，它是一种稳定的排序算法 - 稳定性：稳定
--------------------- END ----------------------
「 作者 」 枫叶先生
「 更新 」 2024.1.9
「 声明 」 余之才疏学浅，故所撰文疏漏难免，
或有谬误或不准确之处，敬请读者批评指正。