您好,登錄后才能下訂單哦!
吐個(gè)槽
又是一個(gè)不正經(jīng)取名的排序算法。真要說(shuō)和雞尾酒間的關(guān)系,大概就是想喝到雞尾酒(得到排序好的隊(duì)列)就要搖晃酒杯讓不同的成分混合均勻(向兩個(gè)方向冒泡排序)
原理
雞尾酒排序(Cocktail Sort)是冒泡排序的一種優(yōu)化算法。原本的冒泡排序只能在一輪中挑出一個(gè)值移動(dòng)到最后,而雞尾酒則可以在一輪里挑最大的移到最后,再挑最小的移到最前面。實(shí)際上就是先正向進(jìn)行一輪普通的冒泡排序,然后再逆向進(jìn)行一輪反向冒泡,每輪冒泡都縮小一點(diǎn)范圍。
復(fù)雜度
最好情況是正序排列的數(shù)列O(n),最壞情況是逆序O(n^2),平均還是O(n^2)??臻g復(fù)雜度都是O(1)。
排序過(guò)程
特別找來(lái)一張圖,方便理解。注意看圖中紅色標(biāo)記的元素,每次向右都是把最大的元素交換到后面,向左都是把最小的交換到前面。
代碼
package main
import (
"time"
"fmt"
"math/rand"
)
func main() {
var length = 10
var list []int
// 以時(shí)間戳為種子生成隨機(jī)數(shù),保證每次運(yùn)行數(shù)據(jù)不重復(fù)
r := rand.New(rand.NewSource(time.Now().UnixNano()))
for i := 0; i < length; i++ {
list = append(list, int(r.Intn(1000)))
}
fmt.Println(list)
// 只需n/2輪的比較,因?yàn)槊枯喞锒紩?huì)吧最大值移到隊(duì)尾,最小值移到隊(duì)首
for loop := 1; loop < length/2; loop++ {
sorted := false
var j int
// 先正向冒泡,把最大值移動(dòng)到隊(duì)尾
for j = loop - 1; j < length-loop; j++ {
if list[j] > list[j+1] {
list[j], list[j+1] = list[j+1], list[j]
sorted = true
}
}
// 如果跑了一輪沒(méi)有交換元素,說(shuō)明已經(jīng)排好序了
if !sorted {
break
}
// 再反向冒泡,把最小值移動(dòng)到隊(duì)首
for ; j >= loop; j-- {
if list[j] < list[j-1] {
list[j], list[j-1] = list[j-1], list[j]
sorted = true
}
}
if !sorted {
break
}
fmt.Println(list)
}
}
運(yùn)行結(jié)果
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。