经典算法题每日演练——第二十三题 鸡尾酒排序

  1. 云栖社区>
  2. 博客>
  3. 正文

经典算法题每日演练——第二十三题 鸡尾酒排序

一线码农 2016-04-12 16:19:37 浏览999
展开阅读全文


这篇我们继续扯淡一下鸡尾酒排序,为了知道为啥取名为鸡尾酒,特意看了下百科,见框框的话,也只能勉强这么说了。

 

要是文艺点的话,可以说是搅拌排序,通俗易懂点的话,就叫“双向冒泡排序”,我想作为码农的话,不可能不知道冒泡排序,

冒泡是一个单向的从小到大或者从大到小的交换排序,而鸡尾酒排序是双向的,从一端进行从小到大排序,从另一端进行从大

到小排序。

从图中可以看到,第一次正向比较,我们找到了最大值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;
        }

网友评论

登录后评论
0/500
评论
一线码农
+ 关注