插入排序

#插入排序

  • 太简单不想说

    • #折半查找

  • 关键就在于每波前面已经排好序的元素使用折半查找直接找到插入位置，然后插入元素并移动后继元素。

    • #时间复杂度

  • 最坏O(n^2)
  • 平均O(n^2)
  • 最好O(n)

    • #代码实现

    //插入排序

    void insertSort(int arr[], int num)

    {

    int i = 0, j = 0, temp = 0;

    for (i = 1; i < num; i++)

    {

    if (arr[i] < arr[i - 1])

    {

    temp=arr[i];

    for (int j = i - 1; arr[j]>temp;j--)

    {

    arr[j+1] = arr[j];

    }

    arr[j+1] = temp;

    }

    }

    }