直接插入排序(InsertSort)

每次插入一个新的待排序数到已排序序列中，注意此时从后往前比较，更节省时间。

举例

原始序列： 49, 38, 65, 13, 27

1. 一开始只看49,则单个数字肯定是有序的

{49} / 38, 65, 13, 27

2. 此时插入38， 由于38<45， 故45向后移动， 38插入到49原来的位置

{38, 49} / 65, 13, 27

3. 此时插入65, 从后向前进行比较，49<65， 故65直接插入到49之后

{38, 49, 65} / 13, 27

4. 此时插入13，从后向前进行比较，一直到38>13，这趟排序后的结果为：

{13, 38, 49, 65} / 27

5. 此时插入27，从后向前进行比较，发现该插入到13之后，38之前

{13, 27, 38, 49, 65}

代码：

#include <iostream>
using namespace std;

void InsertSort(int array[], int n) {
  int i, j, temp;
  for (i = 1; i < n; ++i) {
    temp = array[i];
    j = i - 1;
    while (j >= 0 && temp < array[j]) {
      array[j+1] = array[j];
      --j;
    }
    array[j+1] = temp;
  }
}

void print_array(int array[], int n) {
  for (int i = 0; i < n; ++i)
    cout<<array[i]<<" ";
  cout<<endl;
}

int main() {
  int array[] = {49, 38, 65, 13, 27};
  print_array(array, 5);
  InsertSort(array, 5);
  print_array(array, 5);

  return 0;
}

复杂度分析

1. 时间复杂度：
最坏情况，整个原始序列是逆序的，则内层循环temp<array[i]每次都成立，则时间复杂度为O(n^2).
最好情况，整个原始序列原本就是按序排列的，则内存循环条件不满足，时间复杂度为O(n).
综合来看，时间复杂度为O(N^2).

2. 空间复杂度：
只需要一个temp，并不随着待排序列的规模而变化，因此空间复杂度为O(1).