鸡尾酒排序

作者: 兔爷爱吃炸酱面 | 来源:发表于2014-08-01 20:19 被阅读300次

    鸡尾酒排序

    @(F1 - 算法学习)[排序|noteton]

    WIKI上的定义

    鸡尾酒排序,也就是定向冒泡排序、鸡尾酒搅拌排序、搅拌排序(也可以视作选择排序的一种排序)、涟漪排序、来回排序或者快乐小时排序,是冒泡排序的一种变形。与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

    Sorting_shaker_sort_anim.gif
    分类 排序算法
    数据结构 数组
    最差时间复杂度
    最优时间复杂度
    平均时间复杂度

    与冒泡排序不同的地方

    鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低(有先后顺序,并非同时;大循环下第一个循环是从开始扫到结束,将最大的归到最后;第二个循环是从倒数第二个位置往开始端扫,将最小的归到开始的位置),而冒泡排序则仅仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次只移动一个项目和。
      以排序(2,3,4,5,1)为例,鸡尾酒排序只要访问一次序列就可以完成排序,但如果使用冒泡排序需要四次。但是在乱数序列的状态下,鸡尾酒排序和冒泡排序的效率都很差。

    伪代码

    function cocktail_sort(list, list_length){ // the first element of list has index 0
        bottom = 0;
        top = list_length - 1;
        swapped = true; 
        while(swapped == true) // if no elements have been swapped, then the list is sorted
        {
            swapped = false; 
            for(i = bottom; i < top; i = i + 1)
            {
                if(list[i] > list[i + 1])  // test whether the two elements are in the correct order
                {
                    swap(list[i], list[i + 1]); // let the two elements change places
                    swapped = true;
                }
            }
            // decreases top the because the element with the largest value in the unsorted
            // part of the list is now on the position top 
            top = top - 1; 
            for(i = top; i > bottom; i = i - 1)
            {
                if(list[i] < list[i - 1]) 
                {
                    swap(list[i], list[i - 1]);
                    swapped = true;
                }
            }
            // increases bottom because the element with the smallest value in the unsorted 
            // part of the list is now on the position bottom 
            bottom = bottom + 1;  
        }
    }
    

    Java实现

    /**
         * 鸡尾酒排序法
         * 
         * @param a
         *            指定整型数组
         */
        public void sort(int[] a) {
            //需要来回a,length/2趟
            for (int i = 0; i < a.length / 2; i++) {
                //类冒泡,交换最大值至右端
                for (int j = i; 1 + j < a.length - i; j++)
                    if (a[j] > a[1 + j])
                        Arr.swap(a, j, 1 + j);
                //类冒泡,交换最小值至左端
                for (int j = a.length - i - 1; j > i; j--)
                    if (a[j - 1] > a[j])
                        Arr.swap(a, j - 1, j);
            }
        }
    

    注意看这里的代码实现,没有了状态变量sorted,最外面的while循环也被替代成确定length/2趟的for循环,因为循环内有两个for各分担饿了一般的工作,所以,大循环只需要进行一半。这个在代码的具体实现时看具体情况吧,如果分析不清楚,就用伪代码中的设置状态变量也未尝不可。PS,伪代码要像思维导图一样逼着自己先写着!

    C实现

    #include<stdio.h>
    #include<stdbool.h>
    void swap(int *a ,int *b);
    int main()
    {
        int a[] = {4,3,1,6,5,7,2,9,8};
        bool sorted = true;
        int length = sizeof(a) / sizeof(a[0]);
        int top = length - 1;
        int bottom = 0;
        int tmp = 0;
        while (sorted)
        {
            sorted = false;
            for (int i = bottom; i < top; i++)
            {
                if (a[i]<a[i - 1])
                {
                    swap(&a[i], &a[i - 1]);
                    /*
                    {
                        tmp=a[i];
                        a[i] = a[i - 1];
                        a[i - 1] = tmp;
                    }
                    */
                    sorted = true;
                }
            }
            top--;
            for ( int i = top; i >bottom; i--)
            {
                if (a[i]>a[i + 1])
                {
                    swap(&a[i], &a[i + 1]);
                    /*
                    {
                        tmp = a[i];
                        a[i] = a[i + 1];
                        a[i + 1] = tmp;
                    }
                    */
                    sorted = true;
                }
            }
            bottom++;
        }
        for (int i = 0; i < length; i++)
        {
            printf("%d", a[i]);
        }
    }
    
    void swap(int *a, int *b)
    {
        int tmp = 0;
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
    

    相关文章

      网友评论

        本文标题:鸡尾酒排序

        本文链接:https://www.haomeiwen.com/subject/pinstttx.html