//时间复杂度为O(n^2), 比较和移动次数的期望值约为(n^2)/4


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define ARRAY_SIZE 10

void insertSort(int sortArray[], int size)
{
  int i, j, temp;
  for(i=1;i<size;i++)
    if(sortArray[i]<sortArray[i-1])
    {
      temp = sortArray[i];
      for(j=i-1; j>=0 && sortArray[j]>temp; j--)
        sortArray[j+1] = sortArray[j];
      sortArray[j+1] = temp;
    }
}

int main()
{
  int sortArray[ARRAY_SIZE]={30, 29, 45, 33, 21, 3, 108, 75, 99, 66};
  int i;
  insertSort(sortArray, 10);
  for(i=0;i<10;i++)
    printf("%d ", sortArray[i]);
  printf("\n");
}