冒泡排序
算法简介
冒泡排序(BubbleSort)算法：比较相邻元素的大小，如果第一个元素大于第二个元素，则交换它们的位置，然后第二个元素与第三个元素比较，直到所有的元素比较完，冒泡出最小的元素。假设我们有n各元素，那么我们就要进行 n-1 次冒泡，n-1 个最小的元素已经冒泡出来，因此，最后剩下的一个元素也就处于它应当处于的位置。
本篇文章主要是对冒泡排序进行优化，使其避免不必要的比较，以及泛型的实现，共分四个版本。
先来看一张直观的图：
第一版
static int FirstVersionBubbleSort(int[] array) { int count = array.Length - 1; int number = 0; for (int i = 0; i < count; i++) { for (int j = 0; j < count - i; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } number++; } } return number; }
外层循环用来控制冒泡的次数，内层循环用来比较相邻元素的大小。number 用来记录总共进行了几次比较，为后面的优化版本做对比。
执行 Main():
int[] firstArray = { 2, 1, 3, 4 }; Console.WriteLine("总共比较的次数:{0}", FirstVersionBubbleSort(firstArray)); foreach (var item in firstArray) { Console.Write(item.ToString().PadRight(2)); }
总共比较的次数:6 1 2 3 4
总共比较了6次，分别是：
第一次冒泡出 4:
2-1：1 2 3 4
2-3：1 2 3 4
3-4 : 1 2 3 4
第二次冒泡 3:
1-2 : 1 2 3 4
2-3 : 1 2 3 4
第三次冒泡 2:
1-2 : 1 2 3 4
看一下上面的过程，就很容想到，当整个数列已经排好序后我们就没有必要再做多余的比较。用一个标志量来表示上次是否内层循环是否有元素交换，如果有则进行下一次循环，否则退出，因为所有元素已经有序。
第二版
static int SecondVersionBubbleSort(int[] array) { int count = array.Length; bool change; int number = 0; do { count--; change = false; for(int i = 0; i < count; i++) { if(array[i] > array[i + 1]) { int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; change = true; } number++; } }while(change); return number; }
执行Main():
int[] secondArray= { 2, 1, 3, 4 }; Console.WriteLine(" 总共比较的次数:{0}", SecondVersionBubbleSort(secondArray)); foreach (var item in secondArray) { Console.Write(item.ToString().PadRight(2)); }
总共比较的次数:5 1 2 3 4
总共比较了5次，分别是：
第一次冒泡出 4:
2-1：1 2 3 4
2-3：1 2 3 4
3-4 : 1 2 3 4
此时 change 为 true
第二次冒泡 3:
1-2 : 1 2 3 4
2-3 : 1 2 3 4
发现已经有序，change 为 false， 结束冒泡。再继续思考，事实上，第一次冒泡后，2、3、4 已经有序，因此下次循环完全没有必要再继续对其比较；现在我们增加一个位置变量来记录每次冒泡的最后交换的位置，下次比较的此处就可以了，避免对后面已经有序的元素重复进行比较。
static int ThirdVersionBubbleSort(int[] array) { int count = array.Length - 1, index = 0; bool change; int number = 0; do { change = false; for (int i = 0; i < count; i++) { if (array[i] > array[i + 1]) { int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; change = true; index = i; // 记录最后一次交换的位置 } number++; } count = index; } while (change); return number; }
执行 Main():
int[] thirdArray = { 2, 1, 3, 4 }; Console.WriteLine(" 总共比较的次数:{0}", ThirdVersionBubbleSort(thirdArray)); foreach (var item in thirdArray) { Console.Write(item.ToString().PadRight(2)); }
总共比较的次数:3 1 2 3 4
有上面的结果，可以看到，这次只进行了 3 次比较，分别如下：
总共比较了3次，分别是：
第一次冒泡出 4:
2-1：1 2 3 4
2-3：1 2 3 4
3-4 : 1 2 3 4
此时 index 为 0， count 为 0，结束冒泡。可见，这种方式，可以大大降低比较的次数。
第四版
如果说继承是为我们提供了代码重用，那么泛型则为我们提供了算法的重用。下面我们将实现一个泛型版本的冒泡排序。
public static int FourthVersionBubbleSort<T>(List<T> list) where T:IComparable<T> { int count = list.Count - 1, index = 0; bool change; int number = 0; do { change = false; for (int i = 0; i < count; i++) { if (list[i].CompareTo(list[i + 1]) > 0) { T temp = list[i]; list[i] = list[i + 1]; list[i + 1] = temp; change = true; index = i; // 记录最后一次交换的位置 } number++; } count = index; } while (change); return number; }
执行 Main():
List<string> stringList = new List<string> { "Banana", "Apple", "Orange" }; Console.WriteLine("总共比较的次数:{0}", FourthVersionBubbleSort(stringList)); foreach (var item in stringList) { Console.Write(item.ToString().PadRight(10)); }
总共比较的次数:2
Apple Banana Orange
结束语
冒泡排序最优时间复杂度为(即所有元素有序，只需遍历一次即可) O(n)，最差时间复杂度为 O(n^2)， 即当所有元素为逆序时。