分治法：每一轮选择一个基准元素，将数组中小于这个基准值的所有元素移动到它的左边，比它大的移动到它的右边，从而数组分成了两个部分，然后在每一部分继续拆分，直到不可分为止，最后得到一个有序的数组。

    • 最好的排序算法

    标准库的sort：先快排，递归深度达到一个阈值后改为堆排，然后对最后几个元素进行插入排序。
    image.png

    • 时间复杂度：O(n*logn)
      • 一共拆分O(logn)轮，递归的深度
      • O(n)：每一轮都会遍历每一部分的每一个元素与基准值进行比较移动。
      • 最坏情况下(正序或者逆序): O(n2) 每一轮拆分都是将数组拆分成了一个元素和其它元素两个部分，退化成了冒泡排序。
        • 避免：随机选择一个基准元素与数组首元素交换
    • vs 冒泡排序
      • 快排每次的数据交换都是跳跃式的两两交换，而冒泡排序每次都只能不断在相邻元素之间进行比较交换，所以快排总的比较和交换次数比冒泡少，速度快，最坏情况下时间复杂度也是O(n2)。
    1. #include <iostream>
    2. #include <vector>
    3. using namespace std;
    5. int partition(vector<int> &nums, int l, int r) {
    6.     int pivot = l;
    7.     while (l != r) {
    8.         while (l < r && nums[r] > nums[pivot]) r--;  // r先走，最后l==r时，nums[l]<nums[pivot]
    9.         while (l < r && nums[l] <= nums[pivot]) l++;
    10.         if (l < r) swap(nums[l], nums[r]);
    11.     }
    12.     swap(nums[l], nums[pivot]);
    13.     return l;
    14. }
    16. void quick_sort(vector<int> &nums, int l, int r) {
    17.     if (l >= r) return;
    18.     int pivot = partition(nums, l, r);
    19.     quick_sort(nums, l, pivot-1);
    20.     quick_sort(nums, pivot+1, r);
    21. }
    23. vector<int> my_sort(vector<int> &nums) {
    24.     quick_sort(nums, 0, nums.size()-1);
    25.     return nums;
    26. }
    28. int main() {
    29.     vector<int> nums{8, 4, 2, 7, 0, 9};
    30.     vector<int> nums_sorted = my_sort(nums);
    31.     for (int n : nums_sorted) {
    32.         cout << n << ' ';
    33.     }
    34.     cout << endl;
    35.     return 0;
    36. }