+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-07(1)

2019-08(109)

2019-09(120)

2019-10(17)

2019-11(1)

鸡尾酒排序(Python)

发布于2020-05-17 18:46     阅读(117)     评论(0)     点赞(4)     收藏(1)


一、鸡尾酒排序简介
二、算法步骤
三、代码实现

一、鸡尾酒排序简介

冒泡排序是每个元素根据自身的大小,一点一点的向数组的一端进行移动,它是一个单向的运动,每一轮都是从左到右来比较元素。

鸡尾酒排序,也是属于冒泡排序的一种改进方法,它是每一轮进行两个方向的比较和移动,刚开始从左到右比较,确定出一个最大数,然后从右向左比较,确定出一个最小数。其实就相当于冒泡排序在一轮中从左到右排序后,再从右往左排序一次。这样可以减少排序回合数,但是代码量和冒泡排序相比要增加一倍。
鸡尾酒排序在大部分元素已经有序的情况下,才可以发挥出它的优势。

二、算法步骤

1、确定总的排序轮数为len(arr)//2

2、设置一个布尔变量,每趟排序开始时都设置为True
3、 奇数轮,从左向右比较和交换;偶数轮开始之前,要重新标记为True;偶数轮,从右向左比较和交换
4、如果没有进行过交换,说明元素已经有序,跳出循环

三、代码实现

# 鸡尾酒排序,也是属于冒泡排序的一种改进方法
def cock_tail_sort(arr=[]):
    for i in range(len(arr)//2):
        # 有序标记,初始为True
        flag=True
        # 奇数轮,从左向右比较和交换
        for j in range(i,len(arr)-1-i):
            if arr[j]>arr[j+1]:
                arr[j+1],arr[j]=arr[j],arr[j+1]
                flag=False
        if flag:
            break
        # 偶数轮开始之前,要重新标记为True
        flag=True
        # 偶数轮,从右向左比较和交换
        for k in range(len(arr)-i-1,i,-1):
            if arr[k]<arr[k-1]:
                arr[k],arr[k-1]=arr[k-1],arr[k]
                flag=False
        if flag:
            break
    return arr

if __name__=='__main__':
    array = [3, 44, 38, 5, 15, 36, 46, 2, 48, 19]
    print(cock_tail_sort(array))

在这里插入图片描述



所属网站分类: 技术文章 > 博客

作者:你太美丽

链接: https://www.pythonheidong.com/blog/article/377304/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

4 0
收藏该文
已收藏

评论内容:(最多支持255个字符)