擴展閱讀：冒泡排序
局部有序和整體有序
對于一個由整數(shù)組成的序列A[0,n)，任何相鄰的兩個數(shù)，都滿足A[i - 1] <= A[i]（前一項小于后一項）我們稱為順序的，那么也就是說，一個有序序列的任何相鄰數(shù)對，都是順序的。反之，對于一個局部存在逆序?qū)Φ男蛄衼碚f，一定不是有序的。
那么我們是不是可以通過不斷改善一個無序序列相鄰逆序?qū)Φ捻樞?，可以使這個序列有序呢？
掃描交換
在用j和j+1標記的一對數(shù)中，通過掃描是否屬于逆序關系，如果后一項小于前一項，就交換它們。
雖然經(jīng)過這樣一趟掃描，序列未必達到整體有序，但有最大的一個元素必然就位。
通過這樣反復的掃描，多次交換后，所有元素都回到了自己的位置。
// 冒泡排序
void bubbleSortA(int a[], int n) {
? ?for(int i = 0; i < n; i++)
? ? ? ?for (int j = 0; j < n-i-1; j++) {
? ? ? ? ? ?if (a[j+1] < a[j])
? ? ? ? ? ? ? ?swap(a[j+1], a[i]);
? ? ? ?}
}這個思路的實現(xiàn)只用了幾行代碼，真正讓人困惑的，可能就是這里的j范圍的界定，為什么j < n-i-1。
通過不斷蠶食待排序的部分，使整個序列有序。
排序過程中，雖有元素朝著各自最終位置亦步亦趨的移動，這個過程可以形象的視為冒泡。
對于這樣一個長度為n的序列，每經(jīng)過1輪掃描后，最大的1個元素必然就位，由此我們可以得出，
掃描交換的時間線性正比于無序部分的規(guī)模，整體呈現(xiàn)出算術級數(shù)的形式，所以它的時間復雜度與末項成平方關系。
冒泡排序改進
這樣的算法是否真的可以滿足我們在各種情況下的需求呢？
可以設想一個這樣的序列，部分元素已經(jīng)就位，但是待排序的部分未必是無序的。
對于這樣一個序列，如果采用我們一開始的算法，就會在序列整體有序后，多余的繼續(xù)掃描序列。
換句話說，我們對于相鄰兩個元素的檢查，可能在不久的過去已經(jīng)做過了，它們是有序的，但我們還是機械的一趟一趟掃描這些序列，就只是為了我們認為的所有元素歸位。
改進的策略是，我們在掃描時，不妨記錄一下，是否真的存在逆序?qū)Γ绻淮嬖?，那么這個序列局部處處有序，整體必然是有序的，我們可以提前終止程序了。
現(xiàn)在的問題是，如何判斷存在或不存在逆序?qū)Γ蛘哒f，什么是存在逆序?qū)Φ臈l件？這個問題的答案是不言而喻的，就是在這一趟掃描中，曾經(jīng)是否交換過一對元素。
// 冒泡排序改進
void bubbleSortB(int a[], int n) {
? ?bool sorted = false; ? ? ? ? ? ? ? ?// 定義全局順序標志，首先認為尚未排序
? ?while (!sorted) { ? ? ? ? ? ? ? ? ?// 尚未確定是否排序前，先逐躺掃描
? ? ? ?sorted = true; ? ? ? ? ? ? ? ?// 無罪推論，假定全局順序
? ? ? ?for (int i = 1; i < n; i++)
? ? ? ? ? ?if (a[i] < a[i - 1]) { ? ? ?// 發(fā)現(xiàn)逆序?qū)Γ? ? ? ? ? ? ? ? ?sorted = false; ? ? ? ?// 發(fā)現(xiàn)罪證，清除全局順序標志
? ? ? ? ? ? ? ?swap(a[i], a[i - 1]); ? ?// 交換，使得局部順序
? ? ? ? ? ?}
? ? ? ?n--; ? ? ? ? ? ? ? ? ? ? ? ?// 部分元素歸位，縮小待排序序列的規(guī)模
? ?}
}冒泡排序再改進
這樣的算法是否就可以應對所有的場景呢？
由于篇幅原因，這里直接給出改進的代碼和思路。通過增加last來標記掃描的邊界，對于超出邊界的元素，是否值得掃描呢，留給各位自己思考。
// 冒泡排序再改進
void bubbleSortC(int a[],int n){
? ?bool sorted = false; ? ? ? ? ? ? ? ?// 定義全局順序標志，首先認為尚未排序
? ?while (!sorted) { ? ? ? ? ? ? ? ? ? // 尚未確定是否排序前，先逐躺掃描
? ? ? ?sorted = true; ? ? ? ? ? ? ? ? // 無罪推論，假定全局順序
? ? ? ?int last = n;
? ? ? ?for (int i = 1; i < n; i++)
? ? ? ? ? ?if (a[i] < a[i - 1]) { ? ? ?// 發(fā)現(xiàn)逆序?qū)Γ? ? ? ? ? ? ? ? ?sorted = false; ? ? ? ?// 發(fā)現(xiàn)罪證，清除全局順序標志
? ? ? ? ? ? ? ?swap(a[i], a[i - 1]); ? // 交換，使得局部順序
? ? ? ? ? ? ? ?last = i+1;
? ? ? ? ? ?}
? ? ? ?n = (last < n-1) ? last : n-1; ? ?// 部分元素歸位，縮小待排序序列的規(guī)模
? ?}
}