快速排序

[toc]

快速排序1960年由查爾斯安東尼理查德霍爾(Charles Antony Richard Hoare,縮寫為C. A. R. Hoare)提出的
作者行業(yè)內(nèi)昵稱為東尼霍爾(Tony Hoare)

執(zhí)行流程

從序列中選擇一個軸點元素 (pivot)
- 段設(shè)每次選擇0位置的元素為軸點元素
利用pivot將序列分割成2個子序列
- 將小于pivot的元素放在pivot前面(左側(cè))
- 將大于pivot的元素放在pivot后面(右側(cè))
- 等于pivot的元素放哪邊都可以
對子序列進行1坦辟、2操作
- 直到不能再分割(子序列中只剩下1個元素)

本質(zhì)：逐漸將每一個元素都轉(zhuǎn)化成軸點元素

選擇軸點流程

如圖

image.png

構(gòu)造兩個索引begin和end,begin指向頭元素蕴侧，end指向末尾元素，選擇將第一個元素變成軸點6a嘉赎，備份6a
從末尾開始掃描辜羊，也就是從end開始掃描涕蜂，發(fā)現(xiàn)7>6酷鸦，讓end--鳞尔，end指向5，如圖第2行
再比較5<6,讓5覆蓋6a元素的位置盗扇，begin++笼裳，如圖第3行，5是黑色表示是垃圾數(shù)據(jù)粱玲，該位置隨時可能會被覆蓋
再開始begin開始掃描，發(fā)現(xiàn)8>6,讓8覆蓋黑色5的位置拜轨，原來8的位置變成黑色抽减，如果第4行，執(zhí)行end--橄碾，end指向9
再比較9>6,直接讓end--,end指向4卵沉，如果5行
再比較4<6,讓4覆蓋8a黑色位置，如圖6行法牲，begin++史汗，end變成黑色即為垃圾位置
再比較8b>6,讓8b覆蓋4的位置，并執(zhí)行end--拒垃，如圖行7
比較6b=6a,可以不動停撞，也可以移動，這里讓6b移動悼瓮，也就是放入8b黑色的位置戈毒，并執(zhí)行begin++,如圖行8
比較2<6，直接begin++横堡，如圖行9
此時begin==end埋市，將6a放入此位置，軸點生成完成

代碼


class QuickSort<T extends Comparable<T>> extends Sort<T> {
  @override
  sort() {
    int begin = 0;
    int end = list.length;
    _sort(begin,end);
  }

  ///
  /// Author: liyanjun
  /// description:
  ///對[[begin,end)],左閉右開的命贴，范圍內(nèi)元素進行快速排序
  _sort(int begin, int end) {
    //元素必須大于2
    if (end - begin < 2) return;
    int mid = _pivotIndex(begin, end);//O(n)
    _sort(begin, mid); //左邊子序列快速排序 
    _sort(mid + 1, end); //右邊子序列快速排序
  }

  ///
  /// Author: liyanjun
  /// description:
  /// 構(gòu)造出 [begin, end) 范圍的軸點元素,返回軸點元素的最終位置
  ///
  int _pivotIndex(int begin, int end) {
    //將begin元素備份
    T pivot = list[begin];
    //由于是左閉右開道宅，所以要讓end--
    end--;
    while (begin < end) {//確定變換方向后繼續(xù)執(zhí)行
      while (begin < end) {//后面掃描
        if (cmpElement(list[end], pivot) > 0) {
          //右邊元素大于軸點元素
          end--;
        } else {
          //右邊元素小于等于軸點元素
          list[begin++] = list[end];
          break;
        }
      }
      while (begin < end) {//前面掃描
        if (cmpElement(list[begin], pivot) < 0) {
          //左邊元素小于軸點元素
          begin++;
        } else {
          //右邊元素>=軸點元素
          list[end--] = list[begin];
          break;
        }
      }
    }
    list[begin] = pivot; //// 將軸點元素放入最終的位置
    return begin; //此時begin==end
  }
}

驗證


main(List<String> args) {
  // List<int> list = IntergerTools.random(10000, 1, 20000); //生成10000個數(shù)食听，最小是1，最大是20000
  List<int> list = IntergerTools.random(10, 1, 20); //生成10000個數(shù)污茵，最小是1樱报，最大是20000
  List<Sort> sortList = [
    // HeapSort<num>(),
    // SelectSort<num>(),
    // BubbleSort2<num>(),
    // BubbleSort1<num>(),
    // BubbleSort<num>(),
    // InsertSort<num>(),
    // InsertSort1<num>(),
    // InsertSort2<num>(),
    // MergeSort<num>(),
    QuickSort<num>()
  ];
  testSorts(list, sortList);
}

void testSorts(List<int> list, List<Sort> sorts) {
  print('排序前 ：$list');
  for (Sort sort in sorts) {
    List<int> newList = List.from(list);
    sort.setList(newList);
    sort.sortPrint();
    Asserts.test(IntergerTools.isAscOrder(sort.list));
     print('排序后 ：${sort.list}');
  }
  sorts.sort(); //比較
  for (Sort sort in sorts) {
    print(sort);
  }
}

執(zhí)行結(jié)果

排序前 ：[7, 9, 6, 15, 10, 19, 16, 18, 18, 6]
排序后 ：[6, 6, 7, 9, 10, 15, 16, 18, 18, 19]
【QuickSort<num>】
耗時：0.001s (1ms)     比較：22    交換：0
-----------------

時間復(fù)雜度

在軸點左右元素數(shù)量比較均勻的情況下，同時也是最好的情況
- 左邊 $T(n/2)$ 省咨，右邊 $T(n/2)$
- $\therefore$ $T(n) = 2 ? T(n/2) + O (n) = O(nlogn)$
如果軸點左右元素數(shù)量極度不均勻肃弟，最壞情況
- 假如左邊n-1個，右邊1個
- 左邊 $T(n-1)$ 零蓉，右邊左邊 $T(1)$
- $\therefore$ $T(n) = T(n-1) + O (n) = O(n^2)$

最好笤受、平均時間復(fù)雜度： $O(nlogn)$
最壞時間復(fù)雜度： $O(n^2)$
由于遞歸調(diào)用的緣故，空間復(fù)雜度： $O(logn)$
屬于不穩(wěn)定排序

為了降低最壞情況的出現(xiàn)概率敌蜂，一般采取的做法是

隨機選擇軸點元素

優(yōu)化代碼

 ///
  /// Author: liyanjun
  /// description:
  /// 構(gòu)造出 [begin, end) 范圍的軸點元素,返回軸點元素的最終位置
  ///
  int _pivotIndex(int begin, int end) {
    
  // 隨機選擇一個元素跟begin位置進行交換
    //因為 Random().nextInt(max)是包括max的箩兽，所以應(yīng)該end-1
        swap(begin, begin + Random().nextInt(end-1-begin));
    //將begin元素備份
    T pivot = list[begin];
    //由于是左閉右開，所以要讓end--
    end--;
    while (begin < end) {//確定變換方向后繼續(xù)執(zhí)行  思想章喉，掉頭用兩個while循環(huán)
      while (begin < end) {//后面掃描
        if (cmpElement(list[end], pivot) > 0) {
          //右邊元素大于軸點元素
          end--;
        } else {
          //右邊元素小于等于軸點元素
          list[begin++] = list[end];
          break;
        }
      }
      while (begin < end) {//前面掃描
        if (cmpElement(list[begin], pivot) < 0) {
          //左邊元素小于軸點元素
          begin++;
        } else {
          //右邊元素>=軸點元素
          list[end--] = list[begin];
          break;
        }
      }
    }
    list[begin] = pivot; //// 將軸點元素放入最終的位置
    return begin; //此時begin==end
  }
}

與軸點相等的元素

cmp 位置的判斷分別改為 ≤汗贫、≥ 會起到什么效果
假如原數(shù)組為
[3,3,3,3,3,3]
如果判斷為 ≤、≥ 秸脱，則會導(dǎo)致軸點元素處于兩端落包，造成最壞情況的時間復(fù)雜度，所以不用

快速排序（dart實現(xiàn)）