当前位置:C++技术网 > 资讯 > 鸡尾酒排序--冒泡排序

鸡尾酒排序--冒泡排序

更新时间:2018-12-18 18:10:46浏览次数:1+次

    要是文艺点的话,可以说是搅拌排序,通俗易懂点的话,就叫“双向冒泡排序”,我想作为码农的话,不可能不知道冒泡排序,冒泡是一个单向的从小到大或者从大到小的交换排序,而鸡尾酒排序是双向的,从一端进行从小到大排序,从另一端进行从大到小排序。



从图中可以看到,第一次正向比较,我们找到了最大值9. 
                           第一次反向比较,我们找到了最小值1.
                           第二次正向比较,我们找到了次大值8.
                           第二次反向比较,我们找到了次小值2
                           。。。
                          最后就大功告成了。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml.Xsl;
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list = new List<int>() { 8, 1, 4, 2, 9, 5, 3 };
            Console.WriteLine("\n排序前 => {0}\n", string.Join(",", list));
            list = CockTailSort(list);
            Console.WriteLine("\n排序后 => {0}\n", string.Join(",", list));
            Console.Read();
        }

        /// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        static List<int> CockTailSort(List<int> list)
        {
            //因为是双向比较,所以比较次数为原来数组的1/2次即可。
            for (int i = 1; i <= list.Count / 2; i++)
            {
                //从前到后的排序 (升序)
                for (int m = i - 1; m <= list.Count - i; m++)
                {
                    //如果前面大于后面,则进行交换
                    if (m + 1 < list.Count && list[m] > list[m + 1])
                    {
                        var temp = list[m];
                        list[m] = list[m + 1];
                        list[m + 1] = temp;
                    }
                }
                Console.WriteLine("正向排序 => {0}", string.Join(",", list));
                //从后到前的排序(降序)
                for (int n = list.Count - i - 1; n >= i; n--)
                {
                    //如果前面大于后面,则进行交换
                    if (n > 0 && list[n - 1] > list[n])
                    {
                        var temp = list[n];
                        list[n] = list[n - 1];
                        list[n - 1] = temp;
                    }
                }

                Console.WriteLine("反向排序 => {0}", string.Join(",", list));
            }
            return list;
        }
    }
}

    从结果上面看,我们会发现,当数组有序的时候,我们还会继续往下排,知道完成length/2次,这个就跟没优化之前的冒泡排序一样,此时我们可以加上一个标志位IsSorted来判断是否已经没有交换了,如果没有,提前退出循环。。。

/// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        static List<int> CockTailSort(List<int> list)
        {
            //判断是否已经排序了
            var isSorted = false;

            //因为是双向比较,所以比较次数为原来数组的1/2次即可。
            for (int i = 1; i <= list.Count / 2; i++)
            {
                //从前到后的排序 (升序)
                for (int m = i - 1; m <= list.Count - i; m++)
                {
                    //如果前面大于后面,则进行交换
                    if (m + 1 < list.Count && list[m] > list[m + 1])
                    {
                        var temp = list[m];

                        list[m] = list[m + 1];

                        list[m + 1] = temp;

                        isSorted = true;
                    }
                }

                Console.WriteLine("正向排序 => {0}", string.Join(",", list));

                //从后到前的排序(降序)
                for (int n = list.Count - i - 1; n >= i; n--)
                {
                    //如果前面大于后面,则进行交换
                    if (n > 0 && list[n - 1] > list[n])
                    {
                        var temp = list[n];

                        list[n] = list[n - 1];

                        list[n - 1] = temp;

                        isSorted = true;
                    }
                }

                //当不再有排序,提前退出
                if (!isSorted)
                    break;

                Console.WriteLine("反向排序 => {0}", string.Join(",", list));
            }

            return list;
        }