算法-有趣的鸡尾酒排序算法

内容纲要

冒泡和鸡尾酒排序(双向冒泡)

鸡尾酒排序为什么叫鸡尾酒排序,我特地百度了下,由于排序过程类似搅拌,也叫鸡尾酒搅拌排序,具体现象可以根据下图观察得出

鸡尾酒排序算法可视化

原理:对待排序列进行双向的循环,采用冒泡排序的方式,在正向循环时把最大元素移动到序列末端,在逆向循环时把最小元素移动到前面

鸡尾酒排序

为了不影响C++代码的阅读,将注释写到了Python代码里

C++代码实现

#include <iostream>
#include <vector>
using namespace std;
void bubble_sort(vector<int> &v){
    int temp;
    int n = v.size();
    //当排第n-1个数时,最后一个数已经排好,所以只需要n-1次循环,
    for(int i = 0;i < n-1;++i){  
        for(int j = 0;j < n-1-i;++j){   //除去已经排好的序列
            if(v[j] > v[j+1]) 
                swap(v[j],v[j+1]);
        }
    }
}
void cocktail_sort(vector<int> &v){
    int beg = 0;
    int end = v.size();
    while(beg < end){
        int t_beg = beg;
        int t_end = end;
        for(int i = beg;i < end;++i){
            if(v[i] > v[i+1]){
                t_end = i;
                swap(v[i],v[i+1]);
            }
        }
        if(t_end == end) break;
        end = t_end;
        for(int j = end;j > beg;--j){
            if(v[j] < v[j-1]){
                t_beg = j;
                swap(v[j],v[j-1]);
            }
        }
        if(t_beg == beg) break;
        beg = t_beg;
    }
}
int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(22);
    v.push_back(12);
    v.push_back(5); 
    cocktail_sort(v);
    for(int i = 0;i < 4;i++) cout << v[i] << endl;
    return 0;
}

Python代码实现

# 冒泡排序
def bubbleSort(seq):
    n = len(seq)
    for i in range(n-1):
        for j in range(n-i-1):
            if seq[j] > seq[j+1]:
                seq[j],seq[j+1] = seq[j+1],seq[j]
# 鸡尾酒排序(双向冒泡排序)
def cocktail_sort(seq):
    # 初始化正循环的起始位置
    beg = 0
    end = len(seq) - 1
    while beg < end:    # 正反两方向循环进行冒泡排序
        # 初始化逆循环的起始位置
        t_end = end
        t_beg = beg
        # 正向循环(beg,end),把大的数往后排
        print("beg = ",beg,"end = ",end)
        for i in range(beg,end):
            if(seq[i] > seq[i+1]):
                t_end = i
                seq[i],seq[i+1] = seq[i+1],seq[i]
        if(t_end == end):   # 判断正循环是否还进行比较,不进行则排序结束
            break
        # 一轮正循环后 待排序序列 的最后一个数确定了位置即完成"排序"
        # 那么更新排序的起止位置,即正循环(beg,t_end),逆循环(t_end,beg)
        end = t_end
        # 逆循环(end,beg),把小的数往前排
        for j in range(end,beg,-1):
            if(seq[j] < seq[j-1]):
                t_beg = j
                seq[j],seq[j-1] = seq[j-1],seq[j]
        if(t_beg == beg):   # 和正向循环同理
            break
        beg = t_beg
# 排序测试
if __name__ == '__main__':
    seq = [3,44,38,5,47,15,36,26,27,50]
    # bubbleSort(seq)
    cocktail_sort(seq)
    print(seq)

发表评论