993
插入法排序
所謂插入排序法，就是檢查第i個數字，如果在它的左邊的數字比它大，進行交換，這個動作一直繼續下去，直到這個數字的左邊數字比它還要小，就可以停止了。
假設我們輸入的是 “5，1，4，2，3” 我們從第二個數字開始，這個數字是1，我們的任務隻要看看1有沒有正確的位置，我們的做法是和這個數字左邊的數字來比，因此我們比較1和5，1比5小，所以我們就交換1和5，原來的排列就變成了“1，5，4，2，3 ”
接下來，我們看第3個數字有沒有在正確的位置。這個數字是4，它的左邊數字是5，4比5小，所以我們將4和5交換，排列變成了 “1，4，5，2，3 "我們必須繼續看4有沒有在正確的位置，4的左邊是1，1比4小，4就維持不動了。
/**********************************************************************
*功能描述：插入法排序
*輸入參數： 數組， 起始索引(0), 終止索引
*輸出參數： 排好序的數組
*返回值： void
*其它說明：
*修改記錄1： //修改曆史記錄，包括修改日期、版本號、修改人及修改內容等
*修改日期 版本號 修改人 修改內容
* --------------------------------------------------------------------------------------------------
* 20140716 V1.0 wuyq 創建
***********************************************************************/
void insertion_sort(int array[], int first, int last)
{
int i,j;
int temp;
for(i=first+1; i<=last; i++)
{
temp=array[i];
j=i-1;
//與已排序的數逐一比較，大於temp時，該數移後
while((j>=first)&&(array[j]>temp))
{
array[j+1]=array[j];
j--;
}
array[j+1]=temp;
}
}
/**********************************************************************
*功能描述：插入法排序
*輸入參數： 數組， 元素個數
*輸出參數： 排好序的數組
*返回值： void
*其它說明：
*修改記錄1： //修改曆史記錄，包括修改日期、版本號、修改人及修改內容等
*修改日期 版本號 修改人 修改內容
* --------------------------------------------------------------------------------------------------
* 20140716 V1.0 wuyq 創建
***********************************************************************/
void insert_sort(int* array, unsigned int n)
{
int i,j;
int temp;
for(i=1;i<n;i++)
{
temp=*(array+i);
for(j=i;j>0&&*(array+j-1)>temp;j--)
{
*(array+j)=*(array+j-1);
}
*(array+j)=temp;
}
}
#include <stdio.h>
int main()
{
int a[8] = {5, 6, 2, 7, 2, 0, 1, 4};
//insertion_sort(a, 0, 7);
insert_sort(a, 8);
int i;
for(i=0; i<8; i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
最後更新：2017-04-03 05:39:27