「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

???? 前言

大家好,我是Edison????

之前有写过一篇关于「冒泡排序」的文章;但是冒泡排序的实现仍然不是最优,有一种排序算法叫做 「鸡尾酒排序」

鸡尾酒排序是基于冒泡排序的一种升级;

今天这篇文章就是关于 「鸡尾酒排序」 的详细介绍;Let‘s get it!

????送所有正在努力的大家一句话:你不一定逆风翻盘,但一定要向阳而生????

 

????热榜必看文章:室友打一把王者就学会了冒泡排序算法

文章目录

1. 基本思想

鸡尾酒排序又叫「快乐小时排序」;它基于冒泡排序做了一点小小优化;

让我们首先来回顾一下冒泡排序的思想:

冒泡排序的每⼀个元素都可以像⼩⽓泡⼀样,根据⾃⾝⼤⼩,⼀点⼀点地向着数组的⼀侧移动。

算法的每⼀轮都是从左到右来⽐较元素, 进⾏单向的位置交换的 。

那么鸡尾酒排序做了怎样的优化呢?

鸡尾酒排序的元素比较和交换过程是双向

2. 图解示例

让我们来举一个栗子:

有8个数组成一个无序数列:2,3,4,5,6,7,8,1,希望从小到大排序。

 

如果按照冒泡排序的思想,排序的过程是什么样呢?

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

???? 冒泡过程

第一轮结果(8和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第二轮结果(7和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第三轮结果(6和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第四轮结果(5和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第五轮结果(4和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第六轮结果(3和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第七轮结果(2和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

那么冒泡排序有什么问题呢???

由上面可以看出,从2到8已经是有序了。只有元素1的位置不对,却还要进行7轮排序,太麻烦了吧?

 

那我们的鸡尾酒排序正是要解决这种问题,让我们来看一看鸡尾酒排序的过程吧。

???? 鸡尾酒过程

鸡尾酒排序是什么样子呢?让我们来看一看详细过程:

第一轮(和冒泡排序一样,8和1交换)

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第二轮

此时开始不一样了,我们反过来从右往左比较和交换:

 

8已经处于有序区,我们忽略掉8让1和7比较元素1小于7,所以1和7交换位置:

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

接下来1和6比较元素1小于6,所以1和6交换位置:

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

接下来1和5比较元素1小于5,所以1和5交换位置:

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

接下来1和4交换1和3交换1和2交换,最终成为了下面的结果:

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第三轮

虽然已经有序,但是流程并没有结束;

 

1和2比较,位置不变;2和3比较,位置不变;3和4比较,位置不变…6和7比较,位置不变;

 

没有元素位置交换,证明已经有序,排序结束。

这就是鸡尾酒排序的思路。

排序过程就像大摆锤一样,第一轮从左到右第二轮从右到左第三轮再从左到右

3. 动图演示

我们先来看个「鸡尾酒排序」的动图吧

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

刚刚的「鸡尾酒排序」过程,我们也可以用动图演示????

第一轮操作( 8 和 1 交换 )

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第二轮操作 ( 从序列右边开始遍历 )

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

第三轮操作 ( 从左向右比较和交换 )

「鸡尾酒排序」不会?每天一遍,排序再见【超详细】

4. 代码实现

???? 代码示例

void Cocktail_Sort(int arr[], int sz)
{
    int tmp = 0;
    int left = 0;
    int right = sz - 1;
    for (int i = 0; i < sz / 2; i++)
    {
        //有序标记,每一轮的初始是true
        int flag = 1;

        //奇数轮,从左向右比较和交换
        for (int j = 0; j < sz - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;

                //有元素交换,所以不是有序,标记变为0
                flag = 0;
            }
        }

        if (flag)
            break;

        //偶数轮之前,重新标记为1
        flag = 1;

        //偶数轮,从右向左比较和交换
        for (int j = sz - i - 1; j > i; j--)
        {
            if (arr[j] < arr[j - 1])
            {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;

                //有元素交换,所以不是有序,标记变为0
                flag = 0;
            }
        }

        if (flag)
            break;
    }
}

void Cocktail_Show(int arr[], int sz)
{
    int i = 0;

    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] = { 2,3,4,5,6,7,8,1 };
    int sz = sizeof(arr) / sizeof(int);

    printf("排序前:");
    Cocktail_Show(arr, sz);//打印排序函数

    Cocktail_Sort(arr, sz);//排序函数

    printf("排序后:");
    Cocktail_Show(arr, sz);

    return 0;
}

这段代码是鸡尾酒排序的原始实现。

代码外层的大循环控制着所有排序回合,大循环内包含两个小循环;

 

第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。

5. 代码优化

上次介绍冒泡排序的时候,有一种针对有序区间的优化,那么我们的鸡尾酒排序也可以根据这个思路来进行优化;

让我们来回顾一下冒泡排序针对有序区的优化思路:

原始的冒泡排序,有序区的长度和排序的轮数是相等的。

比如第一轮排序过后的有序区长度是1,第二轮排序过后的有序区长度是2 …

要想优化,我们可以在每一轮排序的最后,记录下最后一次元素交换的位置,那个位置也就是无序数列的边界,再往后就是有序区了。

对于单向的冒泡排序,我们需要设置一个边界值;

对于双向的鸡尾酒排序,我们需要设置两个边界值。请看代码:

void Cocktail_Sort(int arr[], int sz)
{
    int tmp = 0;

    //无序数列的左边界,每次比较只需要比到这里为止
    int leftBorder = 0;

    //无序数列的右边界,每次比较只需要比到这里为止
    int rightBorder = sz - 1;

    //记录右侧最后一次交换的位置
    int lastRightExchange = 0;

    //记录左侧最后一次交换的位置
    int lastLeftExchange = 0;

    for (int i = 0; i < sz / 2; i++)
    {
        //有序标记,每一轮的初始是true
        int flag = 1;

        //奇数轮,从左向右比较和交换
        for (int j = leftBorder; j < rightBorder; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;

                //有元素交换,所以不是有序,标记变为0
                flag = 0;
                lastRightExchange = j;
            }
        }

        rightBorder = lastRightExchange;
        if (flag)
            break;

        //偶数轮之前,重新标记为1
        flag = 1;

        //偶数轮,从右向左比较和交换
        for (int j = rightBorder; j > leftBorder; j--)
        {
            if (arr[j] < arr[j - 1])
            {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;

                //有元素交换,所以不是有序,标记变为0
                flag = 0;
                lastLeftExchange = j;
            }
        }
        leftBorder = lastLeftExchange;
        if (flag)
            break;
    }
}

代码解释????

代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder 代表左边界。

比较交换元素时,奇数轮leftSortBorder 遍历到 rightSortBorder 位置;

偶数轮rightSortBorder 遍历到 leftSortBorder 位置。

6. 特性总结

时间复杂度:同冒泡排序,为 O ( n ² ) O(n²) O(n²)

空间复杂度:同冒泡排序,为 O ( 1 ) O(1) O(1)

优点:能够在特定的条件下,减少排序的回合数;

缺点:代码量几乎扩大了一倍;

适用场景:大部分元素已经是有序的情况下,使用「鸡尾酒排序」会更好;

总结

????作者水平有限,如有总结不对的地方,欢迎留言或者私信!

 

????如果你觉得这篇文章还不错的话,那么点赞????、评论????、收藏????就是对我最大的支持!

 

????你知道的越多,你不知道越多,我们下期见!

上一篇:什么?你竟然还不知道「无影」?


下一篇:《c# 实现p2p文件分享与传输系统》 二、 设计