學(xué)習(xí)Go語言第二周肪跋，本周任務(wù)嘗試實(shí)現(xiàn)七大經(jīng)典排序算法以及分析算法復(fù)雜度、優(yōu)劣及應(yīng)用場景等土砂，七大經(jīng)典算法分別為冒泡排序州既，插入排序，選擇排序萝映，希爾排序吴叶，歸并排序，快速排序序臂，堆排序蚌卤。
冒泡排序
- 思路
正如“冒泡”二字，我的理解是重復(fù)依次比較相鄰的兩個(gè)數(shù)奥秆，大的數(shù)放在后面逊彭，小的數(shù)放在前面，一直重復(fù)到?jīng)]有任何一對數(shù)字需要交換位置為止构订。就像冒泡一樣侮叮，大的數(shù)不斷浮上來。
- 偽代碼
do
swapped = false
for i = 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap(leftElement, rightElement)
swapped = true; swapCounter++
while swapped
- Go實(shí)現(xiàn)
func Bubble_Sort(arr []int) {
swapped := true
len := len(arr)
for swapped {
swapped = false
for i := 0; i < len-1; i++ {
if arr[i] > arr[i+1] {
arr[i], arr[i+1] = arr[i+1], arr[i]
swapped = true
}
}
}
}
選擇排序
- 思路
先假設(shè)第一個(gè)元素為最小值悼瘾，然后與剩余的 len-1 個(gè)元素依次進(jìn)行比較囊榜，標(biāo)記最小數(shù)的位置，如果有更小的數(shù)亥宿，則在進(jìn)行下一輪遍歷比較之前交換位置锦聊。
- 偽代碼
repeat (numOfElements - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
- Go實(shí)現(xiàn)
func Selection_Sort(arr []int) {
len := len(arr)
for i := 0; i < len-1; i++ {
min := i
for j := i+1; j < len; j++ {
if arr[j] < arr[min] {
min = j
}
}
arr[min], arr[i] = arr[i], arr[min]
}
}
插入排序
思路
這個(gè)排序感覺和選擇排序的思路有點(diǎn)相似的。首先1個(gè)長度的數(shù)組肯定是有序的箩绍，假設(shè)數(shù)組的長度為n，第一位是有序的尺上，然后從第二位開始在已排序序列中從后向前掃描材蛛，找到相應(yīng)位置并插入。偽代碼
mark first element as sorted
for each unsorted element X
'extract' the element X
for j = lastSortedIndex down to 0
if current element j > X
move sorted element to the right by 1
break loop and insert X here
- Go實(shí)現(xiàn)
func Insertion_Sort(arr []int) {
len := len(arr)
for i := 0; i < len; i++ {
selected := arr[i]
for j := i-1; j >= 0; j-- {
if arr[j] > selected {
arr[j], arr[j+1] = arr[j+1], arr[j]
} else {
arr[j+1] = selected
break
}
}
}
}
歸并排序
- 思路
歸并排序是采用分治法的一個(gè)非常典型的應(yīng)用怎抛。歸并排序的思想就是先遞歸分解數(shù)組卑吭，再合并數(shù)組。先考慮合并兩個(gè)有序數(shù)組马绝，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)豆赏，誰小就先取誰，取了后相應(yīng)的指針就往后移一位。然后再比較掷邦，直至一個(gè)數(shù)組為空白胀，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過來即可。再考慮遞歸分解抚岗，基本思路是將數(shù)組分解成left和right或杠，如果這兩個(gè)數(shù)組內(nèi)部數(shù)據(jù)是有序的，那么就可以用上面合并數(shù)組的方法將這兩個(gè)數(shù)組合并排序宣蔚。如何讓這兩個(gè)數(shù)組內(nèi)部是有序的向抢？可以再二分，直至分解出的小組只含有一個(gè)元素時(shí)為止胚委，此時(shí)認(rèn)為該小組內(nèi)部已有序挟鸠。然后合并排序相鄰二個(gè)小組即可。（摘抄）
- 偽代碼
split each element into partitions of size 1
recursively merge adjancent partitions
for i = leftPartStartIndex to rightPartLastIndex inclusive
if leftPartHeadValue <= rightPartHeadValue
copy leftPartHeadValue
else: copy rightPartHeadValue; Increase InvIdx
copy elements back to original array
- Go實(shí)現(xiàn)
func Merge_Sort(arr []int) []int{
if len(arr) <= 1 {
return arr
}
var middle int = len(arr)/2
left := Merge_Sort(arr[:middle])
right := Merge_Sort(arr[middle:])
return merge(left, right)
}
func merge(a, b []int) []int {
alen, blen := len(a), len(b)
var z []int = make([]int, alen + blen)
k := 0//數(shù)組切片z的下標(biāo)
i, j := 0, 0//a亩冬、b起始下標(biāo)均未0
for i < alen && j < blen {
if a[i] < b[j] {
z[k] = a[i]
i++
} else {
z[k] = b[j]
j++
}
k++
}
for i != alen {
z[k] = a[i]
k++
i++
}
for j != blen {
z[k] = b[j]
k++
j++
}
return z
}
快速排序
- 思路
快速排序可能是當(dāng)前應(yīng)用最廣泛的排序算法艘希。快速排序（英語：Quicksort）鉴未，又稱劃分交換排序（partition-exchange sort）枢冤，一種排序算法，最早由東尼·霍爾提出铜秆。在平均狀況下淹真，排序n個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較连茧，但這種狀況并不常見核蘸。事實(shí)上，快速排序通常明顯比其他Ο(n log n)算法更快啸驯，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來客扎。快速排序引人注目的特點(diǎn)包括它是原地排序（只需要一個(gè)很小的輔助棧）罚斗。
該方法的基本思想是：1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)徙鱼。2．分區(qū)過程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊针姿，小于或等于它的數(shù)全放到它的左邊袱吆。3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)距淫。
- 偽代碼
for each (unsorted) partition
set first element as pivot
storeIndex = pivotIndex + 1
for i = pivotIndex + 1 to rightmostIndex
if element[i] < element[pivot]
swap(i, storeIndex); storeIndex++
swap(pivot, storeIndex - 1)
- Go實(shí)現(xiàn)
func Quick_Sort(arr []int) {
sort(arr, 0, len(arr)-1)
}
func sort(arr []int, left int, right int) {
if right <= left {
return
}
p := partition(arr, left, right)//快速排序切分
sort(arr, left, p-1)
sort(arr, p+1, right)
}
func partition(arr []int, left int, right int) int {
pivot := arr[left]
i, j := left, right+1
for true {
for i++; arr[i] < pivot; i++ {
if i==right {
break
}
}
for j--; pivot < arr[j]; j-- {
if j==left {
break
}
}
if i>=j {
break
}
arr[i], arr[j] = arr[j], arr[i]
}
arr[left], arr[j] = arr[j], arr[left]
return j
}
希爾排序
- 思路
希爾排序(Shell Sort)是插入排序的一種绞绒。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本榕暇。希爾排序是非穩(wěn)定排序算法蓬衡。該方法因DL．Shell于1959年提出而得名喻杈。希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：1. 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高狰晚，即可以達(dá)到線性排序的效率2. 但插入排序一般來說是低效的筒饰，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位
- Go實(shí)現(xiàn)
func Shell_Sort(arr []int) {
N := len(arr)
var gap int = N/2 //初始步長
for gap > 0 {
for i := gap; i < N; i++ { //每一列進(jìn)行插入排序 , 從gap 到 n-1
temp := arr[i]
j := i
for j>=gap && arr[j-gap]>temp { //插入排序
arr[j] = arr[j-gap]
j = j-gap
}
arr[j] = temp
}
gap = gap/2 //重新設(shè)置步長
}
}
堆排序
堆排序是一種選擇排序，其時(shí)間復(fù)雜度為O(nlogn)
- 堆的定義
n個(gè)元素的序列{k1家肯，k2龄砰，…,kn}當(dāng)且僅當(dāng)滿足下列關(guān)系之一時(shí)，稱之為堆讨衣』慌铮 情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小頂堆） 情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大頂堆） 其中i=1,2,…,n/2向下取整;
若將和此序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作此序列的存儲結(jié)構(gòu)）看成是一個(gè)完全二叉樹，則堆的含義表明反镇，完全二叉樹中所有非終端結(jié)點(diǎn)的值均不大于（或不小于）其左固蚤、右孩子結(jié)點(diǎn)的值。
例如歹茶，下列兩個(gè)序列為堆夕玩，對應(yīng)的完全二叉樹如圖：
若在輸出堆頂?shù)淖钚≈抵螅沟檬Ｓ鄋-1個(gè)元素的序列重又建成一個(gè)堆惊豺，則得到n個(gè)元素的次小值燎孟。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列尸昧，這個(gè)過程稱之為堆排序揩页。堆排序（Heap Sort）只需要一個(gè)記錄元素大小的輔助空間（供交換用），每個(gè)待排序的記錄僅占有一個(gè)存儲空間烹俗。
- 堆的存儲
一般用數(shù)組來表示堆爆侣，若根結(jié)點(diǎn)存在序號0處， i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i-1)/2幢妄。i結(jié)點(diǎn)的左右子結(jié)點(diǎn)下標(biāo)分別為2i+1和2i+2兔仰。（注：如果根結(jié)點(diǎn)是從1開始，則左右孩子結(jié)點(diǎn)分別是2i和2i+1蕉鸳。）如第0個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1和2乎赴。如最大化堆如下：左圖為其存儲結(jié)構(gòu)，右圖為其邏輯結(jié)構(gòu)潮尝。
- 堆的排序?qū)崿F(xiàn)
- 構(gòu)造最大堆（Build_Max_Heap）：若數(shù)組下標(biāo)范圍為0~n无虚，考慮到單獨(dú)一個(gè)元素是大根堆，則從下標(biāo)n/2開始的元素均為大根堆衍锚。于是只要從n/2-1開始，向前依次構(gòu)造大根堆嗤堰，這樣就能保證戴质，構(gòu)造到某個(gè)節(jié)點(diǎn)時(shí)度宦，它的左右子樹都已經(jīng)是大根堆。2. 堆排序（HeapSort）：由于堆是用數(shù)組模擬的告匠。得到一個(gè)大根堆后戈抄，數(shù)組內(nèi)部并不是有序的。因此需要將堆化數(shù)組有序化后专。思想是移除根節(jié)點(diǎn)划鸽，并做最大堆調(diào)整的遞歸運(yùn)算。第一次將heap[0]與heap[n-1]交換戚哎，再對heap[0...n-2]做最大堆調(diào)整裸诽。第二次將heap[0]與heap[n-2]交換，再對heap[0...n-3]做最大堆調(diào)整型凳。重復(fù)該操作直至heap[0]和heap[1]交換丈冬。由于每次都是將最大的數(shù)并入到后面的有序區(qū)間，故操作完后整個(gè)數(shù)組就是有序的了甘畅。3. 最大堆調(diào)整（Max_Heapify）：該方法是提供給上述兩個(gè)過程調(diào)用的埂蕊。目的是將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn) 疏唾。
- Go實(shí)現(xiàn)
func Heap_Sort(arr []int) {
N := len(arr)
var first int = N/2 //最后一個(gè)非葉子節(jié)點(diǎn)
for start := first; start > -1; start-- { //構(gòu)造大根堆
max_heapify(arr, start, N-1)
}
for end := N-1; end > 0; end-- { //堆排蓄氧，將大根堆轉(zhuǎn)換成有序數(shù)組
arr[end],arr[0] = arr[0],arr[end]
max_heapify(arr, 0, end-1)
}
}
func max_heapify(arr []int, start int, end int) {
root := start
for true {
child := root*2 + 1 //調(diào)整節(jié)點(diǎn)的子節(jié)點(diǎn)
if child > end {
break
}
if child + 1 <= end && arr[child] < arr[child+1] {
child = child + 1 //取較大的子節(jié)點(diǎn)
}
if arr[root] < arr[child] {
arr[root], arr[child] = arr[child], arr[root] //較大的子節(jié)點(diǎn)成為父節(jié)點(diǎn)
root = child
} else {
break
}
}
}
七種經(jīng)典排序算法指標(biāo)對比
參考資料
可視化排序動(dòng)態(tài)圖](https://visualgo.net/en/sorting))
經(jīng)典排序算法總結(jié)與實(shí)現(xiàn) (Python實(shí)現(xiàn))
堆排序 Heap Sort
算法(中文版?第4版)
