本文介绍: 从结果上面看,我们会发现,当数组有序的时候,我们还会继续往下排,知道完成 length/2 次,这个就跟没优化之前的冒泡排序一样,此时我们可以加上一个标志位 IsSorted 来判断是否已经没有交换了,如果没有,提前退出循环。冒泡是一个单向的从小到大或者从大到小的交换排序,而鸡尾酒排序是双向的,从一端进行从小到大排序,从另一端进行从大到小排序。从图中可以看到,第一次正向比较,我们找到了最大值 9.第一次反向比较,我们找到了最小值1.第二次正向比较,我们找到了次大值8.第二次反向比较,我们找到了次小值2。
通俗易懂点的话,就叫“双向冒泡排序”。
冒泡是一个单向的从小到大或者从大到小的交换排序,而鸡尾酒排序是双向的,从一端进行从小到大排序,从另一端进行从大到小排序。
从图中可以看到,第一次正向比较,我们找到了最大值 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;
}
原文地址:https://blog.csdn.net/s1t16/article/details/134640593
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_22630.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。