鸡尾酒排序含义及代码示例
代码示例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace Sort { class CockTailSorter { private static int[] myArray; private static int arraySize;
public static int[] Sort(int[] myArray) { arraySize = myArray.Length; CockTailSort(myArray); return myArray; }
public static void CockTailSort(int[] myArray) { int low, up, index, i; low = 0;//数组起始索引 up = myArray.Length - 1;//数组索引最大值 index = low;//临时变量 //判断数组中是否有多个元素 while (up > low)//每一次进入while循环都会找出相应范围内最大最小的元素并分别放到相应的位置 { //进入该for循环会将索引限定范围内最大的元素放到最右边 for (i = low; i < up; i++) { if (myArray[i] > myArray[i + 1]) { Swap(ref myArray[i], ref myArray[i + 1]); index = i;//记录当前索引 } } up = index;//记录最后一个交换的位置 //进入该for循环会将索引限定范围内最小的元素放到最左边 for (i = up; i > low; i--) { if (myArray[i] < myArray[i - 1]) { Swap(ref myArray[i], ref myArray[i - 1]); index = i; } } low = index;//记录最后一个交换的位置 } }
private static void Swap(ref int left, ref int right) { int temp; temp = left; left = right; right = temp; }
} }
|
思想
鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。
使用鸡尾酒排序,数组中的数字本是无规律的排放,先找到最小的数字,把他放到第一位,然后找到最大的数字放到最后一位。然后再找到第二小的数字放到第二位,再找到第二大的数字放到倒数第二位。以此类推,直到完成排序。
复杂度
时间复杂度
鸡尾酒排序最糟或是平均所花费的次数都是O(n²),但如果序列在一开始已经大部分排序过的话,会接近O(n)。
空间复杂度
平均的空间复杂度为:O(1)
稳定性
稳定