Notifications
Article
冒泡排序
Published 2 months ago
63
0
代码可直接使用
把一个无序数列 {23, 34, 2, 16, 87, 98, 19, 100}从大到小排列 主要思想:把相邻的元素两两比较,当一个元素小于右侧相邻元素时,交换他们的位置;当一个元素大于或等于右侧相邻元素时,位置不变。
... ...
代码实现: static void Main(string[] args) { int[] array = new int[] { 23, 34, 2, 16, 87, 98, 19, 100 }; sort(array); for(int i = 0; i < array.Length; i++) { Console.Write("{0}\t",array[i]); } Console.Read(); } public static void sort(int[] array) { //外部循环控制所有的回合 for (int i = 0; i < array.Length - 1; i++) { //内部循环实现每一轮的冒泡处理 for (int j = 0; j < array.Length - i - 1; j++) { //先进行元素比较,再进行元素交换 if (array[j] < array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } }
1)冒泡排序的优化 例如有这样的一个数组 {9,5,8,2,6,3,7,1} 到第六轮排序后{9,8,7,6,5,3,2,1}这个数列已经有序了,但上面的排序还是会执行第7轮; 针对这种情况,对已经有序的数列添加一个标记,剩下的就不必执行。 代码实现: public static void sort(int[] array) { //外部循环控制所有的回合 for (int i = 0; i < array.Length - 1; i++) { //添加标记,初始值为true,认为当前数列为有序的 bool isSorted = true; for (int j = 0; j < array.Length - i - 1; j++) { //先进行元素比较,再进行元素交换 if (array[j] < array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; //由于有元素进行交换,可以得知刚才的假设情况是错误的,所以标记为false isSorted = false; } } //当数列已经有序,直接跳出循环 if (isSorted) break; } }
2)冒泡继续优化 例如有这样的一个数组 {7,6,5,8,9,3,2,1} 后面的3,2,1已经是有序的了,并且都比左边的其他值小,但每一轮还是会进行比较。 针对这种情况,可以在每一轮排序后,记录最后一个元素交换的位置,在该位置的后面就是有序区了。 代码实现: public static void sort(int[] array) { //记录最后一次交换的位置 int lastIndex = 0; //无序数列的边界,表示每次需要比较到的位置 int sortBorder = array.Length - 1; //外部循环控制所有的回合 for (int i = 0; i < array.Length - 1; i++) { //添加标记,初始值为true,认为当前数列为有序的 bool isSorted = true; for (int j = 0; j < sortBorder; j++) { //先进行元素比较,再进行元素交换 if (array[j] < array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; //由于有元素进行交换,可以得知刚才的假设情况是错误的,所以标记为false isSorted = false; //更新最后一次交换元素的位置 lastIndex = j; } } //更新无序数列的边界 sortBorder = lastIndex; //当数列已经有序,直接跳出循环 if (isSorted) break; } }
鸡尾酒排序 前面的排序思路都是从左到右比较元素,进行单向的位置交换的。 例如有这样的一个数组 {8, 7, 6, 5, 3, 2, 1, 9} 8,7,6,5,3,2,1已经是有序的了,但是因为是从左到右单向比较的,还是进行了7轮排序。 而鸡尾酒排序的元素比较和交换过程是双向的。(第一轮从左到右比较,第二轮改为从右到左...,当没有元素进行交换,证明已经是有序数列,排序结束)。 代码实现: public static void sort(int[] array) { int temp = 0; bool isSorted = false; //外部循环控制所有的回合,回合数除以2是每回合进行了两轮排序,从左到右,然后从右到左 for (int i = 0; i < array.Length / 2; i++) { //添加标记,初始值为true,认为当前数列为有序的 isSorted = true; //奇数轮,从左向右比较 for (int j = i; j < array.Length - i - 1; j++) { //先进行元素比较,再进行元素交换 if (array[j] < array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; //由于有元素进行交换,可以得知刚才的假设情况是错误的,所以标记为false isSorted = false; } } //当数列已经有序,直接跳出循环 if (isSorted) break; //在偶数轮时,从右向左比较,重置标记 isSorted = true; for (int j = array.Length - i - 1; j > i; j--) { if (array[j] > array[j - 1]) { temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; isSorted = false; } } //当数列已经有序,直接跳出循环 if (isSorted) break; } } 鸡尾酒排序的优点是能够在特定条件下,减少排序的回合数,但代码量增加了一倍。
Tags:
Ritern
Programmer
6
Comments