山東公務員考試網計算機常識-交換類排隊序法

所謂交換類排序法是指借助數據元素之間的互相交換進行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。

1、冒泡排序法

基本過程如下：

首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。放最大值

然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個元素的大小。若相鄰兩個元素中，后面的元素大于前面的元素，則將它們互換，這樣就又消去了一個逆序。放最小值。

重復上述過程，直到剩下的線性有變空為止，此時的線性表已經變為有序。

假設線性表的長為n，則在最壞情況下，冒泡排序需要經過n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數為n(n-1)/2。

2、 快速排序法

快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法。

基本思想如下：

從線性表中選取一個元素，設T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結果就將線性表分成了兩部分（稱為兩個子表），T插入到其分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。

如此反復，則此時的線性表就變成了有序表。

步驟：首先，在表的第一個，中間一個與最后一個元素中選取中項，設為P（K），并將P（K）賦給T，再將表中的第一個元素移到P（K）的位置上。

然后設置兩個指針i和j分別指向表的起始與最后的位置。反復操作以下兩步：

（4） 將j逐漸減小，并逐次比較P（j）與T，直到發現一個P(j)<T為止，將P(j)移到P(i)位置上。

（5） 將i逐漸減小，并逐次比較P（i）與T，直到發現一個P(i)>T為止，將P(i)移到P(j)位置上。

上述兩個操作交替進行，直到指針i與j 指向同一個位置（即i=j）為止，此時將P(i)的位置上。

分割需要記憶，用棧來實現。

更多精彩資訊請關注查字典資訊網，我們將持續為您更新最新資訊!