1.排序的概念及分类
排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作
常见的排序算法可以按如图所示分类。
以下所有的排序算法均以升序的方式实现。
2.插入排序
2.1 直接插入排序（InsertSort）
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
简单来说，平常玩的扑克牌游戏就是一种插入排序。
排序原理：
当插入第 i ( i >= 1 ) 个元素时，前面的 array[0] ，array[1] ，… ，array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i - 1] ，array[i - 2] ，… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。
💻排序实现：
void InsertSort(int* a, int n) {
for (int i = 1; i < n; ++i) {
int end = i - 1;
int tmp = a[i];
while (end >= 0) {
if (tmp < a[end]) {
a[end + 1] = a[end];
--end;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
⌨️代码解读：
- 第一个
for循环指的是从第一个数开始依次往后遍历，end指向已排序部分的最后一个元素（即开始的a[0]），tmp = a[i]提前保存该位置的数据，避免移动时的覆盖消除该数据。 - 从后往前遍历已排序部分，找到合适的插入位置，如果当前要插入的元素小于已排序部分的元素，将已排序部分的元素后移一位，
--end继续向前比较；如果找到合适的插入位置，break退出循环。 - 找到合适位置后，
a[end + 1] = tmp将当前要插入的元素插入到合适的位置。
🖱️复杂度分析：
• 时间复杂度：
○ **最好情况：**数组已经是有序的，此时内层的 while 循环每次只需要比较一次就会退出，时间复杂度为 O(n)。
○ **最坏情况：**数组是逆序的，内层的 循环每次都需要比较到已排序部分的第一个元素，时间复杂度为 。
