鸡尾酒排序

/ 比较排序 / 0 条评论 / 60浏览

鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

目录 1 伪代码 2 与冒泡排序不同的地方 3 实现示例 3.1 C语言 3.2 C++ 3.3 Rust 3.4 JAVA 3.5 JavaScript 3.6 PHP 3.7 Python 2.7 3.8 Python 3.10 3.9 Golang 3.10 Julia (编程语言) 4 复杂度 5 外部链接 伪代码 将一个序列由小到大进行排序：

function cocktail_sort(list, list_length){ // the first element of list has index 0 bottom = 0; top = list_length - 1; swapped = true; while(swapped == true) // if no elements have been swapped, then the list is sorted { swapped = false; for(i = bottom; i < top; i = i + 1) { if(list[i] > list[i + 1]) // test whether the two elements are in the correct order { swap(list[i], list[i + 1]); // let the two elements change places swapped = true; } } // decreases top the because the element with the largest value in the unsorted // part of the list is now on the position top top = top - 1; for(i = top; i > bottom; i = i - 1) { if(list[i] < list[i - 1]) { swap(list[i], list[i - 1]); swapped = true; } } // increases bottom because the element with the smallest value in the unsorted // part of the list is now on the position bottom bottom = bottom + 1;
} } 与冒泡排序不同的地方 鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的性能，原因是冒泡排序只从一个方向进行比对（由低到高），每次循环只移动一个项目。

以序列（2,3,4,5,1）为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。但是在随机数序列的状态下，鸡尾酒排序与冒泡排序的效率与其他众多排序算法相比均比较低。

实现示例 C语言 void cocktail_sort(int arr[], int len) { int i, left = 0, right = len - 1; int temp; while (left < right) { for (i = left; i < right; i++) if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } right--; for (i = right; i > left; i--) if (arr[i - 1] > arr[i]) { temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; } left++; } } C++ template //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能 void cocktail_sort(T arr[], int len) { int j, left = 0, right = len - 1; while (left < right) { for (j = left; j < right; j++) if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]); right--; for (j = right; j > left; j--) if (arr[j - 1] > arr[j]) swap(arr[j - 1], arr[j]); left++; } } Rust fn cocktail_sort<T: PartialOrd>(arr: &mut [T]) { let mut bottom: usize = 0; let mut top = arr.len() - 1; let mut swapped = true;

while swapped {
    swapped = false;
    for i in bottom..top {
        if arr[i] > arr[i+1] {
            arr.swap(i, i+1);
            swapped = true;
        }
    }

    top -= 1;
    for j in ((bottom + 1)..=top).rev() {
        if arr[j] < arr[j - 1] {
            arr.swap(j, j - 1);
            swapped = true;
        }
    }
    bottom += 1;
}

} JAVA public static void cocktail_sort(int[] arr) { int i, left = 0, right = arr.length - 1; int temp; while (left < right) { for (i = left; i < right; i++) if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } right--; for (i = right; i > left; i--) if (arr[i - 1] > arr[i]) { temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; } left++; } } JavaScript Array.prototype.cocktail_sort = function() { var i, left = 0, right = this.length - 1; var temp; while (left < right) { for (i = left; i < right; i++) if (this[i] > this[i + 1]) { temp = this[i]; this[i] = this[i + 1]; this[i + 1] = temp; } right--; for (i = right; i > left; i--) if (this[i - 1] > this[i]) { temp = this[i]; this[i] = this[i - 1]; this[i - 1] = temp; } left++; } }; PHP function swap(&$x, &$y) { $t = $x; $x = $y; $y = $t; } function cocktail_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參才能修改原陣列 $left = 0; $right = count($arr) - 1; while ($left < $right) { for ($j = $left; $j < $right; $j++) if ($arr[$j] > $arr[$j + 1]) swap($arr[$j], $arr[$j + 1]); $right--; for ($j = $right; $j > $left; $j--) if ($arr[$j - 1] > $arr[$j]) swap($arr[$j - 1], $arr[$j]); $left++; } } Python 2.7 def cocktail_sort(l): l_len = len(l) for i in range(l_len, 0, -1): rem_i_l_len = abs(i - l_len) isNeedContinue = False obverse_count = len(l[rem_i_l_len : i-1]) reverse_count = len(l[rem_i_l_len + 1 : i-1])

    for j in range(obverse_count):
        if l[j] > l[j + 1]:
            l[j], l[j + 1] = l[j + 1], l[j]
            isNeedContinue = True
    # you can print this to observe the whole process
    # print l
    
    for j in range(reverse_count, 0, -1):
        if l[j] < l[j - 1]:
            l[j], l[j - 1] = l[j - 1], l[j]
            isNeedContinue = True
    # you can print this to observe the whole process
    # print l
    
    if isNeedContinue:
        continue
    else:
        return

if name == 'main': sample_list = [6,5,4,3,2,100] cocktail_sort(sample_list) print(sample_list) Python 3.10 def cocktail_sort(arr: list, bottom: int = None, top: int = None): if not bottom and not top: bottom, top = 0, len(arr) - 1

if bottom == top or bottom > top:
    return

swapped: bool = False
for i in range(bottom, top):
    if arr[i] > arr[i + 1]:
        arr[i + 1], arr[i] = arr[i], arr[i + 1]
        swapped = True

for i in range(top - 1, bottom, -1):
    if arr[i] < arr[i - 1]:
        arr[i - 1], arr[i] = arr[i], arr[i - 1]
        swapped = True

if not swapped:
    return

cocktail_sort(arr, bottom + 1, top - 1)

if name == 'main': sample_list = [3, 7, 5, 1, 6, 4, 8, 2] cocktail_sort(sample_list) print(sample_list) Golang func cocktailSort(arr []int) { left := 0 right := len(arr) - 1

for left < right {
	for i := left; i < right; i++ {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}
	}
	right--

	for i := right; i > left; i-- {
		if arr[i-1] > arr[i] {
			arr[i-1], arr[i] = arr[i], arr[i-1]
		}
	}
	left++
}

}

Julia (编程语言)

Julia Sample : CocktailSort

function CocktailSort(A) isordered, lo, hi = false, 1, length(A)

while !isordered && hi > lo
	isordered = true
	
	for i=lo+1:hi
		if A[i] < A[i-1]
			A[i-1], A[i] = A[i], A[i-1]
			isordered = false
		end
	end
	
	hi -= 1
	
	if isordered || hi ≤ lo 
		break 
	end

	for i in hi👎lo+1
		if A[i-1] > A[i]
			A[i-1], A[i] = A[i], A[i-1]
			isordered = false
		end
	end
	lo += 1
end
return A

end

Main Code

A = [16,586,1,31,354,43,3] println(A) # Original Array println(CocktailSort(A)) # Cocktail Sort Array 复杂度 鸡尾酒排序最糟或是平均所花费的次数都是 � ( � 2 ) O(n^{2})，但如果序列在一开始已经大部分排序过的话，会接近 � ( � ) O(n)。

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为:

↓ ← → ↑