快速排序and归并排序

1.快速排序

快速排序的思想分治

• 确定轴值(分界点)，可以是q[l]、q[l+r>>1](建议用这个)、q[r]
• 根据轴值划分
• 递归左右子划分

快排结束即已经是合并完的情况，所以已经完成子问题合并

代码分析

//快速排序函数
void quick_sort(int a[], int l, int r)//待排序列，左端点，右端点
{
    //序列中只有一个数或者没有数结束
    if (l >= r) return;
	
    //i j双指针来划分，pivot轴值
    int i = l - 1, j = r + 1, pivot = a[(l + r) >> 1];

    //双指针交换思想
    while (i < j)
    {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i < j) swap(a[i], a[j]);
    }
	
    //递归左右子序列
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

思想

• 双指针划分

  左右两端设置两个指针，两指针向中间移动，左指针找到一个不属于左区间的数，右指针找到一个不属于右区间的一个数，将两者交换，直到两指针相遇循环结束就完成了划分

• 递归时的子区间

  当分为[l,j]和[j + 1,r]时，轴值可以取q[l]或q[(l + r) >> 1]

  当分为[l,i - 1]和[i,r]时，轴值可以取q[(l + r + 1) >> 1]

  其他递归区间和轴值选取都会有边界问题，建议记住第一个即可

2.归并排序

归并排序的思想分治

• 确定分界点mid=l+r>>1
• 递归排序左右区间
• 归并

代码分析

int q[N], tmp[N];//需要中间数组辅助归并的过程

void merge_sort(int q[], int l, int r)//待排序列，左端点，右端点
{
    //序列中只有一个数或者没有退出递归
    if (l >= r) return;

    //分界点为中点，mid为下标
    int mid = l + r >> 1;

    //递归左右区间
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    //归并
    int k = 0, i = l, j = mid + 1;//k下标,i j双指针
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while (i <= mid) tmp[k++] = q[i++];//归并剩下的数
    while (j <= r) tmp[k++] = q[j++];//归并剩下的数

    //注意i从左端点开始
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];//复制回q数组
}

思想

• 双指针

  不同于快速排序的双指针，归并运用同向双指针，快排运用双向双指针