双端冒泡排序

要是文艺点的话，可以说是搅拌排序，通俗易懂点的话，就叫“双向冒泡排序”，我想作为码农的话，不可能不知道冒泡排序，
冒泡是一个单向的从小到大或者从大到小的交换排序，而鸡尾酒排序是双向的，从一端进行从小到大排序，从另一端进行从大
到小排序。

#include <iostream>
using namespace std;


void Swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}


void Bubble_Sort(int *arr, int length)
{
    int low,high,index;
	low = index = 0;
	high = length-1;
	while (low<high)
	{
	//最大往尾端
		for(int i = low;i<high;i++)
		{
			if(arr[i]>arr[i+1])
			{
				Swap(arr[i],arr[i+1]);
				index = i;
			}
		}
		high = index;
		//最小往前端
		for(int i = high;i>low;i--)
		{
			if(arr[i]<arr[i-1])
			{
				Swap(arr[i],arr[i-1]);
				index = i;
			}
		}
		low = index;


	}
}

 
int main()
{
    int arr[] = {8, 1, 4, 2, 9, 5, 3};
	int n = sizeof(arr)/sizeof(arr[0]);
	Bubble_Sort(arr, n);
	for(int i = 0;i<n;i++)
	{
		cout<<arr[i]<<endl;
	}
    system("pause");
    return 0;
}

最好情况时间复杂度为O(n)，最坏和平均情况时间复杂度为O(n^2)。适合数据少量，部分有序效果比较好。