第九章 查找第十章 內部排序
void Insert_Sort
{
k=L
for(i=k
if(L
{
L
for(j=i+
L
L
}
}//Insert_Sort
void BiInsert_Sort(SqList &L)//二路插入排序的算法
{
int d[MAXSIZE]; //輔助存儲
x=L
first=
for(i=
{
if(L
{
for(j=final;d[j]>L
d[j+
d[j+
final++;
}
else //插入後部
{
for(j=first;d[j] d[j-1]=d[j]; d[(j-2)%MAXSIZE+1]=L.r[i].key; first=(first-2)%MAXSIZE+1; //這種形式的表達式是為了兼顧first=1的情況 } }//for for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//將序列復制回去 L.r[j].key=d[i]; }//BiInsert_Sort 10.25 void SLInsert_Sort(SLList &L)//靜態鏈表的插入排序算法 { L.r[0].key=0;L.r[0].next=1; L.r[1].next=0; //建初始循環鏈表 for(i=2;i<=L.length;i++) //逐個插入 { p=0;x=L.r[i].key; while(L.r[L.r[p].next].key p=L.r[p].next; q=L.r[p].next; L.r[p].next=i; L.r[i].next=q; }//for p=L.r[0].next; for(i=1;i { while(p q=L.r[p].next; if(p!=i) { L.r[p]<->L.r[i]; L.r[i].next=p; } p=q; }//for }//SLInsert_Sort 10.26 void Bubble_Sort1(int a[ ],int n)//對包含n個元素的數組a進行改進的冒泡排序 { change=n-1; //change指示上一趟冒泡中最後發生交換的元素 while(change) { for(c=0,i=0;i if(a[i]>a[i+1]) { a[i]<->a[i+1]; c=i+1; //c指示這一趟冒泡中發生交換的元素 } change=c; }//while }//Bubble_Sort1 10.27 void Bubble_Sort2(int a[ ],int n)//相鄰兩趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1; while(low { change=0; for(i=low;i if(a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } high--; //修改上界 for(i=high;i>low;i--) //從下向上起泡 if(a[i]
{ a[i]<->a[i-1]; change=1; } low++; //修改下界 }//while }//Bubble_Sort2 10.28 void Bubble_Sort3(int a[ ],int n)//對上一題的算法進行化簡,循環體中只包含一次冒泡 { int b[ 3 ]; //b[0]為冒泡的下界,b[ 2 ]為上界,b[1]無用 d=1;b[0]=0;b[ 2 ]=n-1; //d為冒泡方向的標識,1為向上,-1為向下 change=1; while(b[0] { change=0; for(i=b[1-d];i!=b[1+d];i+=d) //統一的冒泡算法 if((a[i]-a[i+d])*d>0) //注意這個交換條件 { a[i]<->a[i+d]; change=1; } b[1+d]-=d; //修改邊界 d*=-1; //換個方向 }//while }//Bubble_Sort3 10.29 void OE_Sort(int a[ ],int n)//奇偶交換排序的算法 { change=1; while(change) { change=0; for(i=1;i if(a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } for(i=0;i if(a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } }//while }//OE_Sort 分析:本算法的結束條件是連續兩趟比較無交換發生 10.30 typedef struct { int low; int high; } boundary; //子序列的上下界類型 void QSort_NotRecurve(int SQList &L)//快速排序的非遞歸算法 { low=1;high=L.length; InitStack(S); //S的元素為boundary類型 while(low { if(high-low>2) //如果當前子序列長度大於3且尚未排好序 { pivot=Partition(L,low,high); //進行一趟劃分 if(high-pivot>pivot-low) { Push(S,{pivot+1,high}); //把長的子序列邊界入棧 high=pivot-1; //短的子序列留待下次排序 } else { Push(S,{low,pivot-1}); low=pivot+1; } }//if else if(low { Easy_Sort(L,low,high); //直接進行比較排序 low=high; //當前子序列標志為已排好序 } else //如果當前子序列已排好序但棧中還有未排序的子序列 { Pop(S,a); //從棧中取出一個子序列 low=a.low; high=a.high; } }//while }//QSort_NotRecurve int Partition(SQList &L,int low,int high)//一趟劃分的算法,與書上相同 { L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low { while(low high--; L.r[low]=L.r[high]; while(low low++; L.r[high]=L.r[low]; }//while L.r[low]=L.r[0]; return low; }//Partition void Easy_Sort(SQList &L,int low,int high)//對長度小於3的子序列進行比較排序 { if(high-low==1) //子序列只含兩個元素 if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high]; else //子序列含有三個元素 { if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high]; if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1]; } }//Easy_Sort 10.31 void Divide(int a[ ],int n)//把數組a中所有值為負的記錄調到非負的記錄之前 { low=0;high=n-1; while(low { while(low a[low]<->a[high]; while(low a[low]<->a[high]; } }//Divide 10.32 typedef enum {RED,WHITE,BLUE} color; //三種顏色 void Flag_Arrange(color a[ ],int n)//把由三種顏色組成的序列重排為按照紅,白,藍的順序排列 { i=0;j=0;k=n-1; while(j<=k) switch(a[j]) { case RED: a[i]<->a[j]; i++; j++; break; case WHITE: j++; break; case BLUE: a[j]<->a[k]; k--; //這裡沒有j++;語句是為了防止交換後a[j]仍為藍色的情況 } }//Flag_Arrange 分析:這個算法
From:http://tw.wingwit.com/Article/program/sjjg/201311/23549.html