C# 實(shí)現(xiàn)經(jīng)典排序算法
using ElementType = System.Int32; // 頂部添加此行,為待排元素的數(shù)據(jù)類(lèi)型起別名(以 Int32 為例)
插入排序
- 直接插入排序
public static void StraightInsertSorting(ElementType[] list) { var flag = 0; // 存儲(chǔ)需要進(jìn)行插入的值 for (int i = 1; i < list.Length; i++) { // 判斷是否需要向前插入 if (list[i] < list[i-1]) { flag = list[i]; // 將要插入的值存儲(chǔ)下來(lái) list[i] = list[i - 1]; // list[i] 已確定要向前插入笤休,因此list[i-1]可向后挪一位 // 尋找目標(biāo)位置 int j; for (j = i - 2; j >= 0 && list[j] > flag; j--) { list[j + 1] = list[j]; } // 找到目標(biāo)位置建峭,插入 if (j + 1 >= 0) { list[j + 1] = flag; } } } }
交換排序
-
冒泡排序
public static void BubbleSort(ElementType[] list) { var changed = true; // i 為窗口大小值,即需要進(jìn)行相鄰比較的次數(shù) // list[0] 需要進(jìn)行 n-1 次; list[1]: n-2; list[n-1]: 1 // 因此 i 從 n-1 開(kāi)始依次遞減启泣,直至 i 為 0 for (int i = list.Length-1; i > 0 && changed; i--) { changed = false; // 相鄰元素的比較與交換操作 // 只要進(jìn)行了交換涣脚,則 changed 置為 true, 否則表明當(dāng)前序列已滿(mǎn)足非降序排列,不用再進(jìn)入后續(xù)循環(huán) for (int j = 0; j < i; j++) { if (list[j] > list[j + 1]) { Swap(ref list[j], ref list[j+1]); changed = true; } } } } private static void Swap(ref ElementType a, ref ElementType b) { var temp = a; a = b; b = temp; }
-
快速排序
public static void QuickSort(ElementType[] list) { // low: 0, high: n-1 QSort(list, 0, list.Length - 1); } private static void QSort(ElementType[] list, int low, int high) { if (high <= low) { return; } // 一分為二寥茫,分別快排 var pivotIndex = Partition(list, low, high); QSort(list, low, pivotIndex - 1); QSort(list, pivotIndex + 1, high); } private static int Partition(ElementType[] list, int low, int high) { var pivot = list[low]; // 樞紐元素 while (low < high) { // 只要 high 指向的元素值不小于 pivot遣蚀,就繼續(xù)向前移動(dòng) while (low < high && list[high] >= pivot) { high--; } // 直至找到某元素的值小于 pivot,則應(yīng)該將其置于 low 區(qū)域 list[low] = list[high]; // 只要 low 指向的元素值不大于 pivot纱耻,就繼續(xù)向后移動(dòng) while (low < high && list[low] <= pivot) { low++; } // 直至找到某元素的值大于 pivot芭梯,則應(yīng)置于 high 區(qū)域 list[high] = list[low]; } list[low] = pivot; // 將樞紐元素歸位,其左邊均為不大于它的元素膝迎,右邊均為不小于它的元素 return low; // 返回樞紐元素的下標(biāo) }
選擇排序
-
簡(jiǎn)單選擇排序
public static void SimpleSelectionSort(ElementType[] list) { for (int i = 0; i < list.Length; i++) { // 挑出 list[i] 至 list[n-1] 中值最小的元素下標(biāo) var minElemIndex = SelectMinElemIndex(list, i); // 將當(dāng)前元素 list[i] 與最小元素進(jìn)行交換 if (minElemIndex >= 0 && minElemIndex != i) { Swap(ref list[minElemIndex], ref list[i]); } } } private static int SelectMinElemIndex(ElementType[] list, int offset) { if (offset >= list.Length) { return -1; } // 最小值下標(biāo)默認(rèn)為 i 的起始值 var minElemIndex = offset; for (int i = offset; i < list.Length; i++) { // 若當(dāng)前元素的值更小粥帚,則更新最小值下標(biāo) if (list[i] < list[minElemIndex]) { minElemIndex = i; } } return minElemIndex; }
-
堆排序
public static void HeapSort(ElementType[] input) { // 創(chuàng)建堆空間,增加 1 空閑元素限次,使各元素的下標(biāo)芒涡,與其作為完全二叉樹(shù)節(jié)點(diǎn)的編號(hào)相同 HeapType[] h = new HeapType[input.Length + 1]; for (int i = 0; i < input.Length; i++) { h[i + 1] = input[i]; } // 構(gòu)建大頂堆, 從第一個(gè)非終端節(jié)點(diǎn)(因?yàn)橐袛嗯c其左右孩子的大小關(guān)系)開(kāi)始向前調(diào)整 for (int i = h.Length / 2; i > 0; i--) { HeapFilter(h, i, h.Length - 1); } // 將最大元素交換至末端后,對(duì)其之前的元素再次構(gòu)建大頂堆 // 保證每次交換至末端的都是范圍內(nèi)最大的元素 for (int i = h.Length - 1; i > 0; i--) { Swap(ref h[i], ref h[1]); HeapFilter(h, 1, i - 1); } // 將排序結(jié)果輸出至原數(shù)組中 for (int i = 0; i < input.Length; i++) { input[i] = h[i + 1]; } } // 篩選卖漫,構(gòu)建大頂堆 private static void HeapFilter(HeapType[] h, int insertPos, int end) { var insertedValue = h[insertPos]; int maxChildIndex; for (maxChildIndex = insertPos * 2; maxChildIndex <= end; maxChildIndex *= 2) { // 找到較大的孩子 if (maxChildIndex < end && h[maxChildIndex] < h[maxChildIndex+1]) { maxChildIndex = maxChildIndex + 1; } // 與較大的孩子比較费尽,若雙親較大,符合大頂堆羊始,則不用調(diào)整 if (insertedValue >= h[maxChildIndex]) { break; } // 若雙親較小旱幼,則將較大的孩子放至雙親的當(dāng)前位置 h[insertPos] = h[maxChildIndex]; // 記錄下最大值的節(jié)點(diǎn)位置,并進(jìn)一步迭代突委,確保該節(jié)點(diǎn)及其孩子構(gòu)成的序列也是大頂堆 insertPos = maxChildIndex; } h[insertPos] = insertedValue; }