快速排序

[toc]

快速排序1960年由查尔斯安东尼理查德霍尔(Charles Antony Richard Hoare,缩写为C. A. R. Hoare)提出的
作者行业内昵称为东尼霍尔(Tony Hoare)

执行流程

从序列中选择一个轴点元素 (pivot)
- 段设每次选择0位置的元素为轴点元素
利用pivot将序列分割成2个子序列
- 将小于pivot的元素放在pivot前面(左侧)
- 将大于pivot的元素放在pivot后面(右侧)
- 等于pivot的元素放哪边都可以
对子序列进行1、2操作
- 直到不能再分割(子序列中只剩下1个元素)

本质：逐渐将每一个元素都转化成轴点元素

选择轴点流程

如图

image.png

构造两个索引begin和end,begin指向头元素，end指向末尾元素，选择将第一个元素变成轴点6a，备份6a
从末尾开始扫描，也就是从end开始扫描，发现7>6，让end--，end指向5，如图第2行
再比较5<6,让5覆盖6a元素的位置，begin++，如图第3行，5是黑色表示是垃圾数据，该位置随时可能会被覆盖
再开始begin开始扫描，发现8>6,让8覆盖黑色5的位置，原来8的位置变成黑色，如果第4行，执行end--，end指向9
再比较9>6,直接让end--,end指向4，如果5行
再比较4<6,让4覆盖8a黑色位置，如图6行，begin++，end变成黑色即为垃圾位置
再比较8b>6,让8b覆盖4的位置，并执行end--，如图行7
比较6b=6a,可以不动，也可以移动，这里让6b移动，也就是放入8b黑色的位置，并执行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)],左闭右开的，范围内元素进行快速排序
  _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:
  /// 构造出 [begin, end) 范围的轴点元素,返回轴点元素的最终位置
  ///
  int _pivotIndex(int begin, int end) {
    //将begin元素备份
    T pivot = list[begin];
    //由于是左闭右开，所以要让end--
    end--;
    while (begin < end) {//确定变换方向后继续执行
      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个数，最小是1，最大是20000
  List<int> list = IntergerTools.random(10, 1, 20); //生成10000个数，最小是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);
  }
}

执行结果

排序前 ：[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
-----------------

时间复杂度

在轴点左右元素数量比较均匀的情况下，同时也是最好的情况
- 左边 $T(n/2)$ ，右边 $T(n/2)$
- $\therefore$ $T(n) = 2 ∗ T(n/2) + O (n) = O(nlogn)$
如果轴点左右元素数量极度不均匀，最坏情况
- 假如左边n-1个，右边1个
- 左边 $T(n-1)$ ，右边左边 $T(1)$
- $\therefore$ $T(n) = T(n-1) + O (n) = O(n^2)$

最好、平均时间复杂度： $O(nlogn)$
最坏时间复杂度： $O(n^2)$
由于递归调用的缘故，空间复杂度： $O(logn)$
属于不稳定排序

为了降低最坏情况的出现概率，一般采取的做法是

随机选择轴点元素

优化代码

 ///
  /// Author: liyanjun
  /// description:
  /// 构造出 [begin, end) 范围的轴点元素,返回轴点元素的最终位置
  ///
  int _pivotIndex(int begin, int end) {
    
  // 随机选择一个元素跟begin位置进行交换
    //因为 Random().nextInt(max)是包括max的，所以应该end-1
        swap(begin, begin + Random().nextInt(end-1-begin));
    //将begin元素备份
    T pivot = list[begin];
    //由于是左闭右开，所以要让end--
    end--;
    while (begin < end) {//确定变换方向后继续执行  思想，掉头用两个while循环
      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 位置的判断分别改为 ≤、≥ 会起到什么效果
假如原数组为
[3,3,3,3,3,3]
如果判断为 ≤、≥ ，则会导致轴点元素处于两端，造成最坏情况的时间复杂度，所以不用

快速排序（dart实现）