01.03 数组排序（第 05 ~ 08 天）_Java

01.03 数组排序（第 05 ~ 08 天）

1.冒泡排序算法(bubble sort)

经过多次迭代，通过相邻元素之间的比较与交换，使值较小的元素逐步从后面移到前面，值较大的元素从前面移到后面。
假设数组的元素个数为 $n$ 个，则冒泡排序的算法步骤如下：

第 $1$ 趟「冒泡」：对前 $n$ 个元素执行「冒泡」，从而使第 $1$ 个值最大的元素放置在正确位置上。
1. 先将序列中第 $1$ 个元素与第 $2$ 个元素进行比较，如果前者大于后者，则两者交换位置，否则不交换。
2. 然后将第 $2$ 个元素与第 $3$ 个元素比较，如果前者大于后者，则两者交换位置，否则不交换。
3. 依次类推，直到第 $n - 1$ 个元素与第 $n$ 个元素比较（或交换）为止。
4. 经过第 $1$ 趟排序，使得 $n$ 个元素中第 $i$ 个值最大元素被安置在第 $n$ 个位置上。
第 $2$ 趟「冒泡」：对前 $n - 1$ 个元素执行「冒泡」，从而使第 $2$ 个值最大的元素放置在正确位置上。
1. 先将序列中第 $1$ 个元素与第 $2$ 个元素进行比较，若前者大于后者，则两者交换位置，否则不交换。
2. 然后将第 $2$ 个元素与第 $3$ 个元素比较，若前者大于后者，则两者交换位置，否则不交换。
3. 依次类推，直到第 $n - 2$ 个元素与第 $n - 1$ 个元素比较（或交换）为止。
4. 经过第 $2$ 趟排序，使得数组中第 $2$ 个值最大元素被安置在第 $n$ 个位置上。
依次类推，重复上述「冒泡」过程，直到某一趟排序过程中不出现元素交换位置的动作，则排序结束。

void bubblesort(vector<int>& arr) {
    int n = arr.size();
    for(int i = 0; i < n - 1; i++) {
        bool flag = false;//是否发生交换
        for(int j = 0; j < n - i - 1; j++) {
            if( arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                flag = true;
            }
        }
        if(!flage) break;
    }
}
//最佳时间复杂度：o(n)。最好的情况下（初始时序列已经是升序排列），只需经过 $1$ 趟排序，总共经过 $n$ 次元素之间的比较，并且不移动元素，算法就可以结束排序。因此，冒泡排序算法的最佳时间复杂度为 $o(n)$。
//最坏时间复杂度：o(n^2) （初始序列已经是降序，或最小值元素在序列最后）
//平均时间复杂度o(n^2)
//空间复杂度o(1)

2. 选择排序(selection sort)

将数组分为两个区间：左侧为已排序区间，右侧为未排序区间。每趟从未排序区间中选择一个值最小的元素，放到已排序区间的末尾，从而将该元素划分到已排序区间。

假设数组的元素个数为 $n$ 个，则选择排序的算法步骤如下：

初始状态下，无已排序区间，未排序区间为 $[0, n - 1]$ 。
第 $1$ 趟选择：
1. 遍历未排序区间 $[0, n - 1]$ ，使用变量 $min\underline{}i$ 记录区间中值最小的元素位置。
2. 将 $min\underline{}i$ 与下标为 $0$ 处的元素交换位置。如果下标为 $0$ 处元素就是值最小的元素位置，则不用交换。
3. 此时， $[0, 0]$ 为已排序区间， $[1, n - 1]$ （总共 $n - 1$ 个元素）为未排序区间。
第 $2$ 趟选择：
1. 遍历未排序区间 $[1, n - 1]$ ，使用变量 $min\underline{}i$ 记录区间中值最小的元素位置。
2. 将 $min\underline{}i$ 与下标为 $1$ 处的元素交换位置。如果下标为 $1$ 处元素就是值最小的元素位置，则不用交换。
3. 此时， $[0, 1]$ 为已排序区间， $[2, n - 1]$ （总共 $n - 2$ 个元素）为未排序区间。
依次类推，对剩余未排序区间重复上述选择过程，直到所有元素都划分到已排序区间，排序结束。

void selectsort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int min_i = i; 
        for(int j = i + 1; j < n; j++) {
            if( arr[min_i] > arr[j]) {
                min_i = j;
            }
        }
        if (i != min_i) swap(arr[i], arr[min_i]);
    }
}
//时间复杂度o(n^2).排序法所进行的元素之间的比较次数与序列的原始状态无关，时间复杂度总是 $o(n^2)$。因而不能像冒泡那样提前终止。
//空间复杂度o(1)

3. 插入排序（insertion sort)

将数组分为两个区间：左侧为有序区间，右侧为无序区间。每趟从无序区间取出一个元素，然后将其插入到有序区间的适当位置。

假设数组的元素个数为 $n$ 个，则插入排序的算法步骤如下：

初始状态下，有序区间为 $[0, 0]$ ，无序区间为 $[1, n - 1]$ 。
第 $1$ 趟插入：
1. 取出无序区间 $[1, n - 1]$ 中的第 $1$ 个元素，即 $n u m s [1]$ 。
2. 从右到左遍历有序区间中的元素，将比 $n u m s [1]$ 大的元素向后移动 $1$ 位。
3. 如果遇到小于或等于 $n u m s [1]$ 的元素时，说明找到了插入位置，将 $n u m s [1]$ 插入到该位置。
4. 插入元素后有序区间变为 $[0, 1]$ ，无序区间变为 $[2, n - 1]$ 。
第 $2$ 趟插入：
1. 取出无序区间 $[2, n - 1]$ 中的第 $1$ 个元素，即 $n u m s [2]$ 。
2. 从右到左遍历有序区间中的元素，将比 $n u m s [2]$ 大的元素向后移动 $1$ 位。
3. 如果遇到小于或等于 $n u m s [2]$ 的元素时，说明找到了插入位置，将 $n u m s [2]$ 插入到该位置。
4. 插入元素后有序区间变为 $[0, 2]$ ，无序区间变为 $[3, n - 1]$ 。
依次类推，对剩余无序区间中的元素重复上述插入过程，直到所有元素都插入到有序区间中，排序结束。

void insertsort(vector<int> nums) {
    for (int i = 1; i < nums.size(); i++) {
        int temp = nums[i];
        for (int j = i; j > 0; j--) {
            if (nums[j-1] > temp){
                nums[j] = nums[j-1];
            }
            nums[j] = temp;
        }
    }
}
//最佳时间复杂度o(n),已排好序的情况
//时最差间复杂度o(n^2)
//平均时间复杂度o(n^2)$。如果区间的初始情况是随机的
//空间复杂度o(1)

164. 破解闯关密码

闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：

一个拥有密码所有元素的非负整数数组 password密码是 password 中所有元素拼接后得到的最小的一个数请编写一个程序返回这个密码。

说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

思路： 将整数数组转化为字符串数组。并将数组元素用字典序排序，再拼接。

class solution {
public:
    string minnumber(vector<int>& nums) {
        int n = nums.size();
        vector<string> strs(n);
        for (int i = 0; i < n; i++) {
            strs[i] = to_string(nums[i]);
        }
        sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {
            // 看看那种拼接方式得到的数字更小，排前面
            // 不用转成 int 类型，因为字符串的比较算法和正整数的比较算法是一样的
            // 而且拼接字符串比较长，会导致 int 类型溢出
            return (s1 + s2) < (s2 + s1);
        });

        return accumulate(strs.begin(), strs.end(), string(""));
    }
};

0283. 移动零

描述：给定一个数组 $n u m s$ 。

要求：将所有 $0$ 移动到末尾，并保持原有的非 $0$ 数字的相对顺序。

说明：

只能在原数组上进行操作。
$\le nums.length \le 10^4$ 。
$-2^{31} \le nums[i] \le 2^{31} - 1$ 。

思路： 快慢指针。快指针找到非零元素，慢指针指向零元素，然后交换。

void movezeroes(vector<int>& nums) {
    int left = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) {
            swap(nums[i], nums[left++]);
        }
    }
}

0912. 排序数组

描述：给定一个整数数组 $n u m s$ 。

要求：将该数组升序排列。

快排，三路快排

class solution {
public:

    void quicksort(vector<int> &nums, int left, int right)
    {
        if(left >= right) return;

        int less = left;
        int large = right;
        int i = left;
        int pivot = nums[rand() % (right - left) + left];

        while(i <= large)
        {
            if(nums[i] < pivot)
            {
                swap(nums[i], nums[less]);
                i++;
                less++;
            }
            else if(nums[i] > pivot) 
            {
                swap(nums[i], nums[large]);
                large--;
            }
            else
            {
                i++;
            }
        }
        quicksort(nums, left, less - 1);
        quicksort(nums, large + 1, right);
    }

    vector<int> sortarray(vector<int>& nums) {
        
        srand((unsigned)time(null));

        int len = nums.size() - 1;
        
        quicksort(nums, 0, len);

        return nums;
    }
};
//平均时间复杂度o(nlogn)
//空间复杂度o(h),h为快排的递归调用层数

4. 归并排序（merge sort）：采用经典的分治策略，先递归地将当前数组平均分成两半，然后将有序数组两两合并，最终合并成一个有序数组。

假设数组的元素个数为 $n$ 个，则归并排序的算法步骤如下：

分解过程：先递归地将当前数组平均分成两半，直到子数组长度为 $1$ 。
1. 找到数组中心位置 $mi d$ ，从中心位置将数组分成左右两个子数组 $left\underline{}nums$ 、 $right\underline{}nums$ 。
2. 对左右两个子数组 $left\underline{}nums$ 、 $right\underline{}nums$ 分别进行递归分解。
3. 最终将数组分解为 $n$ 个长度均为 $1$ 的有序子数组。
归并过程：从长度为 $1$ 的有序子数组开始，依次将有序数组两两合并，直到合并成一个长度为 $n$ 的有序数组。
1. 使用数组变量 $n u m s$ 存放合并后的有序数组。
2. 使用两个指针 $left\underline{}i$ 、 $right\underline{}i$ 分别指向两个有序子数组 $left\underline{}nums$ 、 $right\underline{}nums$ 的开始位置。
3. 比较两个指针指向的元素，将两个有序子数组中较小元素依次存入到结果数组 $n u m s$ 中，并将指针移动到下一位置。
4. 重复步骤 $3$ ，直到某一指针到达子数组末尾。
5. 将另一个子数组中的剩余元素存入到结果数组 $n u m s$ 中。
6. 返回合并后的有序数组 $n u m s$ 。

class solution {
public:
    // void merge()

    void mergesort(vector<int>& nums, int left, int right){
        if(left >= right) return;
        mid = (left + right) / 2;
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);
        vector<int> temp(right - left + 1);
        int l = left, r = mid + 1, k = 0;
        while(l <= mid && r <= right){
            if(nums[l] <= nums[r]) temp[k++] = nums[l++];
            else temp[k++] = nums[r++];
        }
        while (l <= mid){
            temp[k++] = nums[l++];
        }
        while(r <= right){
            temp[k++] = nums[r++];
        }

        for(k = 0; k < temp.size(); k++){
            nums[left + k] = temp[k];
        }
    }

    vector<int> sortarray(vector<int>& nums) {
        
        mergesort(nums, 0, nums.size() - 1);

        return nums;
    }
};

时间复杂度： $\times \log n)$ 。
空间复杂度： $o (n)$ 。归并排序方法需要用到与参加排序的数组同样大小的辅助空间。因此，算法的空间复杂度为 $o (n)$ 。
排序稳定性：因为在两个有序子数组的归并过程中，如果两个有序数组中出现相等元素，mergesort(nums, left, right): 算法能够使前一个数组中那个相等元素先被复制，从而确保这两个元素的相对顺序不发生改变。因此，归并排序算法是一种 稳定排序算法。

5. 希尔排序（shell sort）：将整个数组切按照一定的间隔取值划分为若干个子数组，每个子数组分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子数组和对子数组进行插入排序。直至最后一轮排序间隔为 $1$ ，对整个数组进行插入排序。

假设数组的元素个数为 $n$ 个，则希尔排序的算法步骤如下：

确定一个元素间隔数 $g a p$ 。
将参加排序的数组按此间隔数从第 $1$ 个元素开始一次分成若干个子数组，即分别将所有位置相隔为 $g a p$ 的元素视为一个子数组。
在各个子数组中采用某种排序算法（例如插入排序算法）进行排序。
减少间隔数，并重新将整个数组按新的间隔数分成若干个子数组，再分别对各个子数组进行排序。
依次类推，直到间隔数 $g a p$ 值为 $1$ ，最后进行一次排序，排序结束。

class solution {
public:
    // void merge()

    void shellsort(vector<int>& nums){
        n = nums.size();
        int gap = size / 2;
        while(gap > 0){
            for(int i = gap; i < n; i++){
                temp = nums[i];
                int j = i - gap;
                while(j >= 0 && nums[j] > temp){
                    nums[j + gap] = nums[j];
                    j -= gap; 
                }
                nums[j + gap] = temp;
            }
            gap /= 2;
        }
    }

    vector<int> sortarray(vector<int>& nums) {
        
        shellsort(nums, 0, nums.size() - 1);

        return nums;
    }
};
// 时间复杂度：介于 $o(n log^2 n)$ 与 $o(n^2)$ 之间。
// 空间复杂度：$o(1)$
// 排序稳定性：在一次插入排序是稳定的，不会改变相等元素的相对顺序，但是在不同的插入排序中，相等元素可能在各自的插入排序中移动。因此，希尔排序方法是一种不稳定排序算法。

0506. 相对名次

描述：给定一个长度为 $n$ 的数组 $score$ 。其中 $score [i]$ 表示第 $i$ 名运动员在比赛中的成绩。所有成绩互不相同。

要求：找出他们的相对名次，并授予前三名对应的奖牌。前三名运动员将会被分别授予「金牌（"gold medal"）」，「银牌（"silver medal"）」和「铜牌（"bronze medal"）」。

vector<string> findrelativeranks(vector<int>& score) {
    int n = score.size();
    vector<string> res(n);
    vector<string> desc = {"gold medal", "silver medal", "bronze medal"};
    vector<pair<int, int>> ranks;
    for (int i = 0; i < n; i++) ranks.push_back({score[i], i});

    sort(ranks.begin(), ranks.end(), greater<>());
    for (int i = 0; i < ranks.size(); i++) {
        if (i < 3) res[ranks[i].second] = desc[i];
        else res[ranks[i].second] = to_string(i + 1);
    }
    return res;

}

0088. 合并两个有序数组

描述：给定两个有序数组 $n u m s 1$ 、 $n u m s 2$ 。

要求：将 $n u m s 2$ 合并到 $n u m s 1$ 中，使 $n u m s 1$ 成为一个有序数组。

思路：归并排序的合并步

vector<int> temp(m+n);
    int i = 0, j = 0, k = 0;
    while(i < m && j < n){
        if(nums1[i] < nums2[j]) temp[k++] = nums1[i++];
        else temp[k++] = nums2[j++];
    }
    while(i < m){
        temp[k++] = nums1[i++];
    }
    while(j < n) {
        temp[k++] = nums2[j++];
    }
    for (k = 0; k < m + n; k++){
        nums1[k] = temp[k];
    }

思路：归并排序的合并步,但逆向。


vector<int> temp(m+n);
    int p1 = m - 1, p2 = n - 1, tail = m + n - 1;
    while(p1 >= 0 || p2  >= 0){
        if(p1 == -1) nums1[tail--] = nums2[p2--];
        else if(p2 == -1) nums1[tail--] = nums1[p1--];
        else if(nums1[p1] > nums2[p2]) nums1[tail--] = nums1[p1--];
        else nums1[tail--] = nums2[p2--];
    }

剑指 offer 51. 数组中的逆序对

描述：给定一个数组 $n u m s$ 。

要求：计算出数组中的逆序对的总数。

class solution {
private:
    int cnt;
    void mergesort(vector<int>& record, int l, int r){
        if (l >= r ) return;
        int mid = (l + r) / 2;
        mergesort(record, l, mid);
        mergesort(record, mid + 1, r);
        merge(record, l, mid, r);
    }
    void merge(vector<int>& record, int l, int mid, int r){
        int temp[r - l + 1];//使用数组，leetcode测速比vector快一些,
        //但实际上vector并不比数组慢，具体跟编译器优化有关
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r){
            if(record[i] > record[j]) {
                temp[k++] = record[j++];
                cnt += mid - i + 1; 
            } else {
                temp[k++] = record[i++];
            }
        }
        while(i <= mid){
            temp[k++] = record[i++];
        }
        while(j <= r){
            temp[k++] = record[j++];
        }
        for(k = 0; k < r-l+1; k++) {
            record[l + k] = temp[k];
        }

    }
public:
    
    int reversepairs(vector<int>& record) {
        cnt = 0;
        mergesort(record, 0, record.size()-1);
        return cnt;
    }

};

6. 快速排序（quick sort）：采用经典的分治策略，选择数组中某个元素作为基准数，通过一趟排序将数组分为独立的两个子数组，一个子数组中所有元素值都比基准数小，另一个子数组中所有元素值都比基准数大。然后再按照同样的方式递归的对两个子数组分别进行快速排序，以达到整个数组有序。

假设数组的元素个数为 $n$ 个，则快速排序的算法步骤如下：

哨兵划分：选取一个基准数，将数组中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧。
1. 从当前数组中找到一个基准数 $p i v o t$ （这里以当前数组第 $1$ 个元素作为基准数，即 $p i v o t = n u m s [l o w]$ ）。
2. 使用指针 $i$ 指向数组开始位置，指针 $j$ 指向数组末尾位置。
3. 从右向左移动指针 $j$ ，找到第 $1$ 个小于基准值的元素。
4. 从左向右移动指针 $i$ ，找到第 $1$ 个大于基准数的元素。
5. 交换指针 $i$ 、指针 $j$ 指向的两个元素位置。
6. 重复第 $\sim 5$ 步，直到指针 $i$ 和指针 $j$ 相遇时停止，最后将基准数放到两个子数组交界的位置上。
递归分解：完成哨兵划分之后，对划分好的左右子数组分别进行递归排序。
1. 按照基准数的位置将数组拆分为左右两个子数组。
2. 对每个子数组分别重复「哨兵划分」和「递归分解」，直到各个子数组只有 $1$ 个元素，排序结束。

class solution {
public:

int partition(vector<int> &nums, int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[i] <= nums[right])
            i++;          // 从左向右找首个大于基准数的元素
        while (i < j && nums[j] >= nums[right])
            j--; // 从右向左找首个小于基准数的元素
                // swap(nums, i, j); // 交换这两个元素
        swap(nums[i], nums[j]);
    }
    // swap(nums, i, left); // 将基准数交换至两子数组的分界线
    swap(nums[i], nums[right]);
    return i;            // 返回基准数的索引
}
void quicksort(vector<int> &nums, int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right)
        return;
    // 哨兵划分
    int pivot = partition(nums, left, right);
    // 递归左子数组、右子数组
    quicksort(nums, left, pivot - 1);
    quicksort(nums, pivot + 1, right);
}

void reversepairs(vector<int>& nums) {
    quicksort(nums, 0, nums.size()-1);
}

};
//最佳时间复杂度：$o(n \times \log n)$。每一次选择的基准数都是当前数组的中位数，此时算法时间复杂度满足的递推式为 $t(n) = 2 \times t(\frac{n}{2}) + \theta(n)$，由主定理可得 $t(n) = o(n \times \log n)$。
//最坏时间复杂度：$o(n^2)$。每一次选择的基准数都是数组的最终位置上的值，此时算法时间复杂度满足的递推式为 $t(n) = t(n - 1) + \theta(n)$，累加可得 $t(n) = o(n^2)$。
//平均时间复杂度**：$o(n \times \log n)$。在平均情况下，每一次选择的基准数可以看做是等概率随机的。其期望时间复杂度为 $o(n \times \log n)$。
//空间复杂度：$o(n)$。无论快速排序算法递归与否，排序过程中都需要用到堆栈或其他结构的辅助空间来存放当前待排序数组的首、尾位置。最坏的情况下，空间复杂度为 $o(n)$。如果对算法进行一些改写，在一趟排序之后比较被划分所得到的两个子数组的长度，并且首先对长度较短的子数组进行快速排序，这时候需要的空间复杂度可以达到 $o(log_2 n)$。
//排序稳定性：在进行哨兵划分时，基准数可能会被交换至相等元素的右侧。因此，快速排序是一种 **不稳定排序算法**。

7.堆排序（heap sort）

是一种基于「堆结构」实现的高效排序算法。

堆排序算法步骤:

构建初始大顶堆：
1. 定义一个数组实现的堆结构，将原始数组的元素依次存入堆结构的数组中（初始顺序不变）。
2. 从数组的中间位置开始，从右至左，依次通过「下移调整」将数组转换为一个大顶堆。
交换元素，调整堆：
1. 交换堆顶元素（第 $1$ 个元素）与末尾（最后 $1$ 个元素）的位置，交换完成后，堆的长度减 $1$ 。
2. 交换元素之后，由于堆顶元素发生了改变，需要从根节点开始，对当前堆进行「下移调整」，使其保持堆的特性。
重复交换和调整堆：
1. 重复第 $2$ 步，直到堆的大小为 $1$ 时，此时大顶堆的数组已经完全有序。

void siftdown(vector<int> &nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma])
            ma = l;
        if (r < n && nums[r] > nums[ma])
            ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) {
            break;
        }
        // 交换两节点
        swap(nums[i], nums[ma]);
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapsort(vector<int> &nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.size() / 2 - 1; i >= 0; --i) {
        siftdown(nums, nums.size(), i);
    }
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.size() - 1; i > 0; --i) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        swap(nums[0], nums[i]);
        // 以根节点为起点，从顶至底进行堆化
        siftdown(nums, i, 0);
    }空间复杂度**：$o(1)$
}
//时间复杂度：$o(n \times \log n)$。
//空间复杂度：$o(1)$

0075. 颜色分类

描述：给定一个数组 $n u m s$ ，元素值只有 $0$ 、 $1$ 、 $2$ ，分别代表红色、白色、蓝色。

要求：将数组进行排序，使得红色在前，白色在中间，蓝色在最后。

思路：快速排序三路并排的做法

class solution {
public:
    void sortcolors(vector<int>& nums) {
        int n = nums.size();
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                swap(nums[i], nums[p2]);
                --p2;
            }
            if (nums[i] == 0) {
                swap(nums[i], nums[p0]);
                ++p0;
            }
        }
    }
};
//时间复杂度：o(n)
//空间复杂度o(1)

0215. 数组中的第k个最大元素

描述：给定一个未排序的整数数组 $n u m s$ 和一个整数 $k$ 。

要求：返回数组中第 $k$ 个最大的元素。

思路: 快排的想法，当一次partiotion之后，pivot的位置是正确的，若pivot<n-k, 则第k大在右侧，否则在左侧。

class solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findkthlargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

剑指 offer 40. 最小的k个数

描述：给定整数数组 $a rr$ ，再给定一个整数 $k$ 。

要求：返回数组 $a rr$ 中最小的 $k$ 个数。

思路:快排的思想.与上题类似，只是找k小的数。

class solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }

    void selected(vector<int>& stock, int l, int r, int cnt) {
        if (l >= r) {
            return;
        }
        int pos = partition(stock, l, r);
        int num = pos - l + 1;
        if (cnt == num) {
            return;
        } else if (cnt < num) {
            selected(stock, l, pos - 1, cnt);
        } else {
            selected(stock, pos + 1, r, cnt - num);
        }
    }

public:
    vector<int> inventorymanagement(vector<int>& stock, int cnt) {
        selected(stock, 0, (int)stock.size() - 1, cnt);
        vector<int> vec;
        for (int i = 0; i < cnt; ++i) {
            vec.push_back(stock[i]);
        }
        return vec;
    }
};

计数排序（counting sort）：

通过统计数组中每个元素在数组中出现的次数，根据这些统计信息将数组元素有序的放置到正确位置，从而达到排序的目的。

计算排序范围：遍历数组，找出待排序序列中最大值元素 $nums\underline{}max$ 和最小值元素 $nums\underline{}min$ ，计算出排序范围为 $nums\underline{}max - nums\underline{}min + 1$ 。
定义计数数组：定义一个大小为排序范围的计数数组 $co u n t s$ ，用于统计每个元素的出现次数。其中：
1. 数组的索引值 $nums\underline{}min$ 表示元素的值为 $n u m$ 。
2. 数组的值 $nums\underline{}min]$ 表示元素 $n u m$ 的出现次数。
对数组元素进行计数统计：遍历待排序数组 $n u m s$ ，对每个元素在计数数组中进行计数，即将待排序数组中「每个元素值减去最小值」作为索引，将「对计数数组中的值」加 $1$ ，即令 $nums\underline{}min]$ 加 $1$ 。
生成累积计数数组：从 $co u n t s$ 中的第 $1$ 个元素开始，每一项累家前一项和。此时 $nums\underline{}min]$ 表示值为 $n u m$ 的元素在排序数组中最后一次出现的位置。
逆序填充目标数组：逆序遍历数组 $n u m s$ ，将每个元素 $n u m$ 填入正确位置。
将其填充到结果数组 $res$ 的索引 $nums\underline{}min]$ 处。
放入后，令累积计数数组中对应索引减 $1$ ，从而得到下个元素 $n u m$ 的放置位置。

void countingsort(vector<int> &nums) {
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }

    for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
    }
 
    int n = nums.size();
    vector<int> res(n);
    for (int i = n - 1; i >= 0; i--) {
        int num = nums[i];
        res[counter[num] - 1] = num; /
        counter[num]--;              
    }

    nums = res;
}

桶排序（bucket sort）

将待排序数组中的元素分散到若干个「桶」中，然后对每个桶中的元素再进行单独排序。

确定桶的数量：根据待排序数组的值域范围，将数组划分为 $k$ 个桶，每个桶可以看做是一个范围区间。
分配元素：遍历待排序数组元素，将每个元素根据大小分配到对应的桶中。
对每个桶进行排序：对每个非空桶内的元素单独排序（使用插入排序、归并排序、快排排序等算法）。
合并桶内元素：将排好序的各个桶中的元素按照区间顺序依次合并起来，形成一个完整的有序数组。

void bucketsort(vector<float> &nums) {
    // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    int k = nums.size() / 2;
    vector<vector<float>> buckets(k);
    // 1. 将数组元素分配到各个桶中
    for (float num : nums) {
        // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        int i = num * k;
        // 将 num 添加进桶 bucket_idx
        buckets[i].push_back(num);
    }
    // 2. 对各个桶执行排序
    for (vector<float> &bucket : buckets) {
        // 使用内置排序函数，也可以替换成其他排序算法
        sort(bucket.begin(), bucket.end());
    }
    // 3. 遍历桶合并结果
    int i = 0;
    for (vector<float> &bucket : buckets) {
        for (float num : bucket) {
            nums[i++] = num;
        }
    }
}

基数排序（radix sort）

将整数按位数切割成不同的数字，然后从低位开始，依次到高位，逐位进行排序，从而达到排序的目的。

基数排序算法可以采用「最低位优先法（least significant digit first）」或者「最高位优先法（most significant digit first）」。最常用的是「最低位优先法」。

确定排序的最大位数：遍历数组元素，获取数组最大值元素，并取得对应位数。
从最低位（个位）开始，到最高位为止，逐位对每一位进行排序：
1. 定义一个长度为 $10$ 的桶数组 $b u c k e t s$ ，每个桶分别代表 $\sim 9$ 中的 $1$ 个数字。
2. 按照每个元素当前位上的数字，将元素放入对应数字的桶中。
3. 清空原始数组，然后按照桶的顺序依次取出对应元素，重新加入到原始数组中。

/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
int digit(int num, int exp) {
    // 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num / exp) % 10;
}

/* 计数排序（根据 nums 第 k 位排序） */
void countingsortdigit(vector<int> &nums, int exp) {
    // 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
    vector<int> counter(10, 0);
    int n = nums.size();
    // 统计 0~9 各数字的出现次数
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp); // 获取 nums[i] 第 k 位，记为 d
        counter[d]++;                // 统计数字 d 的出现次数
    }
    // 求前缀和，将“出现个数”转换为“数组索引”
    for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
    }
    // 倒序遍历，根据桶内统计结果，将各元素填入 res
    vector<int> res(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        int d = digit(nums[i], exp);
        int j = counter[d] - 1; // 获取 d 在数组中的索引 j
        res[j] = nums[i];       // 将当前元素填入索引 j
        counter[d]--;           // 将 d 的数量减 1
    }
    // 使用结果覆盖原数组 nums
    for (int i = 0; i < n; i++)
        nums[i] = res[i];
}

/* 基数排序 */
void radixsort(vector<int> &nums) {
    int m = *max_element(nums.begin(), nums.end());

    for (int exp = 1; exp <= m; exp *= 10)

        countingsortdigit(nums, exp);
}

1122. 数组的相对排序

描述：给定两个数组， $a rr 1$ 和 $a rr 2$ ，其中 $a rr 2$ 中的元素各不相同， $a rr 2$ 中的每个元素都出现在 $a rr 1$ 中。

要求：对 $a rr 1$ 中的元素进行排序，使 $a rr 1$ 中项的相对顺序和 $a rr 2$ 中的相对顺序相同。未在 $a rr 2$ 中出现过的元素需要按照升序放在 $a rr 1$ 的末尾。

思路：计数排序

class solution {
public:
    vector<int> relativesortarray(vector<int>& arr1, vector<int>& arr2) {
        int upper = *max_element(arr1.begin(), arr1.end());
        vector<int> frequency(upper + 1);
        for (int x: arr1) {
            ++frequency[x];
        }
        vector<int> ans;
        for (int x: arr2) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans.push_back(x);
            }
            frequency[x] = 0;
        }
        for (int x = 0; x <= upper; ++x) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

0220. 存在重复元素 iii

描述：给定一个整数数组 $n u m s$ ，以及两个整数 $k$ 、 $t$ 。

要求：判断数组中是否存在两个不同下标的 $i$ 和 $j$ ，其对应元素满足 $\le t$ ，同时满足 $\le k$ 。如果满足条件则返回 true，不满足条件返回 false。

思路：用桶排序的思想

class solution {
public:
    int getid(int x, long w) {
        return x < 0 ? (x + 1ll) / w - 1 : x / w;
    }

    bool containsnearbyalmostduplicate(vector<int>& nums, int k, int t) {
        unordered_map<int, int> mp;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            long x = nums[i];
            int id = getid(x, t + 1ll);
            if (mp.count(id)) {
                return true;
            }
            if (mp.count(id - 1) && abs(x - mp[id - 1]) <= t) {
                return true;
            }
            if (mp.count(id + 1) && abs(x - mp[id + 1]) <= t) {
                return true;
            }
            mp[id] = x;
            if (i >= k) {
                mp.erase(getid(nums[i - k], t + 1ll));
            }
        }
        return false;
    }
};

0164. 最大间距

描述：给定一个无序数组 $n u m s$ 。

要求：找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 $2$ ，则返回 $0$ 。

思路：基数排序

class solution {
public:
    int maximumgap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        int exp = 1;
        vector<int> buf(n);
        int maxval = *max_element(nums.begin(), nums.end());

        while (maxval >= exp) {
            vector<int> cnt(10);
            for (int i = 0; i < n; i++) {
                int digit = (nums[i] / exp) % 10;
                cnt[digit]++;
            }
            for (int i = 1; i < 10; i++) {
                cnt[i] += cnt[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) {
                int digit = (nums[i] / exp) % 10;
                buf[cnt[digit] - 1] = nums[i];
                cnt[digit]--;
            }
            copy(buf.begin(), buf.end(), nums.begin());
            exp *= 10;
        }

        int ret = 0;
        for (int i = 1; i < n; i++) {
            ret = max(ret, nums[i] - nums[i - 1]);
        }
        return ret;
    }
};