直接插入排序
算法思想:把n個待排序的元素看成為一個有序表和一個無序表,開始時有序表中只包含一個元
素,無序表中包含有n-1個元素,排序過程中每次從無序表中取出第一個元素,將它
插入到有序表中的適當(dāng)位置,使之成為新的有序表,重復(fù)n-1次可完成排序過程。
時間復(fù)雜度 o(n^2)
空間復(fù)雜度 o(1)
比較次數(shù) n(n+1)/2
*/
void insert_sort(int array[],int len)
{
int tmp,i,j;
for(i = 1;i < len;i++)
{
if (array[i] < array[i-1])
{
tmp = array[i];
array[i] = array[i-1];
//插入到相應(yīng)位置
for (j = i-2;j >= 0;j--)
{
//往后移
if (array[j] > tmp)
array[j+1] =array[j];
else
{
array[j+1] = tmp;
break;
}
}
if(j == -1)
array[j+1] = tmp;
}
}
}
/*
相關(guān)推薦:
軟考程序員考試歷年真題重點題總結(jié)及答案
2011年上半年軟考報名時間及方式匯總
軟考程序員考試歷年真題匯總(2007年-2010年)