快速排序

排序

快速排序

算法思想

分治

1. 确定分界点：头 、尾 、（头＋尾）/2、 随机
2. 调整区间，使得小于分界点的数全在其左边，大于分界点的数全在右边
   • 利用两个指针在数列两头向中间移动，左边的指针在碰到大于等于分界点时停下，右边的指针反之，都停下时交换两数，循环上述过程，直到两指针相交
3. 递归处理左右两端

题目:
快速排序

完整代码:

#include <iostream>
using namespace  std;
const int N = 1e6+10;//加10防止越界
int n;
int q[N];
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);
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",q[i]);
    return 0;
}

代码模板：

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);
}

注意

若x取q[l]或者q[r]要考虑边界问题
若 递归处用 i-1 和 i ,则x不可以取q[l] ,可以取q[r]或者q[(l+r+1)/2]或者q[l+r+1>>1]等
若 递归处用 j 和 j+1 ,则x不可以取q[r] ,可以取q[l]或者q[(l+r)/2]或者q[l+r>>1]等
否则可能会出现死循环
例如:x取q[l],递归处用i-1和i,排序12,会无限调用递归quick_sort(q,0,1),即无限划分

快排是不稳定的
在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法（但其实没软用）
如何把快排变成稳定的呢—————把快排每个数变成不同的，可把每个数据弄成二元组，双关键字排序

分析

边界问题分析
分治算法最怕n分成0和n,或n分成n和0,这会造成无限划分
若x=q[l]时 最极端情况是i=l,j=l 此时若划分为(l,i-1)和(i,r) 其中(i,r)划分的就是n 这就出现了无限划分
若x=q[r]时 最极端情况时i=r,j=r 此时若划分为(l,j)和(j+1,r) 其中(l,j)划分的就是n 这就出现了无限划分
最后是关于q[l+r>>1]和q[l+r+1>>1] 的问题,
q[l+r+1>>1]是向上取整,因为向上取整时有可能取到q[r],为了避免无限划分,所以递归处划分应该是i-1和i
q[l+r>>1]是向下取整,因为向下取整时有可能取到q[l],为了避免无限划分,所以递归处划分应该时j和j+1

最后
为什么y总要const int N = 1e6+10; 要加10呢 我也没懂 但参考:知乎

归并排序

算法思想

分治

1. 确定分界点：mid=l+r>>1
2. 递归排序left，right
3. 归并————合二为一

注意