[演算法] 插入排序法
插入排序法，是一個依序將值插入到判斷完成的答案中，直到完成為止，因此稱為插入排序法(Insert Sort)。
例：
２ １２ ８ ７ ３９ １
插入排序：
[第一次]
２ １２ ８ ７ ３９ １ ( 和2比較，取得12的位置在第二格 )
２ １２ ８ ７ ３９ １ ( 和2~12比較，取得8的位置在第二格 )
２ ８ １２ ７ ３９ １ ( 和2~12比較，取得7的位置在第二格 )
２ ７ ８ １２ ３９ １ ( 和2~12比較，取得39的位置在第五格 )
２ ７ ８ １２ ３９ １ ( 和2~39較，取得1的位置在第一格 )
１ ２ ７ ８ １２ ３９ ( 結果 )
但其實在實作時，會浪費許多時間在位移的時間。
程式範例（ Linux C ）：
#include
/*************************************************************************/
#include
#include
#include
#include
/*! \struct Leo_Insert
* \brief Leo_Insert function,IN: InputData Input_Number,OUT: None
* \details Leo_Insert function \n
* \author Leo Cheng
*/
/*************************************************************************/
int Leo_Insert(int*
InputData,int
Input_Number)
{
int i,j,k;
int
AnswerNumber[Input_Number];
//---Init---//
for( i=0
; i
{
AnswerNumber[i] = *(InputData + i);
}
//---Start Insert---//
for( i=1
; i
{
for( j=0
; j
{
if(j >= i)
{
AnswerNumber[j] = *(InputData+i);
}
else
{
if(*(InputData+i)
{
for( k=i
; k > j ; k-- )
{
AnswerNumber[k] = AnswerNumber[k - 1];
}
AnswerNumber[j] = *(InputData+i);
break;
}
}
}
}
//---Show InputData---//
for( k=0
; k
{
printf("%2d ",*(InputData+k));
}
printf("\n");
//---Show Answer---//
for( k=0
; k
{
printf("%2d ",*(AnswerNumber+k));
}
printf("\n");
}
/*************************************************************************/
/*! \struct main
* \brief main function,IN: None,OUT: None
* \details main function \n
* \author Leo Cheng
*/
/*************************************************************************/
void main()
{
int Input_Number = 10;
int
InputData[Input_Number];
int i;
srand(time(NULL));
for( i=0 ; i
{
InputData[i]=(rand()%100)+1;
}
Leo_Insert(InputData,Input_Number);
}
改良插入排序法
在我實作的方法中，每次新值要判斷插入的數值都是目前已經判斷值的數目，如
２ ７ ８ １２ ３９ １
３９要插入２～１２之間，則最大要判斷的數目為４個數字。
[方法一]
因此，第一個可以改良了地方，就是改變起頭或結束的位置，比如
２ ７ ．．．１４ ２２ ３２．．． ５５ ６３ X １ ３
上次插入的數字是２２，目前要插入數字是X，先判斷 現在數字是否大於／小於／等於上次數字，
１、如果大於上次數字，代表上次數字（如２２的位置）插入的位置之前的數字 （如２的位置～１４的位置）都可以不用判斷，因此開始位置就可以從第一位（如２的位置）變成 上次位置+1（如３２的位置）
３２．．． ５５ ６３ X １ ３
２、如果小於上次數字，代表上次數字（如２２的位置）插入的位置之後的數字 （如３２的位置～６３的位置）都可以不用判斷，因此結束位置就可以從最後一位（如６３的位置）變成 上次位置-1（如１４的位置）
２ ７ ．．．１４ X １ ３
３、如果與上次位置相同，則直接插入位置就是上次位置
[方法二]
第二個可以改良的地方，是再進一步縮減頭尾位置，在上面縮減的判斷中，只能有效的改變頭尾其中一項，比如當大於上次數字（方法一第１）時，是改變開始位置到 上次位置+1（如３２的位置），但結果位置依舊在最後一位（如６３的位置）
因此在這個情況下，再加上縮短結束位置的方法
假設結束位置 =（（ 最後一位位置 - 上次位置 ）/ ２） + 上次位置
３２．．． ５５ ６３ X １ ３
代入實際數字，假設３２的位置是１０，６３的位置是２３，則假設結束位置為（（２３－１０）/２）＋１０ ＝ １６
意思也就是在原本要判斷的數字列中，再取一個數字來判斷（在此時利用二個位置的中心位置），來判斷１６位置的數字是否大於X
１、假設結束位置的數字大於X，則結束位置從最後一位（如６３的位置）變成假設結束位置（比如從位置２３變成位置１６
在這個例子來看，原本要從判斷最大數（２３－１０）＝１３個數字，變成了只需判斷（１６－１３）＝３個數字
２、當然如果假設結束位置的數字小於X，則開始位置變成假設結束位置，而結束位置依舊在最後一位（如６３的位置）
當然，在方法一第２的情況下也要做相對應的判斷。
部份程式範例（ Linux C ）：（改良修改程式為粗體字）
/*************************************************************************/ ... 實測排列25萬筆資料時，在原方法需花費1分55秒左右 real 1m55.469s 而加入頭尾縮減的方法後，25萬筆資料只需花費1分12秒左右 real 1m12.047s
...
/*! \struct Leo_InsertWithCompare
* \brief Leo_InsertWithCompare function,IN: InputData
Input_Number,OUT: None
* \details Leo_InsertWithCompare function \n
* \author Leo Cheng
*/
/*************************************************************************/
int Leo_InsertWithCompare(int*
InputData,int Input_Number)
{
int i,j,k;
int AnswerNumber[Input_Number];
int StartPlace=0,EndPlace=0,GetLastPalce=0,ReducePlace=0;
//---Init---//
for( i=0 ; i
{
AnswerNumber[i] = *(InputData + i);
}
//---Start Insert---//
for( i=1 ; i
{
//---Get Compare---//
if(i >= 2)
{
if(*(InputData+i) > *(InputData+i-1))
{
StartPlace = GetLastPalce;
ReducePlace = ((i-GetLastPalce)/2)+GetLastPalce;
if(AnswerNumber[ReducePlace] > *(InputData+i))
{
EndPlace = ReducePlace;
}
else if(AnswerNumber[ReducePlace]
{
StartPlace = ReducePlace;
EndPlace = i;
}
else
{
EndPlace = i;
}
}
else if(*(InputData+i) ==
*(InputData+i-1))
{
StartPlace = GetLastPalce;
EndPlace = i;
}
else
{
EndPlace = GetLastPalce;
ReducePlace = GetLastPalce/2;
if(AnswerNumber[ReducePlace]
{
StartPlace = ReducePlace;
}
else if(AnswerNumber[ReducePlace] > *(InputData+i))
{
StartPlace = 0;
EndPlace = ReducePlace;
}
else
{
StartPlace = 0;
}
}
}
else
{
StartPlace = 0;
EndPlace = i;
}
for( j=StartPlace ; j
{
if(j >= i)
{
AnswerNumber[j] = *(InputData+i);
GetLastPalce = j;
}
else
{
if(*(InputData+i)
{
for( k=i ; k > j ; k-- )
{
AnswerNumber[k] = AnswerNumber[k - 1];
}
AnswerNumber[j] = *(InputData+i);
GetLastPalce = j;
break;
}
}
}
}
//---Show InputData---//
for( k=0 ; k
{
printf("%2d ",*(InputData+k));
}
printf("\n");
//---Show Answer---//
for( k=0 ; k
{
printf("%2d ",*(AnswerNumber+k));
}
printf("\n");
}
user 1m55.061s
sys 0m0.015s
user 1m11.686s
sys 0m0.015s
PS：另外如果直接使用二分法頭尾縮減到只剩判斷3個數字，25萬筆資料需花費0分55秒左右
留言列表
