快速排序

时间复杂度平均：O(nlogn)，最差O(n^2)；空间复杂度O(logn)

快排时间复杂度分析（归并排序时间复杂度类似，我们每一步的关键操作就是合并有序数组，迭代层数如下分析）：

快排关键操作就是每次选择一个中轴线，然后把小于中轴线的元素放到左边，剩余放右边。这是每一层我们要做的关键操作

递归的第一层，n个数被划分为2个子区间，每个子区间的数字个数为n/2；
递归的第二层，n个数被划分为4个子区间，每个子区间的数字个数为n/4；
递归的第三层，n个数被划分为8个子区间，每个子区间的数字个数为n/8;

......

递归的第logn层，n个数被划分为n个子区间，每个子区间的数字个数为1；

每一层我们都需要遍历所有n个元素并进行移动操作，因此时间复杂度是O(nlogn)

1、快速排序模板

注意的边界问题较多

注意点1：每次传进来quick( a, 0, n-1)，在qucik内部，需要设置i = l - 1，j = r + 1来保证边界问题
注意点2：枢纽x一旦定下来就不能变，因此x=mid[(l+r)/2]是预先就要设置好的
注意点3：我们在while( i < j )内部嵌套的是do ; while循环
注意点4：最后递归时，分两个区间，[ l , j ]和[ j+1 , r ]

// 关键代码
void quick(int a[],int l,int r){
    if(l>=r) return;

    int i=l-1,j=r+1;
    int x=a[(l+r)/2];
    while(i<j){
        do(i++); while(a[i]<x);
        do(j--); while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }

    quick(a,l,j);
    quick(a,j+1,r);
}

2、快速排序应用——第K个数

使用快排模板，并在其中加入k这一参数

// 关键代码
int quick(int a[],int l,int r,int k){
    if(l>=r) return a[l];

    int i=l-1,j=r+1;
    int x=a[(l+r)/2];

    while(i<j){
        do(i++); while(a[i]<x);
        do(j--); while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }

    //下标从0开始，因此len=j-l+1
    int len=j-l+1;
    //这里带等号，即第len个数是在l-j之中
    if(k<=len) quick(a,l,j,k);
    //否则下标变成k-len
    else quick(a,j+1,r,k-len);
}

3、链表快速排序

归并排序

时间复杂度平均：O(nlogn)；空间复杂度O(n)

1、归并排序模板

注意点如下：

注意点1：归并排序先递归，再处理
注意点2：归并排序采用双指针算法，如果一个数组没处理完就将所有结果追加入s数组中
注意点3：最后不要忘记将s内的元素更新到a之中

// 关键代码
void merge(int a[],int l,int r){
    if(l>=r) return;

    int mid=(l+r)/2;
    int i=l,j=mid+1;
    int k=0;

    merge(a,l,mid);
    merge(a,mid+1,r);

    while(i<=mid && j<=r){
        if(a[i]<a[j]) s[k++]=a[i++];
        else s[k++]=a[j++];
    }

    while(i<=mid) s[k++]=a[i++];
    while(j<=r) s[k++]=a[j++];

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

2、归并排序应用——逆序对数量

这里我们利用归并排序中局部有序的性质，来进行逆序对的统计

注意点1：记得在merge中返回res
注意点2：记得返回long long
注意点3：当a[i]>a[j]时进行res统计

// 关键代码
long long merge(int a[],int l,int r){
    if(l>=r) return 0;

    int mid=(l+r)/2;
    int i=l,j=mid+1;
    int k=0;

    long long res=merge(a,l,mid)+merge(a,mid+1,r);

    while(i<=mid && j<=r){
        if(a[i]<=a[j]) s[k++]=a[i++];
        else {
            res+=mid-i+1;
            s[k++]=a[j++];
        }
    }

    while(i<=mid) s[k++]=a[i++];
    while(j<=r) s[k++]=a[j++];

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

    return res;
}

3、链表归并排序

堆排序

时间复杂度平均：O(nlogn)；空间复杂度O(1)

1、堆排序模板

注意点1：由于我们要利用完全二叉树性质，因此我们数组下标从1开始
注意点2：我们在构建堆时，从第n/2个元素开始向前构建
注意点3：每次输出最小值(堆顶)元素后，和堆末尾元素交换，总量-1。并且对新堆顶再进行down操作

// 关键代码
// 构建堆
for(int i=n/2;i>=1;i--){
    down(i);
}
// 输出最小值
for(int i=0;i<m;i++){
    cout<<h[1]<<" ";
    swap(h[1],h[n]);
    n--;
    down(1);
}
// 堆排序down操作
void down(int u){
    int t=u;
    if(2*u<=n && h[2*u]<h[t]) t=2*u;
    if(2*u+1<=n && h[2*u+1]<h[t]) t=2*u+1;
    if(t!=u){
        swap(h[t],h[u]);
        down(t);
    }
}