插入排序--C語言

插入排序，一般也被稱爲直接插入排序。對於少量元素的排序，它是一個有效的演算法。插入排序的工作方式像許多人排序一手撲克牌，是指在待排序的元素中，假設前面n-1(其中n>=2)個數已經是排好順序的，現將第n個數插到前面已經排好的序列中，然後找到合適自己的位置，使得插入第n個數的這個序列也是排好順序的。
利用C語言寫的插入排序的演算法如下：
平均時間複雜度爲O(NN)，最壞時間複雜度爲O(NN)，穩定性爲穩定；

#include <stdio.h>

void Insertion_sort(int a[],int N)
{
	int p,i; 
	int Tmp;//儲存第二個數 
	for ( p = 1;p < N;p++)//從第二個數逐漸比較插入 
	{
		Tmp = a[p];//儲存第二個數 
		for(i = p;i > 0 && a[i-1] >Tmp;i--)//將tmp與前面的每一個數做比較 
		{
			a[i] = a[i-1];//將tmp的a[i]位置讓出來給a[i-1] 
		}
		a[i] = Tmp;//i的位置就是i-1前面空出來的位置 
	}
}
int  main(void)
{
	int i;
	int a[6] = {34,8,64,51,32,21};
	Insertion_sort(a,6);
	for(i= 0;i<6;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}