排序

排序

1、快速排序

思路：

（1）定义出口
（2）选取一个随机点，以及确定左右边界
（3）i，j两个指针从左右两个边界向中间移动
（3.1）左指针找到需要交换的值（大于参考点的值），就停下来
（3.2）右指针找到需要交换的值（小于参考点的值），就停下来
（3.3）当两个指针都停下来，且i指针在j指针左边时，交换两个值
（4）递归将每一个部分都进行同样的操作，直至细分到最小时，就满足了整个区间从左到右有序排列

代码模板：

void quick_sort(int q[], int l, int r)
{
    //边界条件 
    if(l>=r)return;                         //当左指针大于等于右指针说明两指针已经遍历了全部数据 
    //确定分界点 
    int x=q[l+r>>1], i= l - 1 ,j = r + 1;        //随机选取一个数据中的值作为参考值  用i,j表示左右指针，但注意定义时，需要定义在数据外围外 
    while(i < j)
    {
        do i++ ; while(q[i]<x);          //直到找到第一个不小于参考值x的值，左指针停止 ， 否则左指针不断后移 
        do j-- ; while(q[j]>x);          //直到找到第一个不大于参考值x的值，右指针停止 ， 否则右指针不断左移 
        if(i < j)swap(q[i],q[j]);        //当左右指针都停下，则说明两指针都找到了需要交换的值，则交换两值 
    }

    quick_sort(q, l, j);                 //将左边部分作为一个新串传入， 
    quick_sort(q, j+1, r);               //将右边部分作为一个新串传入， 
    //经过上面的递归则可以完成整个数据的排序 

}

2、归并排序

思路：

（1）定义出口 l >= r
（2）先确定中间点，然后进行左右区间的递归，此时返回的序列为两个有序序列
（3）定义左右两个序列的开头
（4）同时遍历左右两个序列，每次将两个序列中最小的值拿出来，放到答案里（由于此时两个序列都是有序序列，所以只需要比较两个序列的开头就行了）
（5）判断两个序列是否还有元素没有加入，有则直接全部加入即可
（6）最后将排好序的数组重新赋值给原数组即可

代码模板：

void merge_sort(int q[], int l, int r)  
{
    if (l >= r) return;     //出口

    int mid = (l + r) >> 1;     //确定分界点
    int k = 0;  //用于计算存到了多少个了

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);       //将序列递归成两个有序序列

    int i = l, j = mid + 1;     //定义左右序列的开头

    while (i <= mid && j <= r)  //判断两个序列是否有一个序列已经遍历完成
    {
        if (q[i] <= q[j]) temp[k ++] = q[i++];
        else temp[k ++] = q[j++];
    }

    while (i <= mid) temp[k ++] = q[i++];   //将剩余序列的元素直接加入
    while (j <= r) temp[k ++] = q[j++];

    for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = temp[j]; //将数组复原
}