交換排序是基于“比較”和“交換”兩種操作來實(shí)現(xiàn)的排序方法 。

由于選擇“比較”的基準(zhǔn)元素不同，可將交換排序分為以下兩種：

• 冒泡排序
• 快速排序

一、冒泡排序?

1.冒泡排序基本思想?

因?yàn)槠鋵?shí)現(xiàn)與氣泡從水中往上冒的過程類似而得名。 ? ? ?

每一趟的過程都是相鄰兩個元素比較，若為逆序，則交換兩個元素，使關(guān)鍵字較小的元素如氣泡一般逐漸往上“漂移”，直至最后冒出“水面”。直到某一趟排序過程中沒有交換發(fā)生，說明序列已完全有序，排序完成。?

2.算法步驟

假設(shè)待排序的n個數(shù)據(jù)元素存放在數(shù)組a中

（1）首先將第一個元素與第二個元素進(jìn)行比較，若為逆序（a[0]>a[1]），則將兩個元素交換，然后比較第二個元素和第三個元素。依次類推，直到第n-1個元素完成比較為止。上述過程稱為第一次冒泡排序過程，其結(jié)果使得最大的記錄被放在了最后一個記錄的位置上。 ? ?

（2）然后進(jìn)行第二次冒泡排序過程，對前n-1個記錄進(jìn)行同樣的操作，將次大的記錄放在第n-1個記錄的位置上。 ? ?

（3）依此類推，直到某一次冒泡排序過程不再有交換發(fā)生，算法結(jié)束。

3.冒泡排序算法示例?

例：設(shè)待排元素序列為{56,25,70,99,82,10,15,56}，請給出冒泡排序法進(jìn)行排序的過程。?

4.算法代碼?

def bubble_sort2(self):data_len = len(self.data)for i in range(data_len-1, 0, -1):  # 獲得i號位置的正確值flag = Truefor j in range(0, i):if self.data[j+1].key <= self.data[j].key:             self.data[j], self.data[j + 1] = self.data[j + 1], self.data[j]                flag = Falseif flag:break

flag的作用：

• 冒泡算法的每一輪都是相鄰元素a[0]與a[1], a[1]與a[2], ……比較，若為逆序則交換
• 只要某一輪發(fā)生了元素交換，則flag=False，說明此時整個數(shù)組還是無序狀態(tài)，需要進(jìn)行下一輪的相鄰元素比較與交換
• 若某一輪相鄰元素比較下來沒有交換發(fā)生，則flag=True，說明此時整個序列已經(jīng)有序了，以后輪次的比較就不再需要了
• 最好情況下，序列本身有序，則只需進(jìn)行一輪比較，無交換

5.算法分析?

（1）空間復(fù)雜度：在進(jìn)行元素交換時，冒泡排序需要一個輔助空間臨時存放元素，其空間復(fù)雜度為O(1)。? ? ? ??

（2）時間復(fù)雜度：最好的情況下，序列本身是有序的。此時只需要一趟遍歷進(jìn)行n-1次相鄰元素比較，無需交換操作。 ? ? ? ? ?最壞的情況下，初始序列為逆序，此時需要n-1趟遍歷，第i趟遍歷需要比較n-i次，總共比較n(n-1)/2次。每次比較都需要移動，因?yàn)槊看我苿佣家ㄟ^輔助空間來進(jìn)行，故每次移動次數(shù)都為3，總共移動次數(shù)3n(n-1)/2。所以綜合考慮，冒泡排序算法的時間復(fù)雜度為O(n2)。

（3）其他方面：冒泡排序也可用于鏈?zhǔn)酱鎯Y(jié)構(gòu)的序列排序，如果初始序列無序性強(qiáng)，數(shù)據(jù)元素多，則移動次數(shù)較多，此時不宜采用冒泡排序。 ? ? ? ?

由于冒泡排序是順次移動元素，所以不會破壞數(shù)值相同元素的初始次序，是一種穩(wěn)定的排序方法。?

二、快速排序

1.快速排序（劃分交換排序）算法思想?

（1）從數(shù)列中挑出一個元素，稱為“基準(zhǔn)”。 ? ? ?

（2）重新排序數(shù)列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有大于或者等于基準(zhǔn)值的元素擺在基準(zhǔn)的后面，這個稱為劃分操作。在這個劃分結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。 ? ? ?（3）遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序進(jìn)行上述劃分過程。?

快速排序基本思想?

• 將序列中的某一記錄設(shè)置為樞軸（pivot），一趟排序?qū)休S交換到其最終位置，所有小于樞軸的記錄交換到樞軸的左邊，所有大于等于樞軸的記錄交換到樞軸的右邊，這個過程稱為一趟劃分（partition）。
• 接下來對左子序列和右子序列分別快速排序，直至被排序子序列長度小于等于1為止。
• 分而治之思想，對整個序列的排序分解為對左子序列和右子序列的排序，是一種遞歸排序。

?一趟劃分方法

• 對數(shù)組data中l(wèi)ow~high范圍內(nèi)的元素進(jìn)行一趟劃分。
• 一般選取data[low]作為樞軸pivot。
• 在劃分過程中始終保持下圖所示的不變式，即pivot之后為小于pivot的區(qū)域A，緊接著是大于等于pivot的區(qū)域B，后面是i號位置開始的待處理區(qū)域。初始時，i=low+1，A和B區(qū)域的長度都為0。?
• ?為了維持不變式，如果i號記錄大于等于pivot，則i加1，即B區(qū)域長度增加1；否則，則將i號記錄與B區(qū)域的最左記錄進(jìn)行交換。
• 為了方便交換，記錄A、B區(qū)域的分界點(diǎn)last_small，設(shè)last_small為A區(qū)域的最右端位置。交換時，將last_small加1，i號記錄與last_small位置記錄交換，接著i加1。

?

當(dāng)i超出high的范圍，說明除了pivot之外的所有記錄都已歸入A區(qū)域或B區(qū)域，如圖所示，此時，只需將pivot與last_small所指記錄進(jìn)行交換，即可達(dá)成一趟劃分的目標(biāo)。

?2.快速排序算法舉例

例：設(shè)待排數(shù)據(jù)元素序列為{26，67，67，9，6，43，82，10，54}，請給出快速排序法進(jìn)行排序的過程。

3.快速排序代碼?

?一趟劃分交換的代碼

def partition(self, low, high):last_small = lowfor i in range(low + 1, high + 1):if self.data[i] < self.data[low]:last_small = last_small + 1self.swap(last_small, i)self.swap(low, last_small)return last_small

def swap(self, i, j):  # 將i號和j號位置的記錄交換self.data[i], self.data[j] = self.data[j], self.data[i]

遞歸算法和接口方法

def recursive_quickSort(self, low, high):if low < high:self.swap(low,(low+high)//2)pivot_position = self.partition(low, high)self.recursive_quickSort(low, pivot_position - 1)self.recursive_quickSort(pivot_position + 1, high)def quick_sort(self):self.recursive_quickSort(0, len(self.data) - 1)

?4.算法分析

（1）空間復(fù)雜度：快速排序是遞歸程序，每層遞歸調(diào)用過程需要一個棧來存放指針與參數(shù)，而快速排序最大遞歸調(diào)用的次數(shù)與遞歸樹的深度一致，因此最好的情況下空間復(fù)雜度為O(log2n)，最壞的情況下為O(n)。 ? ? ?

（2）時間復(fù)雜度：平均情況O(n log2n) ，最壞情況，即每次劃分過程產(chǎn)生的兩個區(qū)間分別包含n-1個元素和1個元素的情況，比如待排序列已經(jīng)有序的時候，其遞歸樹為單分支樹，這樣必須進(jìn)行n-1趟才能將所有元素定位，快速排序已經(jīng)蛻化為簡單排序的水平，其時間復(fù)雜度為O(n2)。

? ? 當(dāng)對較大量數(shù)據(jù)構(gòu)成的遞增序列進(jìn)行快速排序，且采用首元素為樞軸，可能發(fā)生遞歸調(diào)用棧溢出的錯誤。 ? ? ? ?

? ? 為避免出現(xiàn)極端情況，可在進(jìn)行一次劃分之前進(jìn)行“預(yù)處理”，即先對data[low].key、data[high].key和data[(low+high)//2].key進(jìn)行相互比較，然后取關(guān)鍵字值“三者之中”的記錄為樞軸記錄。?

? ? 當(dāng)基準(zhǔn)元素選擇得當(dāng)?shù)臅r候（每次都選擇中間元素為基準(zhǔn)），每一趟排序都能將元素均勻地分割成兩個長度相等的子序列，達(dá)到快速排序的最好情況，此時分割次數(shù)等于完全二叉樹的深度log2n，另外，無論序列如何劃分，全部比較次數(shù)都接近于n-1次，所以時間復(fù)雜度為O(nlog2n)。一般情況下，基準(zhǔn)元素是隨機(jī)分布的，序列分割次數(shù)接近于log2n，所以快速排序的平均時間復(fù)雜度為O(nlog2n)。

（3）其他方面：在所有同數(shù)量級的排序方法中，依平均時間復(fù)雜度，尤其是初始序列無序性強(qiáng)，數(shù)據(jù)元素比較多的時候，快速排序是目前性能最好的內(nèi)部排序方法。在排序過程中需要序列的上下邊界，所以不適合鏈?zhǔn)酱鎯Y(jié)構(gòu)排序。由于數(shù)據(jù)元素移動的時候是不按順序的，所以快速排序是一種不穩(wěn)定的排序方法。