插入排序（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)