排序演算法整理

資料結構系列
約 5 分鐘閱讀

插入排序(Insertion Sort)

插入排序就像是打撲克牌時，整理牌組的順序

插入排序演示

insertion_sort.gif

插入排序參考程式碼

insert.png

希爾排序 (Shell Sort)

希爾排序法⼜稱縮⼩增量法
希爾排序法的基本思想是：先選定⼀個整數（通常是gap = n/3+1），把待排序數據所有記錄分成各組，所有的距離相等的記錄分在同⼀組內，並對每⼀組內的記錄進⾏排序，然後gap=gap/3+1得到下⼀個整數，再將數組分成各組，進⾏插⼊排序，當gap=1時，就相當於直接插⼊排序
希爾排序其實就是在直接插入排序的基礎上優化而來

希爾排序參考程式碼

shell_Sorting.png

選擇排序(Selection Sort)

選擇排序演示

selection_sort.gif

選擇排序參考程式碼

selection_sort.png

泡沫排序(Bubble Sort)

假設目前有n個待排序的數據，冒泡排序則會進行n輪次的交換，每次交換完畢後都能讓當前輪次的最大值都能到期正確的位置

泡沫排序演示

Bubble_Sort.gif

泡沫排序參考程式碼

bubble_sort.png

  • exchange 是判斷當前輪次是否有做過交換，如果沒做過交換，就代表當前數據已經完成排序。
  • 因爲每輪都是兩兩比較，如果當前數據不是已經完成排序的情況，那必然會有交換發生。

快速排序(Quick Sort)

快速排序演示

Quick_Sort.gif

  • 這裡的上下區分是遞迴的深度演示

    快速排序程式碼演示

    遞迴方法(三種)

    Rec-1.png

    // 快速排序
int Quick_Sort_logic(vector<int>&a,int left,int right){
  int hole = left; // 坑的位置
  int pivot_Val = a[left];
  while(left < right){
      // 從右邊找值來填坑
      while(left < right && a[right] >= pivot_Val){
          --right;
      }
      a[hole] = a[right]; // Update 坑的值
      hole = right; // Update 坑的位置

      while(left < right && a[left] <= pivot_Val){
          ++left;
      }
      a[hole] = a[left];
      hole = left;
  }
  // 這裡結束後會準確地讓pivot_Val左邊都是小於pivot_val 反之右邊都是大於
  // 再來將pivot_Val 填回去他應該在的位置
  a[hole] = pivot_Val;
  return hole;
}
void Quick_Sort(vector<int>&a,int left,int right){
  if(left >= right){
      return;
  }
  int mid = Quick_Sort_logic(a,left,right); // 先排一輪
  Quick_Sort(a,left,mid);
  Quick_Sort(a,mid+1,right);

}

    Rec-3.png

    非遞迴方法

    non-rec-1.png

    堆排序(Heap Sort)

  • 堆排序的核心概念為堆！堆排序就是先建好小堆後，然後再搭配堆刪除數據來完成

    堆排序參考程式碼

    Heap_sort.png

    歸併排序(Merge Sort)

  • 歸併排序的核心思想是分治思想，將大問題拆解成小問題來解決

    歸併排序演示

    Merge_Sort.gif

    歸併排序參考程式碼

    Merge_Sort.png

    計數排序

    計數排序演示

    count_sort.gif

    計數排序參考程式碼

    count_sort.png

    效率、穩定性比較

    Compare.png