简述直接插入排序的原理 ？
参考答案：
直接插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体来说，其原理可以分为以下几个步骤：
初始化：假设待排序的数组为
arr，其长度为n。从数组的第二个元素（索引为1）开始，认为该元素之前的序列（即索引为0的元素）是已经排序好的。插入过程：取出下一个待排序的元素（当前为
arr[i]，其中i从1开始递增），在已经排序的序列中从后向前扫描。比较与移动：如果已排序的元素（
arr[j]）大于新元素（arr[i]），则将该元素移到下一位置（即arr[j+1]）。重复此步骤，直到找到已排序的元素小于或等于新元素的位置。插入新元素：找到位置后，将新元素插入到该位置。
重复：对剩余未排序的元素重复上述步骤，直到整个数组排序完成。
举个例子，假设有一个数组 arr = [4, 3, 2, 10, 12, 1, 5, 6]，其排序过程如下：
- 初始时，认为
[4]是已排序的。 - 取出
3，将其插入到[4]的前面，得到[3, 4]。 - 取出
2，将其插入到[3, 4]的前面，得到[2, 3, 4]。 - 以此类推，直到整个数组排序完成。
直接插入排序的时间复杂度在最坏情况下是 O(n^2)，其中 n 是数组的长度。当输入数组已经有序时，其时间复杂度最好情况为 O(n)。平均时间复杂度也为 O(n^2)。尽管它的时间复杂度相对较高，但由于其实现简单且在某些特定情况下（如部分有序数组）表现良好，因此在某些场合仍被使用。