直接插入排序

直接插入排序

#include <iostream>
using namespace std;

#define N 10

void StraightInsertion(int *a, int n)
{
  int i, t;
  for (i = 1; i < n; i++)
  {
    t = a[i];
    while (t < a[i - 1] && i)
    {
      a[i] = a[i - 1];
      i--;
    }
    a[i] = t;
  }
}

int main()
{
  int i;
  int *a = new int[N];

  for (i = 0; i < N; i++)
  {
    cin >> a[i];
  }

  StraightInsertion(a, N);

  for (i = 0; i < N; i++)
  {
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}

• 时间复杂度： 最好的情况是 O(n) 只需要扫一遍，最坏的情况是 O(pow(n,2))

测试

[blazehu@MacBook ~]$ g++ -o StraightInsertion StraightInsertion.cpp
[blazehu@MacBook ~]$ ./StraightInsertion
1
4
3
2
5
6
7
9
8
0
0 1 2 3 4 5 6 7 8 9