快捷導(dǎo)航

Flutter Dart快速排序算法示例詳解

更新時(shí)間：2022年12月09日 10:59:24 作者：Asscre

這篇文章主要為大家介紹了Flutter Dart快速排序算法示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

引言

在日常研發(fā)的過(guò)程中，我們無(wú)時(shí)無(wú)刻都在考慮自己開(kāi)發(fā)的程序是否高效，一段好的程序執(zhí)行離不開(kāi)對(duì)算法的深刻認(rèn)識(shí)和熟練掌握。接下來(lái)的日子，我將帶著大家一起重溫一下常見(jiàn)的幾種算法。

先上大圖：

下面我們一起來(lái)學(xué)習(xí)一下 快速排序算法 吧！

快速排序算法

維基百科介紹：快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)序列（list）分為較小和較大的2個(gè)子序列，然后遞歸地排序兩個(gè)子序列，最終合并得到一個(gè)從小到大的序列。

有聰明的小伙伴就會(huì)問(wèn)了：什么是分治法策略呢？

分治法（Divide and conquer）

字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。

由此就可以引出我們今天講的快速排序算法的實(shí)現(xiàn)步驟了：

從數(shù)據(jù)中隨機(jī)獲取一個(gè)值，按這個(gè)值的大小對(duì)比分成左右兩個(gè)數(shù)據(jù)集合，左邊數(shù)據(jù)集合的值小于此值，右邊反之
將兩邊數(shù)據(jù)進(jìn)行遞歸調(diào)用步驟1
將所有數(shù)據(jù)合并

快速排序算法實(shí)現(xiàn)

void main() {
  List<int> quickSort(List<int> arr) {
    // 處理邊界問(wèn)題 
    if (arr.length <= 1) {
      return arr;
    }
    // 取出第一個(gè)值作為參考
    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]);
      }
    }
    // 二分?jǐn)?shù)據(jù)后，再繼續(xù)遞歸整理
    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));
}

至此，我們就重新溫習(xí)了一下 快排算法 ！

更多關(guān)于Flutter Dart快速排序算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: