1.冒泡排序（o(n2)） 這個演算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。 冒泡排序過程分析：把最大的放到最後 有哨兵和沒有哨兵的運行結果分析，並不是每次有哨兵的都小於沒有哨兵的，相反有哨兵 ...
1.冒泡排序（o(n2)）
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
- 針對所有的元素重覆以上的步驟，除了最後一個。
- 持續每次對越來越少的元素重覆上面的步驟，直到沒有任何一對數字需要比較。
這個演算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
/// <summary> /// 交換數據 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="data"></param> /// <param name="i"></param> /// <param name="j"></param> public static void Swap<T>(IList<T> data, int i, int j) where T:IComparable{ T temp = data[i]; data[i] = data[j]; data[j] = temp; } /// <summary> /// 冒泡排序(有哨兵) /// </summary> /// <param name="data"></param> public static void BubbleSortWithSentry<T>(IList<T> data) where T : IComparable { bool flag; for (int i = data.Count - 1; i > 0; i--) { flag = true; for (int j = 0; j < i; j++) { if (data[j].CompareTo(data[j + 1]) > 0) { Swap(data, j, j + 1); flag = false; } } if (flag) break; } } /// <summary> /// 冒泡排序 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="data"></param> public static void BubbleSort<T>(IList<T> data) where T : IComparable { for (int i = data.Count - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (data[j].CompareTo(data[j + 1]) > 0) Swap(data, j, j + 1); } } }
冒泡排序過程分析：把最大的放到最後
///運行測試
Stopwatch watch = new Stopwatch(); for (int k = 0; k < 100; k++) { Random rd = new Random(); List<int> bubbleSortData = new List<int>(); List<int> bubbleSortWithSentryData = new List<int>(); for (int i = 0; i < 100; i++) { int d = rd.Next(1000); bubbleSortData.Add(d); bubbleSortWithSentryData.Add(d); } watch.Restart(); SuanFa.BubbleSort(bubbleSortData); watch.Stop(); long bubbleSortTime = watch.ElapsedTicks; watch.Restart(); SuanFa.BubbleSortWithSentry(bubbleSortWithSentryData); watch.Stop(); long bubbleSortWithSentryTime = watch.ElapsedTicks; Console.WriteLine($"時間差: {bubbleSortWithSentryTime - bubbleSortTime}"); }
有哨兵和沒有哨兵的運行結果分析，並不是每次有哨兵的都小於沒有哨兵的，相反有哨兵的運行時間與沒有哨兵的運行時間差小於0的次數比小於50%。if運行是需要花費時間的，基本上在2個運行周期。
2.選擇排序（o(n2)）
選擇排序演算法的原理如下：
每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
/// <summary> /// 選擇排序 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="data"></param> public static void SelectSort<T>(IList<T> data) where T : IComparable { int min; for (int i = 0; i < data.Count - 1; i++) { min = i; for (int j = i + 1; j < data.Count; j++) { if (data[j].CompareTo(data[min]) < 0) min = j; } if (min != i) Swap(data, i, min); } }
選擇排序分析：把最小的放到最前面
3.插入排序（o(n2)）
插入排序有以下幾種：直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序，希爾排序（又稱縮小增量排序）
直接插入排序演算法的原理如下：
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。
/// <summary> /// 直接插入排序 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="data"></param> public static void InsertSort<T>(IList<T> data) where T : IComparable { int min; T temp; for (int i = 1; i < data.Count; i++) { temp = data[i]; min = i; for (int j = i - 1; j >= 0; j--) { if (temp.CompareTo(data[j]) >= 0) break; data[j + 1] = data[j]; min = j; } if (min != i) data[min] = temp; } }
插入排序分析：把一個數與一個已經排好的序的最大值比較，如果比最大值大直接插入，否則最大值依次後移，把索引保存，最後插入要插入的數據。
折半插入/二分插入排序的原理如下：
折半插入排序（binary insertion sort）是對插入排序演算法的一種改進，由於排序演算法過程中，就是不斷的依次將元素插入前面已排好序的序列中。由於前半部分為已排好序的數列，這樣我們不用按順序依次尋找插入點，可以採用折半查找的方法來加快尋找插入點的速度。
/// <summary> /// 折半插入/二分插入排序 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="data"></param> public static void BinaryInsertSort<T>(IList<T> data) where T : IComparable { int pre, end, mid; T temp; for (int i = 1; i < data.Count; i++) { temp = data[i]; pre = 0; end = i - 1; while (pre <= end) { mid = (pre + end) / 2; if (temp.CompareTo(data[mid]) >= 0) pre = mid + 1; else end = mid - 1; } for (int j = i; j > pre; j--) data[j] = data[j - 1]; if (pre != i) data[pre] = temp; } }
折半插入排序：折半插入排序,使用使用折半查找的方式尋找插入點的位置, 可以減少比較的次數,但移動的次數不變, 時間複雜度和空間複雜度和直接插入排序一樣，在元素較多的情況下能提高查找性能。折半插入的關鍵點在於找到插入的位置。
4.快速排序（o(nlogn)）
快速排序演算法的原理如下：
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
/// <summary> /// 快速排序 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="data"></param> public static void QuickSort<T>(IList<T> data) where T : IComparable { QuickSort(data, 0, data.Count - 1); } public static void QuickSort<T>(IList<T> data, int left, int right) where T : IComparable { if (left < right) { //取中間的元素作為比較基準，小於他的往左邊移，大於他的往右邊移 T middle = data[(left + right) / 2]; int l = left - 1; int r = right + 1; while (true) { while (data[++l].CompareTo(middle) < 0 && l < right) ; while (data[--r].CompareTo(middle) > 0 && r > 0) ; if (l >= r) break; Swap(data, l, r); } QuickSort(data, left, l - 1); QuickSort(data, r + 1, right); } }
快速排序分析：註意基準數據永遠不變，永遠是和基準數據進行比較，無論在什麼位置，最後的目的就是把基準數據放在中間，小的放左邊大的放右邊
5.歸併排序
歸併排序演算法的原理如下：
歸併排序是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。
/// <summary> /// 歸併排序 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="data"></param> public static void MergeSort<T>(IList<T> data) where T : IComparable { MergeSort(data, 0, data.Count - 1); } public static void MergeSort<T>(IList<T> data, int left, int right) where T : IComparable { if (left < right) { int mid = (left + right) / 2; MergeSort(data, left, mid); MergeSort(data, mid + 1, right); Merge(data, left, mid, right); } } private static void Merge<T>(IList<T> data, int left, int mid, int right) where T : IComparable { T[] temp = new T[data.Count]; int l = left; int m = mid + 1; int t = l; while (l <= mid && m <= right) { if (data[l].CompareTo(data[m]) <= 0) temp[t++] = data[l++]; else temp[t++] = data[m++]; } while (l <= mid) temp[t++] = data[l++]; while (m <= right) temp[t++] = data[m++]; for (int i = left; i <= right; i++) data[i] = temp[i]; }
