【无标题】

排序 快速排序

选择一个轴（pivot），下标i, j,通过不断移动下标、比较、交换，使得轴左边所有数据小于轴，右边所有数据大于轴；
递归进行上述过程，直到所有数列长度为0或1，排序结束；
由于每次迭代过程，至少有一个值（轴）排好序，所以最终算法会终止；

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int l =0, r= nums.size()-1;
        recursive(nums, l, r);
        return nums;
    }

    void recursive(vector<int>& nums, int l, int r){
        if (l >= r) return;
        int pivot = partition(nums, l, r);
        recursive(nums, l, pivot-1);
        recursive(nums, pivot+1, r);
    }

    int partition(vector<int>& nums, int l, int r){
        int pivot = nums[l];
        while (l < r){
            while (nums[r] >= pivot && l < r) r--;
            nums[l] = nums[r];
            while (nums[l] < pivot && l <r) l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
};

lectcode 215
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

归并排序

归并排序的思想：递归+分治
稳定排序
时间复杂度：O(N^logN)

分治算法

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立，且与原问题性质相同。

求出子问题的解后进行合并，就可以得到原问题的解

一般步骤：

分解：将要解决的问题划分成若干规模较小的同类问题
求解：当子问题划分得足够小的时候，用较简单的方法解决
合并，按原问题的要求，将子问题的解逐层合并构成原问题的解

算法模板

int t[100001];

void mergesort(int a[], int l, int r){
    if (l >= r) return;
    int mid = l+r>> 1;
    mergesort(a, l, mid), mergesort(a, mid+1, r);  // 递归 + 分治

    int i = l, j = mid+1, k= 0;
    while (i <= mid && j <= r){
        if (a[i] < a[j] ) t[k++] = a[i++];
        else t[k++] = a[j++];
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (int i = l, j = 0; i<=r; i++, j++) a[i] = t[j];
}

LeetCode 493. Reverse Pairs (hard) 原题链接 (opens new window)题解

LeetCode 315. Count of Smaller Numbers After Self (hard)

LeetCode 327. Count of Range Sum (hard)

LeetCode 148. Sort List (medium)

冒泡排序

进行len-1次冒泡
第k次冒泡将倒数第k个元素排好序

代码实现

function bubbleSort(nums) {
    for (let i = 0; i < nums.length - 1; i++) { // len - 1次冒泡
        for (let j = 0; j < nums.length - i - 1; j++) { // 依次比较相邻元素，进行冒泡，比较区间[0,len - 1 - i]
            if (nums[j] > nums[j + 1]) {
                let tmp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = tmp
            }
        }
    }
    return nums
}

桶排序 桶排序 的两个步骤：

分桶
合并

基数排序

先按个位进行桶排序
然后按十位进行桶排序
然后按百位进行桶排序 …
直到所有位完成桶排序，最后的序列就是排好序的
比如：452，897，472，385，752

按个位：452，472，752，385，897
按十位：452，752，472，385，897
按百位：385，452，472，752，897 已经排好序

计数排序

统计每一个数字出现的次数，输出次数次即可

题目

LeetCode 164. Maximum Gap (hard)

LeetCode 220. Contains Duplicate III (medium)

LeetCode 451. Sort Characters By Frequency (medium)

基础知识

快速排序（Quick Sort）， 归并排序（Merge Sort）的原理与代码实现。

需要能讲明白代码中每一行的目的。

快速排序时间复杂度平均状态下O（NlogN），空间复杂度O（1），归并排序最坏情况下时间复杂度O（NlogN），空间复杂度O（N）

入门题目：

Leetcode 148. Sort List
Leetcode 56. Merge Intervals
Leetcode 27. Remove elements

进阶题目：

Leetcode 179. Largest Number
Leetcode 75. Sort Colors
Leetcode 215. Kth Largest Element （可以用堆的解法替代）
Leetcode 4. Median of Two Sorted Arrays
注意：后两题是与快速排序非常相似的快速选择（Quick Select）算法，面试中很常考