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;
  }