排序算法：通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。

总览

排序算法最好情况平均情况最坏情况空间占用稳定性
冒泡排序 (Bubble sort)$n$$n^2$$n^2$$1$$\text{Y}$
选择排序 (Selection sort)$n^2$$n^2$$n^2$$1$$\text{N}$
插入排序 (Insertion sort)$n$$n^2$$n^2$$1$$\text{Y}$
希尔排序 (Shellsort)$n\log n$$n^{4/3}$$n^{3/2}$$1$$\text{N}$
归并排序 (Merge sort)$n\log n$$n\log n$$n\log n$$n$$\text{Y}$
快速排序 (Quicksort)$n\log n$$n\log n$$n^2$$\log n$$\text{N}$
堆排序 (Heapsort)$n\log n$$n\log n$$n\log n$$1$$\text{N}$
计数排序 (Counting sort)$-$$n+r$$n+r$$n+r$$\text{Y}$
桶排序 (Bucket sort)$-$$n+r$$n+r$$n+r$$\text{Y}$

冒泡排序

（下面均以递增数列为例）在未排序的部分中，若前面的数比后面大则交换，从头操作到尾。每进行一次外层循环可使一个最大的数归位，从整个数列从尾操作到头即可完成排序。

void bubble_sort(int arr[], int l, int r)
{
    for (int i = r; i >= l + 1; i--)
    {
        bool swapped = false;
        for (int j = l + 1; j <= i; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                swap(arr[j - 1], arr[j]);
                swapped = true;
            }
        }
        if (!swapped)
            return;
    }
}

选择排序

在未排序部分中找到最小的的值，将其放到未排序部分的最左侧。从头到尾循环操作即可完成排序。

void selection_sort(int arr[], int l, int r)
{
    for (int i = l; i <= r - 1; i++)
    {
        int j_min = i;
        for (int j = i + 1; j <= r; j++)
        {
            if (arr[j] < arr[j_min])
                j_min = j;
        }
        if (j_min != i)
            swap(arr[i], arr[j_min]);
    }
}

插入排序

选择未排序部分最左侧一个数，将已排序部分所有比它大的数右移一位，再将该数插入对应位置。从头到尾循环操作即可完成排序。

void insertion_sort(int arr[], int l, int r)
{
    for (int i = l + 1; i <= r; i++)
    {
        int num = arr[i];
        int j = i - 1;
        while (j >= l && num < arr[j])
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = num;
    }
}

归并排序

  1. 确定分界点。取区间中点为分界点：$arr[(l+r)/2]$.
  2. 递归处理。对左右两段分别递归进行处理。

  3. 归并操作。将左右两段合并。

    指针 $i,j$ 分别指向两段的左侧，每次将指针 $i,j$ 指向的较小的那个数接在合并数组后，对应指针右移即可。

const int MAXN = 100;
int tmp[MAXN];
void merge_sort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];
    for (int m = l, n = 0; m <= r; m++, n++)
        arr[m] = tmp[n];
}

快速排序

  1. 确定分界值。可随意选择，如 $arr[l]$，$arr[r]$，$arr[(l+r)/2]$ 均可。下面将分界值记为 $x$.

  2. 调整范围。调整数组，使其满足所有 $\leq x$ 的数在数组左段，所有 $\geq x$ 的数在数组右段。

    $i$ 指针在区间左端，$j$ 指针在区间右端。$i$ 指针右移直到找到 $\geq x$ 的数停止，$j$ 指针左移直到找到 $\leq x$ 的数停止，交换两指针指向的数，然后继续进行操作。直到两指针相遇，则数组调整完成。

  3. 递归处理。对左右两段分别递归进行处理。
void quicksort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int x = arr[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {
        do
            i++;
        while (arr[i] < x);
        do
            j--;
        while (arr[j] > x);
        if (i < j)
            swap(arr[i], arr[j]);
    }
    quicksort(arr, l, j);
    quicksort(arr, j + 1, r);
}

注意：递归边界需要避免出现无限循环的情况。如 $x$ 取 $arr[l]$ 时，递归边界不可取为 $(l, i-1)$、$(i, r)$. 另外，分界点取两端有可能被测试样例卡掉，可取中间点或随机点。