交換排序的基本思想是比較待排序記錄的關鍵字，當發現兩條記錄的順序相反時進行交換，直到沒有順序相反的記錄為止。
應用交換排序基本思想的主要排序方法有:冒泡排序和快速排序。
冒泡排序
1，排序方法
排序後的記錄數組R [1...n]垂直排列，將每條記錄R[i]視為壹個權重為R[i].key的氣泡，根據輕氣泡不能在重氣泡之下的原則，對數組R進行自下而上的掃描:掃描每壹個違反該原則的輕氣泡，使其向上“浮動”。重復這個過程，直到最後的兩個氣泡中，較輕的在頂部，較重的在底部。
(1)初始
R [1...n]是壹個無序區域。
(2)第壹次掃描
從無序區底部向上依次比較相鄰兩個氣泡的重量。如果發現較輕的在下面，較重的在上面，就交換位置。也就是比較(R[n]，R[n-1])，(R[n-1]，R[n-2])，...，(R[2]，R[1])；對於每壹對泡泡(r [j+1]，R[j])，如果R[j+1]。鍵< R[j]。鍵，R[j+1]和r [j]的內容互換。
當第壹次掃描完成後，“最輕”的氣泡會浮到區間頂部，即關鍵字最小的記錄放在最高位置R[1]。
(3)第二次掃描
掃描r [2...n】。當掃描完成時，“第二個光”氣泡漂浮到R[2]的位置...
最後，有序區域R [1...n]可以在n-1次掃描後獲得。
註意:
在第I次掃描時，R [1...I-1]和R [I...n]分別是當前有序區和無序區。掃描仍然是從無序區域的底部到該區域的頂部。當掃描完成後，這個區域最輕的氣泡浮到頂部位置R[i]，結果是R [1...I]成為新的有序區域。
2.氣泡分類過程示例
對關鍵字序列為49 38 65 97 76 13 27 49的文件進行冒泡排序的過程。
3.分類算法
(1)分析
因為每次排序都會給有序區域增加壹個氣泡，經過n-1次排序後，有序區域有n-1個氣泡，無序區域的氣泡重量總是大於等於有序區域的氣泡重量，所以整個氣泡排序過程最多需要n-1次排序。
如果在某壹次排序通過中沒有發現氣泡位置的交換，則說明待排序的無序區域中的所有氣泡都滿足較輕的在上面，較重的在下面的原則，所以在這壹次排序通過後可以終止氣泡排序過程。因此，在下面給出的算法中，引入了布爾交換，並且在每次排序之前將其設置為FALSE。如果在排序過程中發生交換，則將其設置為TRUE。每次分揀結束時檢查交換。如果沒有發生交換，則終止算法，並且不排序下壹遍。
(2)具體算法
void冒泡排序(SeqList R)
{//R(l..n)為待排序文件，R為自底向上掃描冒泡。
int i，j；
布爾交換；//交換標誌
for(I = 1；我& ltn；I++){ //最多做n-1排序。
交換=假；//此行排序開始前，交換標誌要為假。
for(j = n-1；j & gt= I；j-)//掃描當前無序區域R [i...從下到上。
if(R[j+1]。key & ltR[j]。key){//交換記錄
R[0]= R[j+1]；//R[0]不是崗哨，只是壹個臨時存儲單元。
R[j+1]= R[j]；
R[j]= R[0]；
交換=真；//交換已經發生，所以交換標誌設置為true。
}
如果(！交換)//本次排序沒有交換，算法提前終止。
返回；
} //endfor(外部循環)
} //BubbleSort
4.算法分析
(1)算法的最優時間復雜度
如果文件的初始狀態是正序，排序可以在壹次掃描中完成。所需的關鍵字比較時間c和記錄移動時間m都達到最小值:
Cmin=n-1
Mmin=0 .
冒泡排序的最佳時間復雜度為O(n)。
(2)算法的最壞時間復雜度
如果初始文件的順序相反，則需要對n-1遍進行排序。每次排序都需要N-i個關鍵字比較(1≤i≤n-1)，每次比較都要移動記錄三次才能到達交換記錄位置。在這種情況下，比較和移動的次數達到最大值:
Cmax=n(n-1)/2=O(n2)
Mmax=3n(n-1)/2=O(n2)
冒泡排序最差的時間復雜度是O(n2)。
(3)該算法的平均時間復雜度為O(n2)
雖然冒泡排序不必經過n-1遍，但由於記錄移動次數較多，其平均時間性能比直接插入排序差很多。
(4)算法的穩定性
冒泡排序是原地排序，比較穩定。
5.改進算法
上述氣泡排序也可以改進如下:
(1)記住上次交換位置的冒泡排序。
在每次掃描中，記住最後壹次交換的位置(這個位置之前的相鄰記錄都是有序的)。在下壹次排序開始時，r [1..lastexchange-1]是有序區域，R[lastExchange..n]是壹個無序區域。這樣，壹遍排序可以在當前有序區域中擴展多條記錄，從而減少排序遍數。具體算法見習題。
(2)通過改變掃描方向進行氣泡分類
①氣泡分選的不對稱性
當壹次掃描即可完成分類時:
只有最輕的氣泡位於R[n]的位置，其余的氣泡按順序排列，所以只需要壹次掃描就可以完成排序。
例如，對於初始關鍵字序列12，18，42，44，45，67，94，10，只需要壹次掃描。
需要n-1次掃描來完成排序:
當只有最重的氣泡位於R[1]的位置，而其余的氣泡已經排序時，仍然需要n-1次掃描來完成排序。
比如初始關鍵詞序列:94，10，12，18，42，44，45，67，需要掃描七次。
②不對稱的原因
每次掃描只能讓最重的氣泡“沈”壹個位置，所以當頂部最重的氣泡沈到底時，需要n-1次掃描。
③改善不對稱的方法。
在排序過程中交替改變掃描方向可以改善不對稱性。