快速排序

快速排序的边界条件过多，建议包括细节原封不动背下来

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];

void quickSort(int a[],int l,int r)
{
    if(l>=r)
    {
        return;
    }
    //1.确定支点
    int i = l-1;  //因为是dowhile，必定先往前走一次，所以是l-1，r+1
    int j = r+1;
    int x = a[l + r >> 1];    //pivot取中间值，因为二进制数右移一位是/2，所以l+r>>1

    //2.调整区间
    while(i<j)
    {
        do
        {
            i ++ ; 
        }while (a[i] < x);   //不能有等于号
        do 
        {
            j -- ;
        }while (a[j] > x);   //不能有等于号
        if (i < j)
        {
            swap(a[i], a[j]);
        }
    }

    //3.递归左右两段
    quickSort(a,l,j);
    quickSort(a,j+1,r);
}

int main()
{
    int n;   //写在main里面
    scanf("%d",&n);     //数据大尽量用scanf printf
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }

    quickSort(a,0,n-1);

    for(int i = 0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;   
}

思路

1. 确定分界点（支点）pivot。常用方法是取左边界a[l]或右边界a[r]或中点a[(l+r)/2]，写代码的时候我们避免出现某些边界问题，所以就选择用中点a[(l+r)/2]

   注意：写a[(l+r)/2]是AC不了的（亲身实验，但不知道为什么,可能位运算比除法快？）

   我们用a[l + r >> 1]来代替。

   解释：因为二进制数向右移动一位表示除2，例如十进制的5，101右移一位是10，从5变成了2，即相当于5/2；故l+r>>1就相当于(l+r)/2。

2. 调整区间。使得左边的数都是小于pivot的，右边的数都是大于pivot的。

3. 递归处理左右两段（重复1，2）

调整区间的方法：

两个指针相向移动，i找的是比pivot大的值然后停下，j找的是比pivot小的元素然后停下。两个指针指向的元素交换位置，这两个元素即可到达各自应该处于的位置。

快速排序的时间复杂度：

平均：O(nlogn)
最快：O(nlogn)
最慢：O(n2 )

归并排序

1. 确定分界点（中点） mid = (l+r)/2
2. 递归排序左右两段
3. 归并，合二为一。

合并方法：开一个结果数组存放结果。两个待合并子数组中，双指针，逐个比较，选了谁进结果数组，对应的指针就往后挪一位。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int a[N];
int temp[N];   //用来保存归并结果的数组

void mergeSort(int a[], int l, int r)
{
    if(l>=r) return;  //边界条件
    //1.确定分界点
    int mid = l + r >> 1;
    //2.递归左右两段
    mergeSort(a,l,mid);
    mergeSort(a,mid+1,r);
    //3.合并排序好的两段
    int k = 0;  //用于表示temp数组中有多少个元素,别忘了赋初值0
    int i = l;  //定义两个指针，分别指向两段子数组的初始位置
    int j = mid+1;
    while(i<=mid && j<=r)
    {
        if(a[i]<a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++];
        }
    }

    while(i<=mid)   //两个子数组合并后其中有一个数组还剩下元素没有进入temp的情况
    {
        temp[k++] = a[i++];
    }
    while(j<=r)
    {
        temp[k++] = a[j++];
    }

    for(int i = 0,j = l;i<k;i++,j++)
    {
        a[j] = temp[i];
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    mergeSort(a,0,n-1);
    for(int i= 0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

快速排序和归并排序的一些区别和联系

1. 可以看出，快速排序是最后一步递归分治，而合并排序是先递归，再进行合并处理
2. 两个mid不一样，快排里的mid是指数组中间位置的数，而归并排序指的是数组中间的下标
3. 只要记住快速排序和归并排序各自的三个步骤，代码就很好写出来了

快速选择算法

• 比如我们要求一个数组中的第k小的数时，可以用快速排序后输出第k个数，这样的时间复杂度是O(nlogn)；现在我们有一种O(n)的做法：快速选择算法

• 快排的第三步需要分别对左右两段进行递归，但是快选只需要判断k与左边子数组元素个数的关系。若k大于左边子数组元素，则说明第k小的数在右边，我们只需要递归右边的子数组。反之，若k<=左边元素的个数，则递归左边的子数组。即每次都只需要递归一边。

例题：原题链接

//快速选择算法
#include <bits/stdc++.h>
using namespace std;
const int N =100010;
int a[N];
int k;
int n;
int quickSort(int l,int r,int k)
{
    if(l==r) return a[l];
    int x = a[l+r>>1];
    int i = l-1;
    int j = r+1;
    while(i<j)
    {
        do i++; while(a[i]<x);
        do j--; while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    int sl = j - l + 1;  //因为左边区间是[l,j],所以左边的元素个数是j-l+1
    if(k<=sl) return quickSort(l,j,k);  //递归左边
    else return quickSort(j+1,r,k-sl);   
    //递归右边，左边sl个数全是小于第k个的，所以是求右边的第k-sl小
}
int main()
{
    cin>>n>>k;
    for(int i = 0;i<n;i++) cin>>a[i];
    cout<<quickSort(0,n-1,k)<<endl;
    return 0;
}