另一个冒泡排序优化——鸡尾酒排序

From: [Wikipedia 鸡尾酒排序] :

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

原理类似冒泡排序。一次循环中，先从前往后把大数冒上去，再从后往前把小数冒回来。比起基本的冒泡排序，从两端缩小未排序范围更有效率。

排序50000个随机数，与上次写的冒泡排序的比较：冒泡排序—5.79s    鸡尾酒排序—4.05s

以下是Pascal代码，和上次写的冒泡排序用一样的优化。为了简洁，只给出排序函数，swaplnt是交换变量函数，省略了。用法：cocktailsort (长整形数组, 待排序区域下界, 上界)。

procedure cocktailsort (var a: array of longint;  down, up: longint);
	var
		j, lastswp: longint;
		swapped: boolean;
	begin
		repeat
			swapped := false;

			lastswp := 0;
			for j := down to up-1 do
				if a[j] > a[j+1] then
				begin
					swaplint(a[j], a[j+1]);
					lastswp := j;
				end;

			if lastswp <> 0 then
			begin
				up := lastswp;
				swapped := true;
			end;

			lastswp := 0;
			for j := up downto down+1 do
				if a[j] < a[j-1] then
				begin
					swaplint(a[j], a[j-1]);
					lastswp := j;
				end;

			if lastswp <> 0 then
			begin
				down := lastswp;
				swapped := true;
			end;
		until not(swapped);
	end;