簡單排序算法

簡單排序算法

開始

五個整數(shù)排序

?設(shè)有五個整數(shù)需要進行排序

算法：五個整數(shù)排序

BEGIN

inputa,b,c,d,e;/*輸入五個整數(shù)*/

算法：三個整數(shù)排序ifa<bthen交換a和b的值；

BEGINifa<cthen交換2和（:的值；

inputa,b,c;/*輸入三個整數(shù)*/ifa<dthen交換a和d的值;

ifa<bthen交換a和b的值；ifa<ethen交換a和e的值；

ifa<cthen交換a和c的值；/*找出最大數(shù)并放在a中*/

ifb<cthen交換b和c的值；ifb<cthen交換b和c的值；

printa,b,cifb<dthen交換1）和（1的值；

ENDifb<ethen交換b和e的值；

/*找出第二大的數(shù)并放在b中*/

ifc<dthen交換c和d的值；

ifc<ethen交換c和e的值；

/*找出第三大的數(shù)并放在c中*/

ifd<ethen交換d和e的值；

/*找出第四大的數(shù)并放在（1中*/

printa,b,c,d,e

END

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUnivers計y,China3

排序時數(shù)據(jù)集中存放在一段空間中

?在前面的排序算法中，存放數(shù)據(jù)的位置（以a、b、c、d、

e表示）之間沒有聯(lián)系

?下面，約定排序時數(shù)據(jù)集中存放在一段存儲空間中

?例如：下面的7個整數(shù)連續(xù)地存放在位置1?位置7中

143

218

39

413

555

67

7

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China

簡單排序方法

?簡單排序方法有多種，這里我們介紹冒泡（起泡）排序法。

?冒泡排序法（bubblesort）的基本思想是:通過對相鄰元素的比較和

交換，使全部記錄排列有序。

?冒泡排序的過程：對每兩個相鄰的元素進行比較，若為逆序，則將

兩者交換，這樣的操作反復(fù)進行，直至全部記錄都比較、交換完畢

為止。如此經(jīng)過一趟冒泡排序之后，就將關(guān)鍵字最大（或最小）的元

素安排在最后一個（或第一個）元素的位置上。然后，對后n-1個元

素重復(fù)進行同樣的操作，則將具有次大（或次小）元素安排在倒數(shù)（或

正數(shù)）第二個元素的位置上。重復(fù)以上過程，直至沒有元素需要交換

時為止。至此，整個序列的記錄按關(guān)鍵字由小到大的順序排列完畢。

冒泡排序方法

?以7個元素為例說明冒泡排序

?位置立置7的元素初始排列如下所示

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China

冒泡排序方法

若位置1的元素大，則交換

118

243

3V

413

555

67

7

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China

冒泡排序方法

?第二步：令［置2和位置的元素比較,若位置2的元素大，則交換

118

2V

343

413

555

67

7

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China

冒泡排序方法

?第三步：令［置3和位置，的元素比較,若位置3的元素大，則交換

118

2V

313

443

555

67

7

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China

冒泡排序方法

?第四步:令Z置第□位置5的元素比較,若位置4的元素大，則交換

118

2V

313

443

555

67

7

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China

冒泡排序方法

?第五步：令［置§和位置的元素比較,若位置5的元素大，則交換

118

2V

313

443

57

655

7

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Enqineerinq,XidianUniversity,China

冒泡排序方法

?第六步：令位置6和位置7的元素比較，若位置6的元素大，則交換

118

2V

313

443

57

6

755

最大元素被交換到最后一個位置（位置7）

下一趟則需將次大元素交換到倒數(shù)第二個位置

西安電子科技大學(xué)計算機學(xué)院-SchoolofComputerScience&Engineering,XidianUniversity,China

冒泡排序方法

?第七步：令的元素比較，若位置1的元素大，則交換

第八步：令位置2和位置:的元素比較,