C#數據結構與演算法系列（十八）：冒泡排序演算法（BubbleSort）
- 2020 年 6 月 26 日
- 筆記
- C#數據結構和演算法
1.介紹
冒泡排序的基本思想就是：通過對待排序序列從前向後（從下標較小的元素開始），依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向後部，就像水底的氣泡一樣逐漸向上冒泡。
因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下
來沒有進行過交換，就說明序列有序，因此要在排序過程中設置
一個標誌flag判斷元素是否進行過交換。從而減少不必要的比較。(這裡說的優化，可以在冒泡排序寫好後，在進行)
2.圖解
3.程式碼實現
using System; namespace DataStructure { public class BubbleSort { /// <summary> /// 測試 /// </summary> public static void Test() { int[] arr = { 3, 9, -1, 10, 20 }; Console.WriteLine("排序的數組:" + ArrayToString(arr)); Console.WriteLine("\n優化後的數組排序"); Sort(arr); Console.WriteLine("\n優化前的數組排序"); arr = new int[] { 3, 9, -1, 10, 20 }; for (int i = 0; i < arr.Length - 1 - 0; i++) { int temp = 0; if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.Console.WriteLine("\n第一次排序的結果:" + ArrayToString(arr)); for (int i = 0; i < arr.Length - 1 - 1; i++) { int temp = 0; if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.Console.WriteLine("\n第二次排序的結果:" + ArrayToString(arr)); for (int i = 0; i < arr.Length - 1 - 2; i++) { int temp = 0; if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.Console.WriteLine("\n第三次排序的結果:" + ArrayToString(arr)); for (int i = 0; i < arr.Length - 1 - 3; i++) { int temp = 0; if (arr[i] > arr[i + 1]) { temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } System.Console.WriteLine("\n第四次排序的結果:" + ArrayToString(arr)); } /// <summary> /// 將數組轉換成String /// </summary> /// <param name="arr"></param> /// <returns></returns> public static string ArrayToString(int[] arr) { string result = ""; for (int i = 0; i < arr.Length; i++) { result += arr[i] + ","; } return result; } /// <summary> /// 排序演算法優化並封裝 /// </summary> /// <param name="arr"></param> public static void Sort(int[] arr) { //標識標量，表示是否被交換過 bool flag = false; //臨時變數 int temp = 0; //要排序的次數，arr.Length-1 for (int i = 1; i < arr.Length; i++) { //第幾次排序 for (int j = 0; j < arr.Length - i; j++) { //如果前面的數大於後面的數，則交換 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } //每次排序的結果 System.Console.WriteLine("\n第" + i + "次排序的結果:" + ArrayToString(arr)); if (!flag) break; //在一趟排序中，一次交換都沒有發生過 else flag = false; //重置flag進行下次判斷 } } } }
4.結果圖
