插入排序（C語言版）

前言

插入排序(insertion sort)的基本思想：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排序好的序列中，直到全部記錄插入完成為止.

直接插入排序

基本思想

假設待排序的記錄存放在數組R[1..n]中。初始時，R[1]自成1個有序區，無序區為R[2..n].從i = 2起直到i = n 為止，依次將R[i]插入當前的有序區R[1..i - 1]中，生成含n個記錄的有序區.

排序方法

將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i - 1, i - 2, ....,1)的關鍵字比較：

1. 若R[j]的關鍵字大於R[i]的關鍵字，則將R[j]後移一個位置
2. 若R[j]的關鍵字小於或等於R[i]的關鍵字，則查找過程結束，j + 1即為R[i]插入位置

關鍵字比R[i]的關鍵字大的記錄均已後移，所以j + 1的位置已經騰空，只要將R[i]直接插入到此位置即可完成一趟直接插入排序

c語言實現代碼

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

void insertSort(int *, int);

int main()
{
 int i, n;
 int num[10];

 while(scanf("%d", &n) != EOF)
 {
  //接收無序數據
  for(i = 0; i < n; i ++)
  {
   scanf("%d",num + i);
  }

  //快速排序
  insertSort(num, n);

  //打印輸出
  for(i = 0; i < n; i ++)
  {
   printf("%d ",num[i]);
  }
  printf("\n");
 }
 return 0;
}

void insertSort(int *array, int len)
{
 int i, j, temp;

 for(i = 1; i < len; i ++)
 {
  temp = array[i];
  for(j = i - 1; j >= 0; j --)
  {
   if(array[j] > temp)
   {
    array[j + 1] = array[j]; 
   }else
   {
    break;
   }
  }
  array[j + 1] = temp;
 }
}

時間復雜度
當數組和要求排序的順序相同時，為o(n)
當數組和要求排序的順序相反時，為o(n * n)
平均時間復雜度為o(n * n)