「雞尾酒排序」不會？每天一遍，排序再見【超詳細】

🌟 前言

大家好，我是Edison😎

之前有寫過一篇關于「冒泡排序」的文章；

但是冒泡排序的實作仍然不是最優，有一種排序演算法叫做 「雞尾酒排序」；

雞尾酒排序是基于冒泡排序的一種升級；

今天這篇文章就是關于 「雞尾酒排序」 的詳細介紹；

Let‘s get it！

🛫送所有正在努力的大家一句話：你不一定逆風翻盤，但一定要向陽而生🌅

🔥熱榜必看文章：室友打一把王者就學會了冒泡排序演算法

1. 基本思想

雞尾酒排序又叫「快樂小時排序」；它基于冒泡排序做了一點小小優化；

讓我們首先來回顧一下冒泡排序的思想：

冒泡排序的每?個元素都可以像??泡?樣，根據????，?點?點地向著陣列的?側移動，

演算法的每?輪都是從左到右來?較元素， 進?單向的位置交換的 ，

那么雞尾酒排序做了怎樣的優化呢？

雞尾酒排序的元素比較和交換程序是雙向的

2. 圖解示例

讓我們來舉一個栗子：

有8個陣列成一個無序數列：2，3，4，5，6，7，8，1，希望從小到大排序，

如果按照冒泡排序的思想，排序的程序是什么樣呢？

🍑 冒泡程序

第一輪結果（8和1交換）

第二輪結果（7和1交換）

第三輪結果（6和1交換）

第四輪結果（5和1交換）

第五輪結果（4和1交換）

第六輪結果（3和1交換）

第七輪結果（2和1交換）

那么冒泡排序有什么問題呢？？？

由上面可以看出，從2到8已經是有序了，只有元素1的位置不對，卻還要進行7輪排序，太麻煩了吧？

那我們的雞尾酒排序正是要解決這種問題，讓我們來看一看雞尾酒排序的程序吧，

🍑 雞尾酒程序

雞尾酒排序是什么樣子呢？讓我們來看一看詳細程序：

第一輪（和冒泡排序一樣，8和1交換）

第二輪

此時開始不一樣了，我們反過來從右往左比較和交換：

8已經處于有序區，我們忽略掉8，讓1和7比較，元素1小于7，所以1和7交換位置：

接下來1和6比較，元素1小于6，所以1和6交換位置：

接下來1和5比較，元素1小于5，所以1和5交換位置：

接下來1和4交換，1和3交換，1和2交換，最終成為了下面的結果：

第三輪

雖然已經有序，但是流程并沒有結束；

1和2比較，位置不變；2和3比較，位置不變；3和4比較，位置不變…6和7比較，位置不變；

沒有元素位置交換，證明已經有序，排序結束，

這就是雞尾酒排序的思路，

排序程序就像大擺錘一樣，第一輪從左到右，第二輪從右到左，第三輪再從左到右…

3. 動圖演示

我們先來看個「雞尾酒排序」的動圖吧

剛剛的「雞尾酒排序」程序，我們也可以用動圖演示👇

第一輪操作（ 8 和 1 交換 ）

第二輪操作 ( 從序列右邊開始遍歷 ）

第三輪操作 ( 從左向右比較和交換 )

4. 代碼實作

📃 代碼示例

void Cocktail_Sort(int arr[], int sz)
{
	int tmp = 0;
	int left = 0;
	int right = sz - 1;
	for (int i = 0; i < sz / 2; i++)
	{
		//有序標記，每一輪的初始是true
		int flag = 1;

		//奇數輪，從左向右比較和交換
		for (int j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;

				//有元素交換，所以不是有序，標記變為0
				flag = 0;
			}
		}

		if (flag)
			break;

		//偶數輪之前，重新標記為1
		flag = 1;

		//偶數輪，從右向左比較和交換
		for (int j = sz - i - 1; j > i; j--)
		{
			if (arr[j] < arr[j - 1])
			{
				tmp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tmp;

				//有元素交換，所以不是有序，標記變為0
				flag = 0;
			}
		}

		if (flag)
			break;
	}
}

void Cocktail_Show(int arr[], int sz)
{
	int i = 0;

	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[] = { 2,3,4,5,6,7,8,1 };
	int sz = sizeof(arr) / sizeof(int);

	printf("排序前:");
	Cocktail_Show(arr, sz);//列印排序函式

	Cocktail_Sort(arr, sz);//排序函式

	printf("排序后:");
	Cocktail_Show(arr, sz);

	return 0;
}

這段代碼是雞尾酒排序的原始實作，

代碼外層的大回圈控制著所有排序回合，大回圈內包含兩個小回圈；

第一個回圈從左向右比較并交換元素，第二個回圈從右向左比較并交換元素，

5. 代碼優化

上次介紹冒泡排序的時候，有一種針對有序區間的優化，那么我們的雞尾酒排序也可以根據這個思路來進行優化；

讓我們來回顧一下冒泡排序針對有序區的優化思路：

原始的冒泡排序，有序區的長度和排序的輪數是相等的，

比如第一輪排序過后的有序區長度是1，第二輪排序過后的有序區長度是2 …

要想優化，我們可以在每一輪排序的最后，記錄下最后一次元素交換的位置，那個位置也就是無序數列的邊界，再往后就是有序區了，

對于單向的冒泡排序，我們需要設定一個邊界值；

對于雙向的雞尾酒排序，我們需要設定兩個邊界值，請看代碼：

void Cocktail_Sort(int arr[], int sz)
{
	int tmp = 0;

	//無序數列的左邊界，每次比較只需要比到這里為止
	int leftBorder = 0;

	//無序數列的右邊界，每次比較只需要比到這里為止
	int rightBorder = sz - 1;

	//記錄右側最后一次交換的位置
	int lastRightExchange = 0;

	//記錄左側最后一次交換的位置
	int lastLeftExchange = 0;

	for (int i = 0; i < sz / 2; i++)
	{
		//有序標記，每一輪的初始是true
		int flag = 1;

		//奇數輪，從左向右比較和交換
		for (int j = leftBorder; j < rightBorder; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;

				//有元素交換，所以不是有序，標記變為0
				flag = 0;
				lastRightExchange = j;
			}
		}

		rightBorder = lastRightExchange;
		if (flag)
			break;

		//偶數輪之前，重新標記為1
		flag = 1;

		//偶數輪，從右向左比較和交換
		for (int j = rightBorder; j > leftBorder; j--)
		{
			if (arr[j] < arr[j - 1])
			{
				tmp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = tmp;

				//有元素交換，所以不是有序，標記變為0
				flag = 0;
				lastLeftExchange = j;
			}
		}
		leftBorder = lastLeftExchange;
		if (flag)
			break;
	}
}

代碼解釋👇

代碼中使用了左右兩個邊界值，rightSortBorder 代表右邊界，leftSortBorder 代表左邊界，

在比較和交換元素時，奇數輪從leftSortBorder 遍歷到 rightSortBorder 位置；

偶數輪從 rightSortBorder 遍歷到 leftSortBorder 位置，

6. 特性總結

時間復雜度：同冒泡排序，為 O ( n 2 ) O(n2) O(n2)

空間復雜度：同冒泡排序，為 O ( 1 ) O(1) O(1)

優點：能夠在特定的條件下，減少排序的回合數；

缺點：代碼量幾乎擴大了一倍；

適用場景：大部分元素已經是有序的情況下，使用「雞尾酒排序」會更好；

總結

🤗作者水平有限，如有總結不對的地方，歡迎留言或者私信！

💕如果你覺得這篇文章還不錯的話，那么點贊👍、評論💬、收藏🤞就是對我最大的支持！

🌟你知道的越多，你不知道越多，我們下期見！