雙向排序算法是眾多插入算法中的一種，是插入算法的最佳化版。
由於是插入排序中的一種所以不能使用數組作為數據結構，故使用鍊表作為數據結構。
基本介紹
- 中文名：Clover排序算法
- 別名：雙向排序算法
- 最壞時間複雜度是：O（n^2/2）
雙向插入排序算法
該算法的最佳時間複雜度是：O(n)
視覺感受排序過程
Clover排序算法
空間複雜度：O（3n）
礙於其他原因我並未進行複雜度測試，以上只是理論複雜度。
算法剖析:
從大到小排序（也可以舉一反三，寫出從小到大的排序）：
該算法的所有動作均取決於一個數字，也就是平均數。
順序處理數據，先取當前處理數字出來和平均數比對，如果比平均數大或者等於平均數則再次判斷是否比最左邊的數字大，或者等於最左邊的數字，如果是的話則將當前處理的數字放到數據的最左邊如果否就從最左邊到最右邊尋找一個比當前處理數大的數字，並且插入到它的後面；如果當前處理數小於平均數，就判斷是否等於或者小於最左邊的數如果成立則把當前處理數放到最右邊，如果不成立則按照剛才提及的方法從左向右尋找可以存放該數的位置，並插入；最後還原平均數，計算當前平均數；便完成了一個處理周期，用上述方法依次處理所有數據。
#include<stdio.h>
int l;
int pjs(float on_num,int num_nb,int add_num)
{
return (on_num*(num_nb-1)+add_num)/num_nb; //qioupingjunshu
}
int cloverpx(int a[10000][3],int b[10000],int n,char left_or_right[10])
{
int j,deal=0,head=0,till=0,k;
float PJS=b[0];
a[0][0]=b[0]; //begin
a[0][1]=-1;
a[0][2]=-1;
if(left_or_right=="left") //left=(big->small)right=(small->big)
for(j=1;j<n;j++)
if(b[j]>PJS)
{
if(b[j]>=a[head][0])
{//1thinghead
deal++;
a[deal][0]=b[j];
a[deal][1]=head;
a[deal][2]=-1;
a[head][2]=deal;
head=deal;
PJS=pjs(PJS,deal,b[j]);
}
else
{
k=head; //2thing head
while(a[k][0]>b[j])k=a[k][1];//virtual(lookforreal)
deal++;
a[deal][2]=a[k][2];
a[a[k][2]][1]=deal;
a[k][2]=deal;
a[deal][1]=k;
a[deal][0]=b[j];
PJS=pjs(PJS,deal,b[j]);
}
}
else
{
if(b[j]<=a[till][0])
{//1thing till
deal++;
a[deal][0]=b[j];
a[deal][1]=-1;
a[deal][2]=till;
a[till][1]=deal;
till=deal;
PJS=pjs(PJS,deal,b[j]);
}
else
{
k=till; //2thing till
while(a[k][0]<b[j])k=a[k][2];//virtual(lookforreal)
deal++;
a[deal][1]=a[k][1];
a[deal][2]=k;
a[a[k][1]][2]=deal;
a[k][1]=deal;
a[deal][0]=b[j];
PJS=pjs(PJS,deal,b[j]);
}
}
l=head;
return 0;
}
int main()
{
FILE *input,*output;
input=fopen("clover1","r");
int all_num_nb,i,data_2[10000][3],data_1[10000];
fscanf(input,"%d",&all_num_nb);
for(i=0;i<all_num_nb;i++)
fscanf(input,"%d",&data_1[i]);
cloverpx(data_2,data_1,all_num_nb,"left");
output=fopen("clover2","w");
while(data_2[l][1]!=-1)
{
fprintf(output,"%d",data_2[l][0]);
l=data_2[l][1];
}
fprintf(output,"%d",data_2[l][0]);
return 0;
}
