摘要
冒泡排序相對來說敬特，多少都有些了解掰邢，就是多循環(huán)幾輪，每一輪找出最大值放在尾部伟阔，直到數(shù)組中的元素有序為止辣之。
在這基礎上，探討一下有沒有高階的方法皱炉，比如1.提前結(jié)束循環(huán)怀估，或者2.循環(huán)中提前終止，進行下一個循環(huán)娃承。這個是要探討的重點
算法這部分用的編輯語言是 JAVA奏夫，編譯工具是 Eclipse，JAVA 與 Swift 有些不同历筝，邏輯是相通的酗昼，咱的核心就是看邏輯，盡量不要把自己局限在某一種代碼語言中梳猪。
邏輯
將序列中的元素按照一定的比較規(guī)則每每相鄰的元素比較并交換麻削。直到序列完全有序為止蒸痹。
流程
這里是將一個序列處理成從小到大的有序序列：
- 從頭開始比較每一對相鄰元素，如果第一個比第二個大呛哟，就交換它們的位置叠荠。最后一個元素就是最大的元素。
- 忽略上一步中找到的最大元素扫责，繼續(xù) 1 中的操作榛鼎，直到全部元素有序為止。
實現(xiàn)
循環(huán)從尾部開始循環(huán)鳖孤，進行相鄰元素比較和交換者娱。讓每一輪獲得的最大元素放到尾部，下次循環(huán)避開最大元素坐標
for (int end = array.length-1; end > 0; end--) {
for (int begin = 1; begin <= end; begin++) {
if (cmp(begin, begin-1) < 0) {
swap(begin, begin-1);
}
}
}
技巧
Q：為什么大循環(huán)從尾部開始苏揣？
A：示例中是將每一輪大的值放在尾部黄鳍，為了下次循環(huán)避開尾部，所以從尾部開始平匈。
Q：可以更加高效嗎框沟？
A：可以從兩個方面來提高它的效率
- 某一次循環(huán)中已經(jīng)完全有序，則可以終止增炭。
- 序列尾部已經(jīng)達到局部有序忍燥，那么就可以不再遍歷這部分
這兩種可以通過設置標示實現(xiàn)。具體可以看進階部分
進階（含兩個）
如果序列已經(jīng)完全有序弟跑，可以提前終止循環(huán)灾前。
在每一次循環(huán)中設置 isSorted（已經(jīng)有序） 標示防症，如果在遍歷中發(fā)生了交換孟辑，就設置為 false，在遍歷結(jié)束后判斷這個標示蔫敲，如果是 true 就證明整個序列已經(jīng)有序饲嗽，退出循環(huán)。
for (int end = array.length - 1; end > 0; end--) {
boolean isSorted = true;
for (int begin = 1; begin <= end; begin++) {
if (cmp(begin, begin-1) < 0) {
swap(begin, begin-1);
isSorted = false;
}
}
if (isSorted) break;
}
如果序列尾部已經(jīng)局部有序奈嘿，可以記錄最后一次交換的位置貌虾，減少交換的次數(shù)
sortedIndex 是在遍歷完成后，記錄了最后發(fā)生交換的位置裙犹，從這個位置到序列的尾部尽狠，沒有發(fā)生交換，即這部分的元素是有序的叶圃，下次遍歷就不用再遍歷這部分了袄膏。
for (int end = array.length - 1; end > 0; end--) {
// sortedIndex 的初始值在數(shù)組完全有序的時候有用
int sortedIndex = 1; // sortedIndex 的值可以是其他值，-1 或者其他掺冠。目的是達到有序的時候就不需要再進行下面的代碼
for (int begin = 1; begin <= end; begin++) {
if (cmp(begin, begin-1) < 0) {
swap(begin, begin-1);
sortedIndex = begin;
}
}
end = sortedIndex;
}
時間和空間復雜度
- 最好沉馆、平均時間復雜度：O(n^2)
- 最壞時間復雜度：O(n)
- 空間復雜度：O(1)
