插入排序
入门对部分有序的数组效率很高，是小型数据集的实际首选。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void insertionSort(int arr[], int n) {
2 for (int i = 1; i < n; i++) {
3 int key = arr[i];
4 int j = i - 1;
5 while (j >= 0 && arr[j] > key) {
6 arr[j + 1] = arr[j];
7 j--;
8 }
9 arr[j + 1] = key;
10 }
11}
复杂度分析
时间 O(n²)
空间 O(1)
最优 O(n)
最坏 O(n²)
算法讲解
插入排序维护一个已排序的左半部分，逐个将右半部分的元素插入正确位置。
插入时需要将比待插入元素大的元素依次后移。
对于近乎有序的数组，时间复杂度接近 O(n)。
稳定排序，原地操作，适合小规模或部分有序的数据。