这篇我们来聊一下鸡尾酒排序,为了知道为啥取名为鸡尾酒,特意看了下百科,见框框的话,也只能勉强这么说了。
要是文艺点的话,可以说是搅拌排序,通俗易懂点的话,就叫“双向冒泡排序”,我想作为码农的话,不可能不知道冒泡排序,冒泡是一个单向的从小到大或者从大到小的交换排序,而鸡尾酒排序是双向的,从一端进行从小到大排序,从另一端进行从大到小排序。
从图中可以看到:
-
第一次正向比较,我们找到了最大值 9.
-
第一次反向比较,我们找到了最小值 1.
-
第二次正向比较,我们找到了次大值 8.
-
第二次反向比较,我们找到了次小值 2
-
。。。
-
最后就大功告成了。
下面我们看看代码:
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
List list = new List() { 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();
}
///
/// 鸡尾酒排序
///
///
///
static List CockTailSort(List list)
{
//因为是双向比较,所以比较次数为原来数组的1/2次即可。
for (int i = 1; i = 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 来判断是否已经没有交换了,如果没有,提前退出循环。。。
///
/// 鸡尾酒排序
///
///
///
static List CockTailSort(List list)
{
//判断是否已经排序了
var isSorted = false;
//因为是双向比较,所以比较次数为原来数组的1/2次即可。
for (int i = 1; i = 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;
}
好了,这样就比较完美了,希望本篇对您有帮助。