Homepage of Jinghua Xu

排序

快速排序

主要思想：分治

时间复杂度：O(n*log{2}{n})【平均时间复杂度，最快可以达到n^2】

e.g. 对数组q的序号l至r区域进行排序

1. 确定分界点x（数值）：常用——左边界q[l]、**中心点处值q[(l+r)/2]**、右边界q[r]、随机
2. 调整区间：使所有小于（等于）x的值均位于x左侧，所有大于（等于）x的值都位于x右侧（区间内不要求有序）
   • 暴力做法（时间复杂度仍为O(n)，但会额外耗费空间）：
     1. 新开两个数组a[]，b[]
     2. 对数组q的序号l至r区间进行扫描：
        • 若q[i]≤x，将q[i]放入a[]
        • 若q[i]≥x，将q[i]放入b[]
     3. 将a[]、b[]依次放回q[]中
   • 推荐做法（使用指针）：
     1. 从左边界q[l]处开始，使用指针i向右侧移动，若指针指向的数值大于等于x，停下
     2. 从右边界q[r]处开始，使用指针j向左侧移动，若指针指向的数值小于等于x，停下
     3. 交换指针i、j处的数值
     4. 重复1、2、3步骤（在移动后的指针i、j位置基础上继续向右/左侧移动），直到两个指针相遇
3. 递归处理左右两段

---

例题：785. 快速排序 - AcWing题库

给定一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

#include <iostream>

using namespace std;

const int N = 100010; // 保险，防止边界问题

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    //判定边界：区间内只有一个数或没有数时不需要排序
    if (l >= r)
        return;
    
    int x = q[(l + r) / 2], i = l - 1, j = r + 1; //取分界值
    //注意：由于每次完成交换（包括初始状态）都自动向中间移动一格，初始时要将两侧指针取在区间外侧1个单位
    while (i < j) //迭代：移动+交换
    {
        do
            i ++ ;
        while (q[i] < x);
        do
            j -- ;
        while (q[j] > x);
        if (i < j)
        {
            //交换两数:swap(q[i], q[j]);
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
    }
    
    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;
}

归并排序

主要思想：分治

时间复杂度：O(n*log{2}{n})

• 时间复杂度计算：每次递归将当前序列分为2份（原序列->2份->4份->8份->……），直到每一份的长度为1时停止；显然这样的递归需要进行log{2}{n}轮，而对于每一轮而言又需要进行时间复杂度为O(n)的归并，因此整体排序算法的时间复杂度为两者相乘，即O(n*log{2}{n})

e.g. 对数组q的序号l至r区域进行排序

1. 确定分界点：以数组中心点mid = (l+r)/2为分界点，将数组q分成Left、Right两部分
2. 对两部分进行递归排序，使其各自成为有序序列
3. 归并：将两个有序数组合并成一个有序数组
   • 双指针算法（时间复杂度为O(n)）：
     1. 对于两个有序数组Left、Right而言，分别在其左端点处放置一个指针
     2. 比较两个数组指针处数值的大小，将更小的那一个放入输出的目标数组（初始为空）
        • 注意：若两个数组指针处数值大小相等，则优先将数组Left中的数值放入输出目标数组，则可保证排序算法的稳定
        • 排序算法的稳定：排序完成后，原数组中值相同的数之间的相对位置不变（归并排序稳定，快速排序不稳定；若想使快速排序稳定，需要在对数值排序的基础上对各元素在原数组中的位置序号进行排序）
     3. 对于更小的数值所在的数组而言，将指针向后移一位，重复步骤2（依次排入输出目标数组中）
     4. 重复步骤3，直到某个数组中所有的数全部被放入输出目标数组，则跳出循环，将另一个数组的所有剩余数值依次排入输出目标数组中，归并完成