插入排序

工作方式

:::info 🚛 正如上图所示，插入排序的工作方式就如打扑克时抓牌。首先左手是空的，然后右手抓牌后从右向左依次 和左手中的牌进行比较后插入到正确的位置。 :::

代码实现

void insertSearch(int arr[], int len)
{
  for (int j = 1; j < len; j++)
  {
    int i = j - 1;
    int temp = arr[j];
    while (i >= 0 && arr[i] > temp)
    {
      arr[i + 1] = arr[i];
      i--;
    }
    arr[i + 1] = temp;
  }
}

• 数组中下标j的数代表右手抓的牌
• 通过while循环依次与Arr[0, … , j - 1]的数比较，直到i<0或者arr[i] >
• 每次for循环时Arr[0, …, j-1]都为有序数组。

复杂度分析

时间复杂度

:::danger ✅ 最好的情况是每次抓到的牌都比已排好序的最右边的牌大，时间复杂为o(n)。
❌ 最差的情况是按照逆序抓牌，时间复杂度为(n - 1) + (n - 2) + … + 1 = n * (n - 1) / 2，为o(n^2)。 :::

空间复杂度

:::success ✅ 没有用到额外的空间，空间复杂度为o(1) :::

相关资料

<算法导论（第三版）>