基本思想
設有n個數據，首先，數據位置序號模2相等的數進行排序，其次，數據位置序號各加1再模2相等的數進行排序，如此反覆，直到n次比較排序完成。
示例
初始關鍵字 [49 38 65 97 76 27 20 11]
第一趟排序後 [38 49][ 65 97] [27 76] [11 20]
第二趟排序後 38 [49 65][ 27 97][ 11 76] 20
第三趟排序後 [38 49][ 27 65][ 11 97][ 20 76]
第四趟排序後 38[ 27 49][ 11 65][ 20 97] 76
第五趟排序後 [27 38][ 11 49][ 20 65][ 76 97]
第六趟排序後 27[ 11 38][ 20 49][ 65 76 ]97
第七趟排序後 [11 27][ 20 38 ][49 65 ][76 97]
最後一趟排序後 11 [20 27][ 38 49][ 65 76] 97
代碼
C語言
數組排序
void PassSort( DataType a[ ], int n)
{
int i,j;
Boolean exchange; //交換標誌
DataType temp;
for(i=0;i<n;i++) //最多做n趟排序
{
exchange=FALSE; //本趟開始排序前,交換標誌應為假
for(j=i%2;j<n-1;j=j+2)
if(a[j].key>a[j+1].key)
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
exchange=TURE; //發生了交換,故將交換標誌置為真
}
if(! exchange) return; //本趟排序未發生交換,提前終止算法
}
}
示例測試程式如下:
#include<stdio.h>
typedef int KeyType;
typedef enum{FALSE,TURE} Boolean;
typedef struct
{
KeyType key;
}DataType;
void PassSort(DataType a[ ], int n)
{
//函式體同上，省略
}
void main(void)
{
DataType test[8]={ 49, 38, 65 ,97, 76, 27, 20, 11};
int i,n=8;
PassSort(test,n);
for(i=0;i<n;i++)
printf(“%d “,test[i].key);
}
傳遞排序算法的時間複雜度分為最好、最壞和隨機三種情況。
1. 最好情況是原始數據元素集合已全部排好序。這時，所需的關鍵字比較和記錄移動次數均分別達到最小值Cmin=n/2,Mmin=0,所以傳遞排序算法最好情況下的時間複雜度為o(n)。
2. 最壞情況是原始數據元素集合反序排列。這時，需要經過n趟排序，每趟排序要進行n/2次關鍵字比較，且每次比較必須移動記錄3次達到交換記錄位置。Cmax=n^2/2,Mmax=3*n^2/2所以傳遞排序算法最壞情況下的時間複雜度也為o(n^2)。
3. 如果原始數據元素集合中大小排列是隨機的，平均的情況分析稍為複雜，因為算法可能在某一趟排序完成後就終止，所以平均排序趟數為o(n),由此得出平均情況下總的比較次數仍是o(n^2)。
故算法平均複雜度為o(n^2)。
傳遞排序算法的空間複雜度為o(1)。顯然，傳遞排序是一種穩定的排序算法。
帶頭指針單鍊表傳遞排序
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct node{
int data;
struct node *next;
}*Linklist,Node;
Linklist creat(int n)
{
Linklist head,r,p;
int x,i;
head=(Node*)malloc(sizeof(Node));
r=head;
printf("輸入數字:\n");
for(i=n;i>0;i--)
{
scanf("%d",&x);
p=(Node*)malloc(sizeof(Node));
p->data=x;
r->next=p;
r=p;
}
r->next=NULL;
return head;
}
void output(Linklist head)
{
Linklist p;
p=head->next;
do{
printf("%3d",p->data);p=p->next;
}while(p);
printf("\n");
}
void passsort(Linklist head)
{
Linklist p,q;
int i,j,n,temp;
for(i=0;i<n;i++)
{
p=head->next;q=p->next;
j=i%2;
if(j!=0){p=q; q=q->next;}
while(p->next&&q->next)
{
if(p->data>q->data)
{
temp=p->data;
p->data=q->data;
q->data=temp;
}
p=q->next;
q=p->next;
}
if(p->next)
if(p->data>q->data)
{
temp=p->data;
p->data=q->data;
q->data=temp;
}
}
}
void main()
{
Linklist head;
int n;
printf("輸入數字的個數(n):\n");
scanf("%d",&n);
head=creat(n);
printf("輸出數字:\n");
output(head);
passsort(head);
printf("已排序的數字:\n");
output(head);
}
