排序专题

稳定性的概念：稳定性是指相等的元素经过排序之后相对顺序是否发生了改变。
c++中sort函数是非稳定的，stable_sort函数是稳定的。

稳定排序：基数排序、计数排序、插入排序、冒泡排序、归并排序
非稳定排序：选择排序、堆排序、快速排序、希尔排序

排序算法时间复杂度：

1.插入排序

void insert_sort()
{
    for (int i = 1; i < n; i ++ )
    {
        int x = a[i];
        int j = i-1;

        while (j >= 0 && x < a[j])
        {
            a[j+1] = a[j];
            j -- ;
        }
        a[j+1] = x;
    }
}

2选择排序

void select_sort()
{
    for (int i = 0; i < n; i ++ )
    {
        int k = i;
        for (int j = i+1; j < n; j ++ )
        {
            if (a[j] < a[k])
                k = j;
        }
        swap(a[i], a[k]);
    }

}

3冒泡排序

void bubble_sort()
{
    for (int i = n-1; i >= 1; i -- )
    {
        bool flag = true;
        for (int j = 1; j <= i; j ++ )
            if (a[j-1] > a[j])
            {
                swap(a[j-1], a[j]);
                flag = false;
            }
        if (flag) return;
    }
}

4希尔排序

void shell_sort()
{
    for (int gap = n >> 1; gap; gap >>= 1)
    {
        for (int i = gap; i < n; i ++ )
        {
            int x = a[i];
            int j;
            for (j = i; j >= gap && a[j-gap] > x; j -= gap)
                a[j] = a[j-gap];
            a[j] = x;
        }
    }
}

5快速排序（最快）

void quick_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    //第二步：递归处理子问题
    quick_sort(q, l, j), quick_sort(q, j + 1, r);

    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}

6归并排序

void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}

7堆排序（须知此排序为使用了模拟堆，为了使最后一个非叶子节点的编号为n/2，数组编号从1开始）
https://www.cnblogs.com/wanglei5205/p/8733524.html

void down(int u)
{
    int t = u;
    if (u<<1 <= n && h[u<<1] < h[t]) t = u<<1;
    if ((u<<1|1) <= n && h[u<<1|1] < h[t]) t = u<<1|1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}
int main()
{
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = n/2; i; i -- ) down(i);
    while (true)
    {
        if (!n) break;
        cout << h[1] << ' ';
        h[1] = h[n];
        n -- ;
        down(1);
    }
    return 0;
}

8基数排序

int maxbit()
{
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int cnt = 1;
    while (maxv >= 10) maxv /= 10, cnt ++ ;

    return cnt;
}
void radixsort()
{
    int t = maxbit();
    int radix = 1;

    for (int i = 1; i <= t; i ++ )
    {
        for (int j = 0; j < 10; j ++ ) count[j] = 0;
        for (int j = 0; j < n; j ++ )
        {
            int k = (a[j] / radix) % 10;
            count[k] ++ ;
        }
        for (int j = 1; j < 10; j ++ ) count[j] += count[j-1];
        for (int j = n-1; j >= 0; j -- )
        {
            int k = (a[j] / radix) % 10;
            temp[count[k]-1] = a[j];
            count[k] -- ;
        }
        for (int j = 0; j < n; j ++ ) a[j] = temp[j];
        radix *= 10;
    }

}

9计数排序

void counting_sort()
{
    int sorted[N];
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int count[maxv+1];
    for (int i = 0; i < n; i ++ ) count[a[i]] ++ ;
    for (int i = 1; i <= maxv; i ++ ) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i -- )
    {
        sorted[count[a[i]]-1] = a[i];
        count[a[i]] -- ;
    }
    for (int i = 0; i < n; i ++ ) a[i] = sorted[i];
}

10桶排序（基数排序是桶排序的特例，优势是可以处理浮点数和负数，劣势是还要配合别的排序函数）

vector<int> bucketSort(vector<int>& nums) {
    int n = nums.size();
    int maxv = *max_element(nums.begin(), nums.end());
    int minv = *min_element(nums.begin(), nums.end());
    int bs = 1000;
    int m = (maxv-minv)/bs+1;
    vector<vector<int> > bucket(m);
    for (int i = 0; i < n; ++i) {
        bucket[(nums[i]-minv)/bs].push_back(nums[i]);
    }
    int idx = 0;
    for (int i = 0; i < m; ++i) {
        int sz = bucket[i].size();
        bucket[i] = quickSort(bucket[i]);
        for (int j = 0; j < sz; ++j) {
            nums[idx++] = bucket[i][j];
        }
    }
    return nums;
}

第一题： 线性查找第K个元素

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m,k;
int s[50000010];
int quick_sort(int l,int r,int k)
{
    if(l==r) return s[l];
    int mid=s[(l+r)>>1];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
        do i++;while(s[i]>mid);
        do j--;while(s[j]<mid);
        if(i<j) swap(s[i],s[j]);
    }
    int num=j-l+1;
    if(k<=num) quick_sort(l,j,k);
    else quick_sort(j+1,r,k-num);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    cin>>s[1]>>s[2];
    for(int i=3;i<=n;i++)
    {
        ll x=s[i-2];
        x=x*s[i-1]%m;
        s[i]=x;
    }
    int t=quick_sort(1,n,k);
    cout<<t<<endl;
    return 0;
}