一、冒泡排序
原理
冒泡排序是一種簡單的交換類排序方法旺上，能夠將相鄰的數(shù)據(jù)元素進行交換灌闺，從而逐步將待排序序列變成有序序列。冒泡排序的基本思想是：從頭掃描待排序記錄序列堕义，在掃描的過程中順次比較相鄰兩個元素的大小。
下面以升序為例介紹排序過程:
1.在第一趟排序中，對n個記錄進行如下操作。
①對相鄰的兩個記錄的關鍵字進行比較稀并，逆序時就交換位置沛硅。
②在掃描的過程中，不斷向后移動相鄰兩個記錄中關鍵字較大的記錄猿推。
③將待排序記錄序列中的最大關鍵字記錄交換到待排序記錄序列的末尾，這也是最大關鍵字記錄應在的位置。
2.進行第二趟冒泡排序褐捻，對前n-1個記錄進行同樣的操作，其結果是使次大的記錄被放在第n-1個記錄的位置上椅邓。
3.繼續(xù)進行排序工作柠逞，在后面幾趟的升序處理也反復遵循了上述過程，直到排好順序為止景馁。如果在某一趟冒泡過程中沒有發(fā)現(xiàn)一個逆序板壮，就可以馬上結束冒泡排序。整個冒泡過程最多可以進行n-1趟合住。
動畫演示過程
Go語言描述
冒泡排序法運行效率較低绰精，但概念上最簡單,由于太慢，實戰(zhàn)基本不用
- 平均時間復雜度：O(n2)
- 最壞時間復雜度：O(n2)
- 最好時間復雜度：O(n)
- 空間復雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
思路：
1.對未排序的各元素從頭到尾依次比較相鄰的兩個元素大小關系
2.如果左邊的元素大透葛，則兩元素交換
3.向右移動一個位置笨使，比較下面的兩個元素
4.當走到最右端時，最大的元素一定被放在最右邊
5.按照這個思路從左端開始依次類推
冒泡排序的基本思想是僚害，對相鄰的元素進行兩兩比較硫椰，順序相反則進行交換，
這樣，每一趟會將最小或最大的元素“浮”到頂端最爬，最終達到完全有序涉馁。時間復雜度為O(n2）
// 冒泡排序的第一種實現(xiàn)：直接使用內(nèi)層循環(huán)參數(shù)，外層循環(huán)參數(shù)只規(guī)定輪數(shù)
func BubbleSort(list []int, asc bool) {
count := len(list)
for i := 0; i < count-1; i++ { // 冒泡的輪次：選定一個元素爱致，輪數(shù)為n-2次
flag := true
for j := 0; j < count-1-i; j++ { // 每輪冒泡的過程：比較選定元素和其他元素烤送，每輪冒泡比較的元素逐漸減少
if asc {
// 從左到右升序，保持最大的在最右邊
if list[j] > list[j+1] {
list[j], list[j+1] = list[j+1], list[j]
flag = false
}
} else {
// 從左到右降序糠悯，保持最大的在最左邊
if list[j] < list[j+1] {
list[j], list[j+1] = list[j+1], list[j]
flag = false
}
}
}
if flag {
break
}
}
}
二帮坚、快速排序
原理
在前面介紹的冒泡排序中，在掃描過程中只比較相鄰的兩個元素互艾，所以在互換兩個相鄰元素時只能消除一個逆序试和。其實也可以通過兩個不相鄰的元素進行交換，這樣做的好處是消除待排序記錄中的多個逆序纫普，這樣會加快排序的速度阅悍。由此可見，快速排序方法就是通過一次交換而消除多個逆序的過程昨稼。
快速排序的基本思想如下所示：
1.從待排序記錄序列中選取一個記錄节视，通常選取第一個記錄，將其關鍵字設為K1 假栓。
2.將關鍵字小于K1 的記錄移到前面寻行，將關鍵字大于K1 的記錄移到后面，結果會將待排序記錄序列分成兩個子表匾荆。
3.將關鍵字為K1 的記錄插到其分界線的位置拌蜘。
我們通常將上述排序過程稱作一趟快速排序，通過一次劃分之后牙丽，會形成以關鍵字K1 這個記錄作為分界線简卧，并且將待排序序列分成了兩個子表，前面子表中所有記錄的關鍵字都不能大于K1 烤芦，后面子表中所有記錄的關鍵字都不能小于K1 贞滨。我們可以對分割后的子表繼續(xù)按上述原則進行分割，直到所有子表的表長不超過1為止拍棕，此時待排序記錄序列就變成了一個有序表晓铆。
快速排序算法基于分治策略，可以把待排序數(shù)據(jù)序列分為兩個子序列绰播，具體步驟如下所示：
1.從數(shù)列中挑出一個元素骄噪，將該元素作為“基準”。
2.掃描一遍數(shù)列蠢箩，將所有比“基準”小的元素排在基準前面链蕊，所有比“基準”大的元素排在基準后面事甜。
3.使用遞歸將各子序列劃分為更小的序列，直到把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序滔韵。
動畫演示過程
Go語言描述
快速排序：是一個就地排序逻谦，分而治之，大規(guī)模遞歸的算法陪蜻。它是冒泡排序的加強版邦马，但從本質(zhì)上來說，它是歸并排序的就地版本宴卖。
- 平均時間復雜度：O(nlogn)
- 最壞時間復雜度：O(n2)
- 最好時間復雜度：O(n)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
快速排序可以由下面四步組成：
（1）如果不多于1個數(shù)據(jù)滋将，直接返回。
（2）一般選擇序列最左邊的值作為支點數(shù)據(jù)症昏。
（3）將序列分成2部分随闽，一部分都大于支點數(shù)據(jù)，另外一部分都小于支點數(shù)據(jù)肝谭。
（4）對兩邊利用遞歸排序數(shù)列掘宪。
快速排序比大部分排序算法都要快。盡管我們可以在某些特殊的情況下寫出比快速排序快的算法攘烛，但是就通常情況而言添诉，沒有比它更快的了。
快速排序是遞歸的医寿，對于內(nèi)存非常有限的機器來說，它不是一個好的選擇蘑斧。時間復雜度是 O(nlogn)靖秩，空間復雜度最差是O(n), 平均是O(logn)。
func QuickSort(list []int) {
count := len(list)
quickSort(list, 0, count-1)
}
// 分而治之思想竖瘾，遞歸函數(shù)
func quickSort(list []int, left, right int) {
// 小于兩個的不用排序
count := len(list)
if count < 2 {
return
}
// 符合排序條件
if left < right {
// 找基準并排序
benchmark := getAdjust(list, left, right)
// 左邊遞歸排序
quickSort(list, left, benchmark-1)
// 右邊遞歸排序
quickSort(list, benchmark+1, right)
}
}
// 找基準
func getAdjust(list []int, left, right int) int {
// 最簡單找最左為基準數(shù)
x := list[left]
i, j := left, right
// 從右向左找小于x的數(shù)沟突，發(fā)現(xiàn)此數(shù)則退出此循環(huán)
for i < j && list[j] >= x {
j--
}
// 從左向右找大于x的數(shù)，發(fā)現(xiàn)此數(shù)則退出此循環(huán)
for i < j && list[i] <= x {
i++
}
// 交換
if i < j {
list[i], list[j] = list[j], list[i]
}
// 基準數(shù)歸位捕传，現(xiàn)在左邊的序列小于基準數(shù)惠拭，右邊的序列大于基準數(shù)
list[left], list[i] = list[i], list[left]
return i
}
