Flutter Dart快速排序演演算法範例詳解

2022-12-11 14:01:40

引言

在日常研發的過程中，我們無時無刻都在考慮自己開發的程式是否高效，一段好的程式執行離不開對演演算法的深刻認識和熟練掌握。接下來的日子，我將帶著大家一起重溫一下常見的幾種演演算法。

先上大圖：

下面我們一起來學習一下 快速排序演演算法 吧！

快速排序演演算法

維基百科介紹：快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為較小和較大的2個子序列，然後遞迴地排序兩個子序列，最終合併得到一個從小到大的序列。

有聰明的小夥伴就會問了：什麼是分治法策略呢？

分治法（Divide and conquer）

字面上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。

由此就可以引出我們今天講的快速排序演演算法的實現步驟了：

從資料中隨機獲取一個值，按這個值的大小對比分成左右兩個資料集合，左邊資料集合的值小於此值，右邊反之
將兩邊資料進行遞迴呼叫步驟1
將所有資料合併

快速排序演演算法實現

void main() {
  List<int> quickSort(List<int> arr) {
    // 處理邊界問題 
    if (arr.length <= 1) {
      return arr;
    }
    // 取出第一個值作為參考
    int splitData = arr[0];
    // 小於參考值的集合
    List<int> low = [];
    // 大於參考值的集合
    List<int> hight = [];
    // 與參考相等的集合
    List<int> mid = [];
    // 初次把參考值新增到mid中
    mid.add(splitData);
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] < splitData) {
        // 小於
        low.add(arr[i]);
      } else if (arr[i] > splitData) {
        // 大於
        hight.add(arr[i]);
      } else {
        // 等於
        mid.add(arr[i]);
      }
    }
    // 二分資料後，再繼續遞迴整理
    low = quickSort(low);
    hight = quickSort(hight);
    // 最後合併
    return [...low, ...mid, ...hight];
  }
  const List<int> ary = [4, 5, 1, 3, 6, 2, 5, 6, 7, 2, 4];
  print(quickSort(ary));
}

至此，我們就重新溫習了一下 快排演演算法 ！

更多關於Flutter Dart快速排序演演算法的資料請關注it145.com其它相關文章！

Flutter Dart快速排序演演算法範例詳解

目錄

引言

快速排序演演算法

分治法（Divide and conquer）

快速排序演演算法實現

熱門文章