七、排序

0x00 直接插入排序

给定一个整数数组 nums，将该数组升序排列。

以第一个元素作为有序数组，其后的元素通过在这个已有序的数组中找到合适的位置并插入

空间：O(1)

最好：O(n)，初始为有序时

最坏：O(n^2) ，初始为是逆序时

平均：O(n^2)

稳定性：是

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for(int i = 1,j; i < n; i++){//此时0~i-1已有序
            int v = nums[i];//i位置元素待插入
            for(j = i-1; j>=0&&v<nums[j]; j--){//向前寻找插入位置
                nums[j+1]=nums[j];
            }
            nums[j+1] = v;//插入
        }
        return nums;
    }
0x01 折半插入排序

给定一个整数数组 nums，将该数组升序排列。

与直接插入排序的唯一区别就是 查找插入位置时 使用二分，复杂度不变

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for(int i = 1; i < n; i++){//此时0~i-1已有序
            int v = nums[i];//i位置元素待插入

            int l = 0, r = i-1;//二分查找插入位置
            while(l<r){
                int mid = l+r+1 >> 1;
                if(nums[mid]<=v) l = mid;
                else r = mid-1;
            }
            if(nums[l]>v) l--;//防止在单个元素中二分的情况
            //此时的l即为插入位置的前一个位置

            for(int j = i-1; j > l; j--) nums[j+1] = nums[j];//后移
            nums[l+1] = v;//插入
        }
        return nums;
    }
0x02 希尔排序

给定一个整数数组 nums，将该数组升序排列。

类插入排序，只是向前移动的步数变成d，插入排序每次都只是向前移动1。

空间：O(1)

平均：当n在特定范围时为 O(n^1.3)

稳定性：否

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for (int d = n / 2; d >= 1; d /= 2) {//d为增量 d=1时就是0x00的插入排序
            for (int i = d,j; i < n; i++) {
                int v = nums[i];//i位置元素待插入
                for (j = i-d; j >= 0 && v < nums[j]; j -= d) {//以增量d向前寻找插入位置
                    nums[j+d] = nums[j];
                }
                nums[j+d] = v;
            }
        }
        return nums;
    }
0x03 冒泡排序

给定一个整数数组 nums，将该数组升序排列。

通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的最大值

空间：O(1)

最好：O(n)，初始即有序时 一趟冒泡即可

最坏：O(n^2)， 初始为逆序时

平均：O(n^2)

稳定性：是

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        bool sorted = false;//无序
        for(int i = n-1; i >=0 && !sorted; i--){//0~i为无序区 
            sorted = true;//假定已有序
            for(int j = 0; j < i; j++){//相邻比较 大的沉底
                if(nums[j]>nums[j+1]) swap(nums[j],nums[j+1]),sorted = false;//发生交换 则无序
            }
        }
        return nums;
    }
0x04 快速排序

给定一个整数数组 nums，将该数组升序排列。

选择一个元素作为基数（通常是第一个元素），把比基数小的元素放到它左边，比基数大的元素放到它右边（相当于二分），再不断递归基数左右两边的序列。

空间：O(log n)，即递归栈深度

最好：O(nlog n) ，其他的数均匀分布在基数的两边，此时的递归就是不断地二分左右序列。

最坏：O(n^2) ，其他的数都分布在基数的一边，此时要划分n次了，每次O(n)

平均：O(nlog n)

稳定性：否

    void quick_sort(vector<int>& nums, int l , int r){//对下标为 l~r部分 排序
        if(l >= r ) return ;
        int x = nums[l], i = l-1, j = r+1;//x为划分中枢 i为左半起点 j为右半起点
        while(i < j){
            while(nums[++i] < x);//左边寻大于x的数
            while(nums[--j] > x);//右边寻小于x的数
            if(i < j) swap(nums[i],nums[j]);//每次把左边大于x的数和右边小于x的交换即可
        }
        quick_sort(nums,l,j),quick_sort(nums,j+1,r);
        //因为结束时i在j的右边 j是左半段的终点,i是右半段的起点
    }
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        quick_sort(nums,0,n-1);
        return nums;
    }
0x05 快排应用-第k大数

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

    int quick_select(vector<int>& nums, int l , int r, int k){
                                  //在下标为l~r的数中求第k大的数
        if(l >= r) return nums[l];
        int x = nums[l], i = l-1, j = r+1;
        while(i < j){//以x为枢纽 一次快排划分 此处大的在左边 小的在右边
            while(nums[++i] > x);
            while(nums[--j] < x);
            if(i < j) swap(nums[i],nums[j]);
        }
        int sl = j-l+1;//左半区间的长度
        if(sl>=k) return quick_select(nums, l,j,k);
        //k<=左半区间长度,则第k大数必然在左半段 并且是左半段的第k大数
        else return quick_select(nums, j+1, r, k - sl);
        //第k大数必然在右半段 并且是右半段的第k-sl大数
    }
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quick_select(nums,0,n-1,k);
    }
0x06 选择排序

给定一个整数数组 nums，将该数组升序排列。

和冒泡排序相似，区别在于选择排序是直接挑出未排序元素的最大值放后面，其它元素不动。无论如何都要O(n^2)

最好：O(n^2)

最坏：O(n^2)

平均：O(n^2)

稳定性：否

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for(int i = n-1; i >=0; i--){//0~i为无序部分
            int minpos = -1;
            for(int j = 0; j <= i; j++){//寻找0~i区间内的最大值的位置
                if(minpos ==-1||nums[j]>nums[minpos]) minpos = j;
            }
            swap(nums[i],nums[minpos]);//把挑出最大值放到后面
        }
        return nums;
    }
0x07 堆排序

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式 第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式 共一行，包含m个整数，表示整数数列中前m小的数。

输入样例：

5 3

4 5 1 3 2

输出样例：

1 2 3

根据数组建立一个堆（类似完全二叉树），每个结点的值都大于左右结点（大根堆，通常用于升序），或小于左右结点（小根堆堆，通常用于降序）。

空间：O(1)

最好：O(nlog n)，log n是调整小根堆所花的时间

最坏：O(nlog n)

平均：O(nlog n)

稳定性：否

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N];//堆
int n,m;
void down(int x){//小根堆 下调
    int p = x*2;//左孩子下标
    while(p <= n){
        if(p + 1 <=n && h[p+1] < h[p]) p++;//找到子节点的最小值
        if(h[x]<=h[p]) return;//调整完毕
        swap(h[x],h[p]);
        x = p;
        p = x*2;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&h[i]);
    for(int i = n/2; i >=1; i--) down(i);//建堆,从最后一个叶子的父节点开始调整即可
    while(m--){
        printf("%d ",h[1]);//堆顶即为最小值
        swap(h[1],h[n]),n--,down(1);//删除堆顶
    }
    return 0;
}
0x08 归并排序

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

递归将数组分为两个有序序列，再合并这两个序列

空间: O(n) 辅助备份数组

最好：O(nlog n)

最坏：O(nlog n)

平均：O(nlog n)

稳定性：是

输入样例：

5

3 1 2 4 5

输出样例：

1 2 3 4 5

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],t[N];//原数组 t为归并的辅助数组
void merge_sort(int l, int r){//将l~r从小到大排序
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l,mid),merge_sort(mid+1,r);//左右部分别排好序
    //合并左右两部分 ，k为待填充位置 每次选最小的去填
    //i为左部分的起始下标 j为右部边的起始下标 mid为左部分的边界
    for(int k = l,i = l, j = mid+1; k <= r; k++){
        if(j > r||i <= mid&&a[i] <= a[j]) t[k] = a[i++];//选择左部分的值去填的条件
        else t[k] = a[j++];//否则只能选右半部分了
    }
    for(int i = l; i <= r; i++) a[i] = t[i];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    merge_sort(0,n-1);
    printf("%d",a[0]);
    for(int i = 1; i < n; i++) printf(" %d",a[i]);
    return 0;
}
0x09 归并排序的应用-逆序对的数量

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入样例：

6

2 3 4 5 6 1

输出样例：

5

解释:逆序对分别为 (2,1)(3,1)(4,1)(5,1)(6,1)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010; 
int a[N],t[N];
LL ans;//逆序对数量
void merge_sort(int l, int r){//l~r从小到大排 排序过程中统计逆序对数量
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    for(int k = l,i=l,j=mid+1; k <= r; k++){
        if(j > r|| i<= mid&&a[i]<=a[j]) t[k] = a[i++];
        else ans += mid-i+1LL,t[k] = a[j++];
        //此时arr[i]>arr[j] 逆序 统计逆序对数量  则arr[i~mid]的元素均大于arr[j]构成逆序
    }
    for(int i = l; i <= r; i++) a[i] = t[i];
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    merge_sort(0,n-1);
    printf("%lld",ans);
    return 0;
}
0x0a 基数排序

使用十个桶0-9，把每个数从低位到高位根据位数放到相应的桶里，以此循环最大值的位数次。

只能排列正整数，因为遇到负号和小数点无法进行比较。

空间：O(r) r个队列

最好：O(d(n+r)) d趟分配收集 一趟分配O(n)收集O(r)

最坏：O(d(n+r))

平均：O(d(n+r))

稳定性：是

void radixSort(int arr[]) {
    int _max = (*max_element(arr, arr+len));
        // 计算最大值的位数
        int maxDigits = 0; 
        while(_max) {
        maxDigits++;
        _max /= 10;
    }
    // 标记每个桶中存放的元素个数
    int bucketSum[10];
    memset(bucketSum, 0, sizeof(bucketSum));
    int div = 1; 
    // 第一维表示位数即0-9，第二维表示里面存放的值
    int res[10][1000];
    while(maxDigits--) {
        int digit;
        // 根据数组元素的位数将其放到相应的桶里，即分配
        for(int i=0; i<len; i++) {
            digit = arr[i] / div % 10;
            res[digit][bucketSum[digit]++] = arr[i];
        }
        // 把0-9桶里的数放回原数组后再进行下一个位数的计算，即收集
        int index = 0;
        for(int i=0; i<=9; i++) {
            for(int t=0; t<bucketSum[i]; t++) {
                arr[index++] = res[i][t];
            }
        }
        memset(bucketSum, 0, sizeof(bucketSum));
        div *= 10;
    }
}