快排&归并（C++实现）

分享一下个人的两个sort算法实现和其中的体会。

快排

#include 
#include 
using namespace std;

int rand_x(int max,int min)
{
    //return rand() % x;//返回x以内随机数
    /*上面是我个人犯的错，快排需要返回l到r范围内的随机数，
    而不是0到r，否则会导致排过的元素重新再排*/
    return (rand() % (max-min)+min);//返回min到max之间随机数
}
int partition(int a[], int l, int r)
{
    int p = a[l];
    int i = l + 1;
    for (int j = l + 1; j <= r; j++)//注意循环次数
    {
        if (a[j] < p)
        {
            swap(a[j], a[i]);
            i++;
        }
    }
    swap(a[l], a[i - 1]);
    return i - 1;
}
void QuickSort(int a[], int l, int r)
{
    if (l >= r)
    {
        return;
    }
    srand(time(NULL));
    int i = rand_x(r,l);
    swap(a[l], a[i]);
    int j = partition(a, l, r);
    QuickSort(a, l, j - 1);
    QuickSort(a, j + 1, r);
}
int main()
{
    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    QuickSort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        cout << a[i];
    }
    delete[] a;
    getchar();
    return 0;
}

归并

#include 
using namespace std;

void Merge(int a[], int l, int m, int r)
{
    int *b = new int[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r)
    {
        if (a[i] < a[j])
        {
            b[k++] = a[i++];
        }
        else
        {
            b[k++] = a[j++];
        }
    }
    while (i <= m)
    {
        b[k++] = a[i++];
    }
    while (j <= r)
    {
        b[k++] = a[j++];
    }
    for (i = l, k = 0; i <= r; i++, k++)
    {
        a[i] = b[k];
    }
    delete[] b;
}
void Mergesort(int a[], int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;
        Mergesort(a, l, m);
        Mergesort(a, m + 1, r);
        Merge(a, l, m, r);
    }
}
int main()
{
    int n = 0;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    Mergesort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << "  ";
    }
    delete[] a;
    getchar();
    return 0;
}

要点

• 取余可以得到小于取余数的结果。
• swap可以操作字符串，vector和数组元素。
• 快排中用两个端点，两个位置记号来分开基准元素、小于基准元素的元素、大于基准元素的元素、未排序的元素。
• 递归时抓住三要素：基本条件，函数功能，等价条件。可以先忽略函数实现，直接使用它的功能。
• 分析递归算法时间复杂度，当递归过程为标准递归，即每个递归调用都对相同长度子问题进行操作时可以用主方法。另外两种方法是代入法和递归树。
• 在设计函数时，考虑功能来决定返回类型和输入参数。

---

2021/4/30更新
在这劳动节前夕，大家浪的浪宅的宅就我在加训呜呜呜呜呜呜好在对快排有了更深的认识。
快排分三步：1确定参照点2划分区间3递归，显然划分区间是最难的。优雅的写法是双指针思想，左右两个指针相向移动的过程中进行交换。（不优雅的写法是另外开两个数组把左右区间塞进去然后再塞回去，显然emmmm）
需要注意的是，参照元素每次都选中间的要比选边界的快得多得多得多。虽然数学证明随机选择平均复杂度可达O(nlogn)，但是每次都随机的常数也蛮大的。

#include
using namespace std;
const int maxn=1e5+10;
int q[maxn];
void quick_sort(int *a,int l,int r)
{
    if(l>=r)return;
    int x=a[(l+r)/2],i=l-1,j=r+1;
    while(ix);
        if(i>n;
    for(int i=0;i>q[i];
    quick_sort(q,0,n-1);
    for(int i=0;i