插入排序[O(n^2),稳定],不断插入到有序序列。

#include <stdio.h>

void printArray(int *a, int n)
{
for(int i=0;i<n;i++) {
printf("%d ", a[i]);
}
printf("\n");
}

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

int main()
{
int a[] = {5,1,7,3,1,6,9,4};
printArray(a, 8);
insertSort(a, 8);
printArray(a, 8);
}