跳转至

直接插入排序

思想：将序列分为有序和无序两部分，之后不断将后面的无序元素插入到前面的有序序列中。

一开始，第一个元素自己构成有序序列，剩下的元素都在无序序列中。

分析

  • 平均时间复杂度：\(O(n^2)\)。
  • 最好时间复杂度（正序情况）：\(O(n)\)。
  • 最坏时间复杂度（逆序情况）：\(O(n^2)\)。
  • 空间复杂度：\(O(1)\)。
  • 稳定的排序算法。

模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#define MAX_N 1000000

int N;
int nums[MAX_N];

void insertionSort()
{
    for (int i = 1;i < N;i++)
    {
        int temp = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > temp)
        {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = temp;
    }
}