4.插入排序
4.1 基础知识
核心思想
每一轮将未排序区的元素插入已排序区的合适位置，不断扩大已排序区域，缩小未排序区域，直到完成排序。
算法步骤
初始状态：
- 将整个数组分为已排序区和未排序区，初始时已排序区只包含第一个元素，未排序区为剩余的元素。
每一轮插入元素：
- 从未排序区选择第一个元素，将其插入已排序区的合适位置。插入时，从已排序区的末尾开始比较，依次向前找到合适的位置。
更新已排序区和未排序区：
- 将已排序区的范围扩大，未排序区的范围缩小。已排序区的末尾即为刚刚插入的元素的位置。
重复直至排序完成：
- 重复上述步骤，直至未排序区为空。每一轮插入操作都会将未排序区的一个元素插入到已排序区，最终完成整个数组的排序。
时间复杂度
插入排序的最坏情况下的时间复杂度为O(n^2)，平均和最好情况下为O(n)。在已排序或近乎已排序的情况下，插入排序的性能较好。
空间复杂度
插入排序是一种原地排序算法，空间复杂度为O(1)。
稳定性
插入排序是稳定的。相同元素的相对顺序在排序前后不会改变。
适用场景
插入排序适用于小规模数据或基本有序的数据集。由于其简单且稳定的特性，插入排序在实际应用中常被用于对已近乎有序的数据进行排序，或者作为其他高级排序算法的一部分。
代码步骤
外层循环：
- 通过外层循环，控制待插入的元素的索引。从第二个元素开始（索引为1），因为第一个元素被认为已经是有序的。
当前待插入元素：
- 在每一轮开始时，将当前待插入的元素记录为 currentElement。
内层循环找插入位置：
- 通过内层循环，在已排序区域中寻找合适的插入位置。从已排序区的末尾开始，比较已排序区的元素与 currentElement 的大小，如果已排序区的元素较大，就将该元素向后移动一个位置。
插入当前元素：
- 在找到合适的插入位置后，将 currentElement 插入到已排序区域的正确位置。这是通过在内层循环结束后，将 currentElement 赋值给 array[j + 1] 实现的，其中 j + 1 是 currentElement 应该插入的位置。
输出插入后的数组：
- 在每次插入后，输出当前数组的状态，显示排序的过程。
重复直到完成：
- 通过不断重复上述步骤，直到整个数组完全有序。每一轮都会将当前待插入的元素插入到已排序区域的正确位置。
总结说明
尽管插入排序的最坏情况时间复杂度较高，但在某些场景下，由于其稳定性和对部分有序数据的高效处理，它仍然是一个实用的排序算法。在面对小规模数据或已基本有序的数据时，插入排序可以是一个简单而有效的选择。然而，对于大规模数据集，其他高效的排序算法可能更为合适。
4.2 思路框架
static void InsertionSort(ref int[] array)
{
循环：从数组的第二个元素开始，因为第一个元素默认已排序
{
将当前元素值保存到临时变量中
定义指针，用于比较当前元素和已排序部分的元素，初始值是排序区末尾元素索引
循环：将当前元素与排序区元素逐个比较并移动，只要没越界且当前元素值比排序区的小就一直移动
{
覆盖当前指正后一元素值且指针往前移
}
出循环代表找到合适的插入位置，将当前元素值覆盖到指正后一元素中
}
}
require("Lesson01_SortHelpTool")
-- 插入排序函数
function InsertionSort(array)
for i = 2, #array do
local currentElement = array[i]
local j = i - 1
while j >= 1 and array[j] > currentElement do
array[j + 1] = array[j]
j = j - 1
end
array[j + 1] = currentElement
end
end
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序前")
InsertionSort(SortHelpTool.arrayToSort)
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序后")
4.3 纯净代码
static void InsertionSort(ref int[] array)
{
for (int i = 1; i < array.Length; i++)
{
int currentElement = array[i];
int j = i - 1;
while (j >= 0 && array[j] > currentElement)
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = currentElement;
}
}
4.4 带注释代码
using System;
using Lesson01_概述;
class Program
{
static void Main()
{
// 输出排序前的数组
Console.WriteLine("排序前的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
// 调用插入排序函数
InsertionSort(ref SortHelpTool.arrayToSort);
// 输出排序后的数组
Console.WriteLine("排序后的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
}
// 插入排序函数
static void InsertionSort(ref int[] array)
{
// 从1开始，默认第一个数已经排序，代表取出来的未排序区的第一个元素，数组有多长，就有多少-1轮的插入操作
for (int i = 1; i < array.Length; i++)
{
// 当前待插入元素
int currentElement = array[i];
// i - 1代表从已排序区的末尾开始比较
int j = i - 1;
// 在已排序区寻找插入位置，只要未到已排序区头，且当前比较的已排序区元素大于当前待排序元素，就继续往前移动比较，找到合适位置的插入
while (j >= 0 && array[j] > currentElement)
{
// 移动元素，为当前元素腾出插入位置
array[j + 1] = array[j];
// 继续往前移动比较
j--;
}
// 插入当前元素到正确位置，j+1是因为while中将已经将比currentElement大的元素都向后移动了一个位置并让j--继续往前进行比较，所以插入位置就是j+1。
array[j + 1] = currentElement;
// 输出排序中的数组
Console.WriteLine($"第{i}轮 插入元素{currentElement}到正确位置 插入后的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
}
}
}
4.5 运行结果
排序前的数组:
5 2 8 1 7 3 10 4 6 9
第1轮 插入元素2到正确位置 插入后的数组:
2 5 8 1 7 3 10 4 6 9
第2轮 插入元素8到正确位置 插入后的数组:
2 5 8 1 7 3 10 4 6 9
第3轮 插入元素1到正确位置 插入后的数组:
1 2 5 8 7 3 10 4 6 9
第4轮 插入元素7到正确位置 插入后的数组:
1 2 5 7 8 3 10 4 6 9
第5轮 插入元素3到正确位置 插入后的数组:
1 2 3 5 7 8 10 4 6 9
第6轮 插入元素10到正确位置 插入后的数组:
1 2 3 5 7 8 10 4 6 9
第7轮 插入元素4到正确位置 插入后的数组:
1 2 3 4 5 7 8 10 6 9
第8轮 插入元素6到正确位置 插入后的数组:
1 2 3 4 5 6 7 8 10 9
第9轮 插入元素9到正确位置 插入后的数组:
1 2 3 4 5 6 7 8 9 10
排序后的数组:
1 2 3 4 5 6 7 8 9 10
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
