广州哪个公司做网站,域名注册平台哪个好,国内个人网站设计,域名注册后网站建设吐个槽又是一个不正经取名的排序算法。真要说和鸡尾酒间的关系#xff0c;大概就是想喝到鸡尾酒(得到排序好的队列)就要摇晃酒杯让不同的成分混合均匀(向两个方向冒泡排序)原理鸡尾酒排序(Cocktail Sort)是冒泡排序的一种优化算法。原本的冒泡排序只能在一轮中挑出一个值移动到…吐个槽又是一个不正经取名的排序算法。真要说和鸡尾酒间的关系大概就是想喝到鸡尾酒(得到排序好的队列)就要摇晃酒杯让不同的成分混合均匀(向两个方向冒泡排序)原理鸡尾酒排序(Cocktail Sort)是冒泡排序的一种优化算法。原本的冒泡排序只能在一轮中挑出一个值移动到最后而鸡尾酒则可以在一轮里挑最大的移到最后再挑最小的移到最前面。实际上就是先正向进行一轮普通的冒泡排序然后再逆向进行一轮反向冒泡每轮冒泡都缩小一点范围。复杂度最好情况是正序排列的数列O(n)最坏情况是逆序O(n^2)平均还是O(n^2)。空间复杂度都是O(1)。排序过程特别找来一张图方便理解。注意看图中红色标记的元素每次向右都是把最大的元素交换到后面向左都是把最小的交换到前面。[golang] 数据结构-鸡尾酒排序代码package mainimport (timefmtmath/rand)func main() {var length 10var list []int// 以时间戳为种子生成随机数保证每次运行数据不重复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轮的比较因为每轮里都会吧最大值移到队尾最小值移到队首for loop : 1; loop length/2; loop {sorted : falsevar j int// 先正向冒泡把最大值移动到队尾for j loop - 1; j length-loop; j {if list[j] list[j1] {list[j], list[j1] list[j1], list[j]sorted true}}// 如果跑了一轮没有交换元素说明已经排好序了if !sorted {break}// 再反向冒泡把最小值移动到队首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)}}运行结果[golang] 数据结构-鸡尾酒排序©著作权归作者所有来自51CTO博客作者NicoChen的原创作品如需转载请注明出处否则将追究法律责任
