傳遞排序

傳遞排序是一種計算機科學領域的較簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。是一種類似冒泡排序的排序算法。

基本介紹

• 中文名：傳遞排序
• 外文名：Pass sort
• 性質：排序算法
• 用途：快速定位指定索引的元素
• 性質：現象

基本思想

設有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);
}