算法-排序-鸡尾酒排序

鸡尾酒排序本质上就是双向冒泡排序


冒泡排序(Bubble Sort)

元素分为已经排序的元素和待排序的元素,每轮排序之增加一个已经排序的元素

每轮排序都要从数组中待排序的那一端进行相邻元素的逐个比较,比较的结果是减少一个待排序元素,因此最多的比较次数将会是 (n-1)+…+1, 时间复杂度为 o(n^2)。

对于大部分有序的数组将会产生大量没有必要的比较,即当一轮比较不产生交换时说明已经全部有序,因此需要设置一个变量标识是否全部有序及时退出循环。


鸡尾酒排序(Cocktail Sort)

经典的冒泡排序实际上是单向的,而鸡尾酒排序是双向的。

但是,在鸡尾酒排序中每一轮只能在待排序元素中确定一个最大值或者最小值,在最坏情况下它并不能减少比较次数,它的时间复杂度和空间复杂度与经典的冒泡算法相同,只是在大部分有序时可能少于经典冒泡排序的比较次数。

在大部分元素无序时两种排序半斤八两。

----- For reprint please indicate the source -----
0%