注：所有算法的排序原理动图请前往VisualGo观看或前往视频 1|视频 2学习原理

算法复杂度与稳定性

  • 稳定性复杂度口诀

    1、插帽龟(插入、冒泡、归并)，它很稳(稳定性)，此外还有基你太稳(基数排序)
    2、插帽龟喜欢选帽插(选择、冒泡、插入)，插完就方了(平均时间复杂度 $O(n^2)$)
    3、快归队(快速、归并、堆)，$n$ 老二(平均时间复杂度 $O(n\log_2 n)$)

  • 稳定性复杂度表格(基数排序中 r 为关键字基数，d 为长度，n 为关键字个数)

    排序 平均 T(n) 所需 S(n) 稳定性
    插入排序 $O(n^2)$ $O(1)$ 稳定
    希尔排序 $O(n^{\frac{2}{3}})$ $O(1)$ 不稳定
    选择排序 $O(n^2)$ $O(1)$ 不稳定
    堆排序 $O(n\log_2 n)$ $O(1)$ 不稳定
    冒泡排序 $O(n^2)$ $O(1)$ 稳定
    快速排序 $O(n\log_2 n)$ $O(n\log_2 n)$ 不稳定
    归并排序 $O(n\log_2 n)$ $O(1)$ 稳定
    基数排序 $O(d(n+r))$ $O(rd + n)$ 稳定

冒泡排序

原理与实现

  • 冒泡排序原理

    1、冒泡排序英文名为Bubble Sort，是一种最基础的交换排序
    2、排序过程简述为，每轮比较过程中比较相邻的两个数，按照规则交换，每轮结束都能将该轮该数依次罗列在末尾

  • 冒泡排序实现

    #include <stdio.h>

// 采用两层循环实现的方法
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void bubblesort1(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int temp;

    // 从末元素开始，到首元素+1，限制 j 的比对范围，共 n-1 轮对比
    // 每轮结束后，当前 i 的位置便是排序好的
    for (int i = n - 1; i > 0; i--)
    {
        // 每次只需比较 0-i 之间的元素，i 之后的元素是排序好的
        for (int j = 0; j < i; j++)
        {
            // 升序，如果当前比后一个数大，则交换
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 采用递归的方法实现
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void bubblesort2(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int temp;

    // 相当于上面函数的内层循环，外层循环通过递归实现
    for (int i = 0; i < n - 1; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }

    bubblesort2(arr, n - 1); // 递归实现外层循环
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    bubblesort1(arr, 15);
    bubblesort2(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

排序优化

  • 冒泡排序优化方案

    1、如果序列已经是有序的，可以优化冒泡排序的方法
    2、具体做法是每趟排序时判断是否交换过元素，如果没有交换，则证明数列已经有序，可以提前退出排序

  • 优化后代码

    #include <stdbool.h>
#include <stdio.h>

// 采用两层循环实现的方法
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void bubblesort(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int temp;
    bool ifswap; // 每趟过程中是否有交换

    // 从末元素开始，到首元素+1，限制 j 的比对范围，共 n-1 轮对比
    // 每轮结束后，当前 i 的位置便是排序好的
    for (int i = n - 1; i > 0; i--)
    {
        // 初始化交换标志为未交换
        ifswap = false;

        // 每次只需比较 0-i 之间的元素，i 之后的元素是排序好的
        for (int j = 0; j < i; j++)
        {
            // 升序，如果当前比后一个数大，则交换
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                ifswap = true; // 设定为有交换
            }
        }

        // 没有交换提前退出
        if (ifswap == false)
            return;
    }
}

int main(void)
{
    int arr[15] = {2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 48, 50, 47, 46, 44};

    // 在 38 后的部分排序完后，再经过一轮改变 ifswap 后就会直接结束排序
    bubblesort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

选择排序

原理与实现

  • 选择排序原理

    1、选择排序英文名为Selection Sort，其原理十分简单清晰
    2、从头到尾扫描序列，找出最大或最小的元素，与第一个元素交换，然后再从剩下的序列中继续这种选择交换

  • 选择排序实现

    #include <stdio.h>

// 采用两层循环实现的方法
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void selectsort1(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int temp, iminpos; // 最小值的下标

    // 共进行 n-1 轮比较
    for (int i = 0; i < n - 1; i++)
    {
        iminpos = i; // 默认当前位置最小

        // i+1 到 n 是这次需要对比的剩余序列
        for (int j = i + 1; j < n; j++)
        {
            // 升序，如果更小，则记录当前位置
            if (arr[j] < arr[iminpos])
                iminpos = j;
        }

        // 如果最小位置有变动，则交换它们的元素
        if (iminpos != i)
        {
            temp = arr[i];
            arr[i] = arr[iminpos];
            arr[iminpos] = temp;
        }
    }
}

// 采用递归实现的方法
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void selectsort2(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int temp, iminpos = 0; // 每趟循环最小值的下标

    for (int i = 1; i < n; i++)
    {
        // 找出更小的元素，记录它的位置
        if (arr[i] < arr[iminpos])
            iminpos = i;
    }

    // 如果本趟循环的最小元素不是起始元素，则交换它们的位置
    if (iminpos != 0)
    {
        temp = arr[0];
        arr[0] = arr[iminpos];
        arr[iminpos] = temp;
    }

    selectsort2(arr + 1, --n); // 递归，起始位置 +1，元素个数 -1
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    selectsort1(arr, 15);
    selectsort2(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

排序优化

  • 选择排序优化方案

    1、选择排序一趟排序只选择最大或最小值，优化的办法是一趟同时把最大和最小值选出来
    2、排序过程中，最小的放左边，最大的放右边。这样优化可以循环趟数减半

  • 优化后代码

    #include <stdio.h>

// 采用两层循环实现的方法
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void selectsort1(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int ileft = 0, iright = n - 1; // 每趟排序最左和最右的位置，最左从 0 开始，最右到 n-1 结束
    int temp, iminpos, imaxpos;    // 最小值和最大值的下标

    // 只要最左仍在最右的左边
    while (ileft < iright)
    {
        iminpos = imaxpos = ileft; // 初始化最小值和最大值的下标为最左

        // 每趟循环从最左和最右范围中选取元素
        for (int i = ileft; i <= iright; i++)
        {
            if (arr[i] < arr[iminpos])
                iminpos = i;
            if (arr[i] > arr[imaxpos])
                imaxpos = i;
        }

        // 如果本趟循环最小的元素不是最左边的元素，则交换位置
        if (iminpos != ileft)
        {
            temp = arr[ileft];
            arr[ileft] = arr[iminpos];
            arr[iminpos] = temp;
        }

        // 如果 imaxpos 的位置是 ileft，在上面代码中，ileft 已被交换到了 iminpos 的位置
        // 所以 imaxpos 的值要修改成 iminpos
        if (imaxpos == ileft)
            imaxpos = iminpos;

        // 如果本趟循环最大的元素不是最右边的元素，则交换位置
        if (imaxpos != iright)
        {
            temp = arr[iright];
            arr[iright] = arr[imaxpos];
            arr[imaxpos] = temp;
        }

        // 更改范围
        ileft++;
        iright--;
    }
}

// 采用递归实现的方法
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void selectsort2(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int ileft = 0, iright = n - 1; // 每趟排序最左和最右的位置，最左从 0 开始，最右到 n-1 结束
    int temp, iminpos = 0, imaxpos = 0; // 每趟循环最小值和最大值的下标

    // 每趟循环从最左和最右范围中选取元素
    for (int i = ileft; i <= iright; i++)
    {
        if (arr[i] < arr[iminpos])
            iminpos = i;
        if (arr[i] > arr[imaxpos])
            imaxpos = i;
    }

    // 如果本趟循环最小的元素不是最左边的元素，则交换位置
    if (iminpos != ileft)
    {
        temp = arr[ileft];
        arr[ileft] = arr[iminpos];
        arr[iminpos] = temp;
    }

    // 如果 imaxpos 的位置是 ileft，在上面代码中，ileft 已被交换到了 iminpos 的位置
    // 所以 imaxpos 的值要修改成 iminpos
    if (imaxpos == ileft)
        imaxpos = iminpos;

    // 如果本趟循环最大的元素不是最右边的元素，则交换位置
    if (imaxpos != iright)
    {
        temp = arr[iright];
        arr[iright] = arr[imaxpos];
        arr[imaxpos] = temp;
    }

    selectsort2(arr + 1, n - 2); // 递归，起始位置 +1，元素个数 -2
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    selectsort1(arr, 15);
    selectsort2(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

插入排序

原理与实现

  • 插入排序原理

    1、插入排序英文名为Insertion sort
    2、插入排序原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

  • 插入排序实现

    #include <stdio.h>

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void insertsort(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int i, j;
    int temp; // 当前需要排序的元素的值

    // 从第二个数开始，到最后一个数
    for (i = 1; i < n; i++)
    {
        temp = arr[i]; // 待排序元素

        // 从已排序的序列最右边开始，把大于当前元素的元素后移，同时寻找需要插入的位置
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] > temp)
                arr[j + 1] = arr[j]; // 逐个元素后移
            else                     // arr[j] <= temp
                break;               // 找到了需要插入的位置，j+1 便是被排序元素的位置
        }

        // 插入当前排序的元素
        arr[j + 1] = temp;
    }
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    insertsort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

排序优化

  • 插入排序的不足

    1、寻找插入位置
    2、移动元素

  • 插入排序优化方案

    1、对已排序的序列，采用二分查找方法
    2、携带多个元素
    3、数据链表化
    4、希尔排序

希尔排序

原理与实现

  • 希尔排序原理

    1、希尔排序英文名为Shell’s Sort，是插入排序的一种，是针对插入排序的改进
    2、希尔排序基本思想：把待排序的数列分为多个组，然后再对每个组进行插入排序。先让数列整体大致有序，然后多次调整分组方式，使数列更加有序。最后再使用一次插入排序，整个数列将全部有序
    3、每次分组都每间隔 $x-1$ 个一组($x$ 为上轮分得的组数除以 $2$，表示这轮分出的组数)，注意分组是间隔分组而不是相邻分组。分组并排序后，每组中较大的数都放到每组的靠右的位置，整体上较大的数就更偏右侧
    4、希尔排序的核心思想是化远为近，查找次数和移动次数都有所减少，在数据量较大时差距十分明显

  • 希尔排序实现

    #include <stdio.h>

// 希尔排序中的单组排序
// arr 是待排序的数组，n 是数组总长度，ipos 是分组的起始位置， istep 是分组的步长(增量)
void groupsort(int arr[], int n, int ipos, int istep)
{
    // 插入排序稍作更改
    int i, j, temp; // 当前需要排序的元素的值

    // 从当前组第二个元素开始，到末尾结束，每次移动步长
    for (i = ipos + istep; i < n; i += istep)
    {
        temp = arr[i]; // 待排序元素

        // 从已排序的最右边开始，把大于当前排序的元素后移
        for (j = i - istep; j >= 0; j -= istep)
        {
            if (arr[j] > temp)
                arr[j + istep] = arr[j];
            else
                break;
        }

        arr[j + istep] = temp;
    }
}

// 希尔排序
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void shellsort(int arr[], unsigned int n)
{
    // istep 为步长，每次减为原来的一半取整，最后一次必定为 1
    for (int istep = n / 2; istep > 0; istep /= 2)
    {
        // 共 istep 个组，对每一组都执行插入排序
        for (int i = 0; i < istep; i++)
        {
            groupsort(arr, n, i, istep);
        }
    }
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    shellsort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

快速排序

原理与实现

  • 快速排序原理

    1、快速排序英文名为Quick sort
    2、快速排序基本思想：先从数列中取出一个元素作为基准数，扫描数列，将比基准数小的放在左边，大的放在右边，得到两个区间。再对左右区间重复此操作，直到各区间少于两个元素
    3、整体思路为挖坑填数+分治，取出一个基准数后(如第一个数为基准数)，该位置便留下一个坑。左右各放置一个指针，首先右指针从右查找比基准数小的，找到后填到前面的坑中，此位置留出一个坑，再左指针从左查找比基准数大的，填到右边的坑中，以此类推。当左右两指针重合，都指向同一个坑时，把基准数填入。然后把左右指针调整为左区间的范围，向下递归，直到左区间都排序完成，递归回来处理右区间

  • 快速排序实现

    #include <stdio.h>

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void quicksort(int arr[], unsigned int n)
{
    if (n < 2)
        return;

    int temp = arr[0];             // 选取最左边的数作为中心轴(基准数)
    int ileft = 0, iright = n - 1; // 左右下标
    int imoving = 2;               // 当前应该移动的下标，1为左下标,2为右下标

    while (ileft < iright)
    {
        // 如果移动右下标
        if (imoving == 2)
        {
            // 如果当前位置的值 >= 基准数，继续移动右下标
            if (arr[iright] >= temp)
            {
                iright--;
                continue;
            }
            // 如果小于基准数，则填到左下标的坑中
            arr[ileft] = arr[iright];
            ileft++;     // 左下标向右移动
            imoving = 1; // 下次该移动左下标
            continue;
        }

        // 如果移动左下标
        if (imoving == 1)
        {
            // 如果当前位置的值 <= 基准数，继续移动左下标
            if (arr[ileft] <= temp)
            {
                ileft++;
                continue;
            }
            // 如果大于基准数，则填到右下标的坑中
            arr[iright] = arr[ileft];
            iright--;    // 右下标向左移动
            imoving = 2; // 下次该移动右下标
            continue;
        }
    }

    // 循环结束，左右下标重合，把基准值填入
    arr[ileft] = temp;

    // 此时左右序列已经出现，递归进行下轮排序
    quicksort(arr, ileft);                     // 左序列
    quicksort(arr + ileft + 1, n - ileft - 1); // 右序列
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    quicksort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

排序优化

  • 快速排序优化方案

    1、采用更合理的中心轴(基准数)，减少递归深度。从数列中选取多个数，取中间数
    2、结合插入排序，区间在 $10$ 个元素内用插入排序效率更高

  • 优化后代码

    #include <stdio.h>

// 插入排序
void insertsort(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int i, j;
    int temp; // 当前需要排序的元素的值

    // 从第二个数开始，到最后一个数
    for (i = 1; i < n; i++)
    {
        temp = arr[i]; // 待排序元素

        // 从已排序的序列最右边开始，把大于当前元素的元素后移，同时寻找需要插入的位置
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] > temp)
                arr[j + 1] = arr[j]; // 逐个元素后移
            else                     // arr[j] <= temp
                break;               // 找到了需要插入的位置，j+1 便是被排序元素的位置
        }

        // 插入当前排序的元素
        arr[j + 1] = temp;
    }
}

// 快速排序
// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void quicksort(int arr[], unsigned int n)
{
    if (n < 2)
        return;

    int temp = arr[0];             // 选取最左边的数作为中心轴(基准数)
    int ileft = 0, iright = n - 1; // 左右下标
    int imoving = 2;               // 当前应该移动的下标，1为左下标,2为右下标

    while (ileft < iright)
    {
        // 如果移动右下标
        if (imoving == 2)
        {
            // 如果当前位置的值 >= 基准数，继续移动右下标
            if (arr[iright] >= temp)
            {
                iright--;
                continue;
            }
            // 如果小于基准数，则填到左下标的坑中
            arr[ileft] = arr[iright];
            ileft++;     // 左下标向右移动
            imoving = 1; // 下次该移动左下标
            continue;
        }

        // 如果移动左下标
        if (imoving == 1)
        {
            // 如果当前位置的值 <= 基准数，继续移动左下标
            if (arr[ileft] <= temp)
            {
                ileft++;
                continue;
            }
            // 如果大于基准数，则填到右下标的坑中
            arr[iright] = arr[ileft];
            iright--;    // 右下标向左移动
            imoving = 2; // 下次该移动右下标
            continue;
        }
    }

    // 循环结束，左右下标重合，把基准值填入
    arr[ileft] = temp;

    // 此时左右序列已经出现，进行下轮排序
    // 左序列
    if (ileft > 10)
        quicksort(arr, ileft); // 元素大于 10 个，用快速排序递归
    else
        insertsort(arr, ileft); // 否则用插入排序更快
    // 右序列
    if (n - ileft - 1 > 10)
        quicksort(arr + ileft + 1, n - ileft - 1);
    else
        insertsort(arr + ileft + 1, n - ileft - 1);
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    quicksort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

归并排序

原理与实现

  • 归并排序原理

    1、归并排序英文名为Merge Sort，又名合并排序
    2、归并排序基本思想：将已经有序的子数列合并，得到另一个有序的数列
    3、整体思路为，对于两个已经有序的数列，分别用一个指针指向首元素，比较所指的两个元素的大小，将较小的落下排入新序列，再将落下元素的序列的指针后移，继续比较，如果指针已经指向空白，则将另一个序列剩余元素落下。对于一个完全无序的数列，看做许多个只有 $1$ 个元素的有序数列，一对一对比较，得到许多个有 $2$ 个元素的有序数列，以此类推

  • 归并排序实现(递归，实现较简单)

    #include <stdio.h>
#include <string.h>

// arr 是待排序的数组首元素地址，arrtmp 是用于排序的临时数组的首地址
// start 是排序区间第一个元素位置，end 是排序区间最后一个元素位置
void _mergesort(int arr[], int arrtmp[], int start, int end)
{
    // 如果 start == end，表示该区间元素数量只有 1 个，递归终止，而 start > end 则不合理
    // 注意 mergesort() 调用本函数时，参数 end 传入的是 n-1(末元素下标)
    if (start >= end)
        return;

    // 将无序数列对半拆分，递归下去，形成许多只有一个或两个元素的有序数列
    int mid = start + (end - start) / 2; // 计算排序区间中间的位置
    int istart1 = start, iend1 = mid;    // 区间左边元素的首和尾元素的位置
    int istart2 = mid + 1, iend2 = end;  // 区间右边元素的首和尾元素的位置

    _mergesort(arr, arrtmp, istart1, iend1); // 对区间左边元素递归排序
    _mergesort(arr, arrtmp, istart2, iend2); // 对区间右边元素递归排序

    // 递去部分结束后，归来过程中整理这些有序序列，排序并合并

    int i = start; // 已排序数组 arrtmp 的计数器

    // 把区间左右两边的数列合并到已排序的数组 arrtmp 中
    while (istart1 <= iend1 && istart2 <= iend2)
        arrtmp[i++] = arr[istart1] < arr[istart2] ? arr[istart1++] : arr[istart2++]; // 选择更大的数排入序列

    // 把左边数列其他元素追加到已排序数组，如果没有剩余，则循环条件不成立不会执行
    while (istart1 <= iend1)
        arrtmp[i++] = arr[istart1++];
    // 把右边数列其他元素追加到已排序数组，如果没有剩余，则循环条件不成立不会执行
    while (istart2 <= iend2)
        arrtmp[i++] = arr[istart2++];

    // 把已排序数组 arrtmp 的元素复制到 arr 中
    // memcpy(要拷贝到的目标内存地址, 要拷贝的源内存地址, 要拷贝的字节数)
    memcpy(arr + start, arrtmp + start, (end - start + 1) * sizeof(int));
}

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void mergesort(int arr[], unsigned int n)
{
    if (n < 2)
        return;

    int arrtmp[n]; // 分配一个与待排序数组相同大小的数组，用于排序数据的临时存放

    _mergesort(arr, arrtmp, 0, n - 1); // 调用递归函数进行排序
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    mergesort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

  • 归并排序实现(循环)

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int x, int y) // 返回较小数
{
    return x < y ? x : y;
}

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void mergesort(int arr[], unsigned int n)
{
    if (n < 2)
        return;

    int *a = arr;                            // a 指向待排序的数组
    int *b = (int *)malloc(n * sizeof(int)); // b 指向已排序的数组
    int iseg;                                // 区间分段的计数器，1,2,4,8,16...
    int istart;                              // 区间起始位置的计数器

    // 排序的趟数的循环，iseg = 1,2,4,8,16...，*2 后表示每个区间的元素个数
    for (iseg = 1; iseg < n; iseg *= 2)
    {
        // 每趟排序选取区间的循环，如第一趟 istart = 0,2,4,6,8,...，表示每个区间的首元素
        for (istart = 0; istart < n; istart += iseg * 2)
        {
            // 把每个区间分成两部分，ilow 是起始位置， imid 是中间位置， imax 是结束位置
            int ilow = istart;
            int imid = min(istart + iseg, n);     // 考虑分段不均的情况，imid 不能超出 n
            int imax = min(istart + iseg * 2, n); // 考虑分段不均的情况，imax 不能超出 n

            int i = ilow;                     // 已排序数组的计数器
            int istart1 = ilow, iend1 = imid; // 待排序左边数列的首尾位置
            int istart2 = imid, iend2 = imax; // 待排序右边数列的首尾位置

            // 把待排序左右两边数列合并到已排序数列
            while ((istart1 < iend1) && (istart2 < iend2))
                b[i++] = a[istart1] < a[istart2] ? a[istart1++] : a[istart2++];

            // 把左边数列其他元素追加到已排序数组，如果没有剩余，则循环条件不成立不会执行
            while (istart1 < iend1)
                b[i++] = a[istart1++];
            // 把右边数列其他元素追加到已排序数组，如果没有剩余，则循环条件不成立不会执行
            while (istart2 < iend2)
                b[i++] = a[istart2++];
        }

        // 交换两个数组的指针，准备下一趟的排序
        int *ptmp = a;
        a = b;
        b = ptmp;
    }

    // 如果 a 指向的不是原始数组的指针(有可能 a 指向 b，排序好的数组仍在 b 中，而 arr 并没有被更新)，把 a 的内容复制到 arr 中
    if (a != arr)
    {
        memcpy(arr, a, n * sizeof(int));
        b = a;
    }

    free(b); // 释放 malloc() 分配给 b 的内存
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    mergesort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

堆排序

原理与实现

  • 堆排序原理

    1、堆排序英文名为Heap Sort，是利用堆这种数据结构而设计的一种排序算法(通过二叉查找树的思想大大减少了比对次数)
    2、堆排序的特点：堆必须是完全二叉树。二叉树每个节点的值都大于等于其左右子树节点的值，称为大顶堆；或者每个节点的值都小于等于其左右子树节点的值，称为小顶堆。一个完全二叉树的节点与数组下标的关系如下图所示
    3、整体思路为先把数组用完全二叉树表示出来，从最后一个父节点开始，和两个子节点比较选择最大的作为父节点，以此类推，向上形成大顶堆。一轮结束后，将根节点与最后一个叶节点(即数组最后一个元素位置)交换，交换后的叶节点(原先的根节点)便是排序后序列的最大值。此时，交换后的根节点(原先的叶节点)通过Heapify(数组堆化/元素下沉)的方法，先比较出两个子节点中较大的节点(如果两个子节点相同，则左侧节点看作较大)，如果父节点比较大的节点小，则交换两个节点，层层向下直到无法交换，此时便再次构建出了大顶堆。再次将根节点和未排序的最后一个叶节点(即数组倒数第二个元素位置)交换，成为排序后序列的第二大值(执行完上述两轮操作后的二叉树如下图)。以此类推，最后数组的元素将会升序排列

  • 堆排序实现

    #include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 采用循环实现 heapify
// arr 为待排序数组地址，start 为待 heapify 节点的下标，end 为待排序数组末元素下标
void heapify(int arr[], int start, int end)
{
    // 确定父节点和左子节点的数组下标
    int dad = start;
    int son = dad * 2 + 1;

    // 如果子节点的下标没有超出范围，循环继续
    while (son <= end)
    {
        // 先比较两个子节点的大小，选择最大的
        if ((son + 1 <= end) && (arr[son] < arr[son + 1]))
            son++;
        // 如果父节点大于子节点,调整完毕，直接退出函数
        if (arr[dad] > arr[son])
            return;
        // 否则交换父子内容，再继续子节点和孙节点比较
        swap(&arr[dad], &arr[son]);
        dad = son;
        son = dad * 2 + 1;
    }
}

// 采用递归实现 heapify
// arr 为待排序数组地址，start 为待 heapify 节点的下标，end 为待排序数组末元素下标
void heapify1(int arr[], int start, int end)
{
    // 确定父节点和左子节点的数组下标
    int dad = start;
    int son = dad * 2 + 1;

    // 如果子节点下标没有超出范围，则继续
    if (son > end)
        return;
    // 先比较两个子节点的大小，选择最大的
    if ((son + 1 <= end) && (arr[son] < arr[son + 1]))
        son++;
    // 如果父节点大于子节点,调整完毕，直接退出函数
    if (arr[dad] > arr[son])
        return;
    // 否则交换父子内容，再继续子节点和孙节点比较
    swap(&arr[dad], &arr[son]);
    heapify1(arr, son, end);
}

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void heapsort(int arr[], unsigned int n)
{
    // 初始化堆，从最后一个父节点开始调整，父节点 = (末下标-1)/2
    for (int i = (n - 2) / 2; i >= 0; i--)
        heapify(arr, i, n - 1);

    // 把第一个元素和堆最后一个元素交换，然后重新调整，直到排序完毕
    for (int i = n - 1; i > 0; i--)
    {
        swap(&arr[0], &arr[i]);
        heapify(arr, 0, i - 1);
    }
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    heapsort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

计数排序

原理与实现

  • 计数排序原理

    1、计数排序英文名为Counting Sort，只适用于数据范围较小、已知数据最大最小值且数据重复率高的情况
    2、基本思路是通过另外一个数组，对序列中的元素出现的次数计数，然后按照存储的次数按顺序依次将对应个数的对应元素放回序列中

  • 计数排序实现

    #include <stdio.h>
#include <string.h>

int arrmax(int arr[], int n)
{
    int max = arr[0];
    for (int i = 1; i < n; i++)
        max = arr[i] > max ? arr[i] : max;
    return max;
}

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void countsort(int arr[], unsigned int n)
{
    if (n < 2)
        return;

    int imax = arrmax(arr, n);         // 获取待排序数组的最大元素的值
    int arrtmp[imax + 1];              // 临时数组的大小为 imax+1
    memset(arrtmp, 0, sizeof(arrtmp)); // 初始化临时数组

    int i, j, k;

    // 计数
    for (i = 0; i < n; i++)
        arrtmp[arr[i]]++;

    // 把临时数组计数的内容填充到 arr 中
    i = 0;
    for (j = 0; j <= imax; j++)
        for (k = 0; k < arrtmp[j]; k++)
            arr[i++] = j;
}

int main(void)
{
    int arr[20] = {2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2};

    countsort(arr, 20);

    // 输出
    for (int i = 0; i < 20; i++)
        printf("%d ", arr[i]);
    return 0;
}

桶排序

原理与实现

  • 桶排序原理

    1、桶排序英文名为Bucket Sort，桶排序不仅是一种排序算法，更是一种桶的思想
    2、实现原理：假设输入数据服从均匀分布，将数据分到有限量的桶里(每个桶划定一个范围)，然后对每个桶分别排序，再将桶的数据合并
    3、桶排序的时间复杂度，取决于各个桶的数据排序的时间复杂度，因为其他部分的时间复杂度都为 $O(n)$ 。很显然，桶划分的越小，则各个桶的数据量越少，排序所用时间就会越少，但相应的空间消耗会增大，合理分配能够较为均匀的用空间换时间

  • 桶排序实现

    #include <stdio.h>
#include <string.h>

void bubblesort1(int arr[], unsigned int n)
{
    if (n < 2) // 参数小于2不需要排序
        return;

    int temp;

    // 从末元素开始，到首元素+1，限制 j 的比对范围，共 n-1 轮对比
    // 每轮结束后，当前 i 的位置便是排序好的
    for (int i = n - 1; i > 0; i--)
    {
        // 每次只需比较 0-i 之间的元素，i 之后的元素是排序好的
        for (int j = 0; j < i; j++)
        {
            // 升序，如果当前比后一个数大，则交换
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void bucketsort(int arr[], unsigned int n)
{
    int bucket[5][5];  // 分配 5 个桶
    int bucketsize[5]; // 每个桶中元素个数的计数器

    // 初始化桶和桶计数器
    memset(bucket, 0, sizeof(bucket));
    memset(bucketsize, 0, sizeof(bucketsize));

    // 把数组 arr 的数据放入桶中
    for (int i = 0; i < n; i++)
        // 每个桶范围为 10 个数，[arr[i] / 10]表示要存入哪个桶，第二维表示对应桶的第几个元素，且运行后自增指向下一个空白
        bucket[arr[i] / 10][bucketsize[arr[i] / 10]++] = arr[i];

    // 对每个桶进行排序，使用的排序算法可以自行选择
    for (int i = 0; i < 5; i++)
        bubblesort1(bucket[i], bucketsize[i]);

    // 把每个桶的数据填充到 arr 中
    int k = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < bucketsize[i]; j++)
            arr[k++] = bucket[i][j];
}

int main(void)
{
    int arr[15] = {44, 3, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 49, 48};

    bucketsort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

关于桶思想

  • 误区

    1、如果数据分布不均，大量数据集中在少数桶中，桶排序就没效果了。反驳：实际应用场景的前提就是在数据均匀分布的情况下，应按照场景选择算法
    2、桶排序要时间就省不了空间，要空间就省不了时间，所以桶排序意义不大。反驳：桶排序可以通过调配每个桶的范围大小，来实现时间和空间的相互转换，可以自由地调配比例，且可以达到时间和空间的较完美平衡

  • 桶思想

    1、在现实世界中，大部分数据是均匀分布的，或者设计时可以让它均匀分布，又或者可以转换为均匀分布
    2、数据均匀分布了，桶排序的优势便可以发挥出来。理解桶思想可以设计出很高效的算法(分库分表)，也体现了分治的思想

基数排序

原理与实现

  • 基数排序原理

    1、基数排序英文名为Radix Sort，是桶排序的拓展
    2、基数排序基本思想：将整数按位数切割成不同的数字，然后每个数位分别比较，位数不足的前面补零
    3、整体思路为，先分配十个桶，分别表示 $0 \to 9$，首先按照个位数字分类进桶，再按照桶号 $0 \to 9$ 依次拿出放回序列(一个桶中有多个数据，则按照先进先出的原则拿出)，此时只看个位是一个有序数列。第二轮按照十位数字分类进桶(没有十位则十位看作 $0$)，再依次出桶放回序列，此时只看后两位是一个有序数列。以此类推，直到排序完最高数位，则整个序列有序
    4、实际代码实现并没有在桶内反复存入拿出，具体实现请根据代码细节理解，其中较难理解部分有以下辅助图示

  • 基数排序实现

    #include <stdio.h>
#include <string.h>

int arrmax(int arr[], int n)
{
    int max = arr[0];
    for (int i = 1; i < n; i++)
        max = arr[i] > max ? arr[i] : max;
    return max;
}

void _radixsort(int arr[], unsigned int n, unsigned int exp)
{
    int i;
    int buckets[10] = {0}; // 初始化 10 个桶
    int result[n];         // 存放从桶中收集的数据的临时数组

    // 遍历 arr，将数据出现的次数存储在 buckets 中
    for (i = 0; i < n; i++)
        buckets[(arr[i] / exp) % 10]++;

    // 调整 buckets 中各元素的值，调整后的值就是 arr 中元素在 result 中的位置(下标额外多了 1)
    for (i = 1; i < 10; i++)
        buckets[i] = buckets[i] + buckets[i - 1];

    // 将 arr 中元素填充到 result 中
    for (i = n - 1; i >= 0; i--)
    {
        int iexp = (arr[i] / exp) % 10;
        result[buckets[iexp] - 1] = arr[i];
        buckets[iexp]--;
    }

    // 将排序好的数组 result 复制到数组 arr 中
    memcpy(arr, result, n * sizeof(int));
}

// 参数 arr 是待排序的数组首元素地址，n 是数组元素个数
void radixsort(int arr[], unsigned int n)
{
    int imax = arrmax(arr, n); // 获取数组中的最大值

    // 从个位开始，对数组 arr 按指数位进行排序，iexp 为排序指数：1, 10, 100
    for (int iexp = 1; imax / iexp > 0; iexp *= 10)
        _radixsort(arr, n, iexp);
}

int main(void)
{
    int arr[15] = {144, 203, 738, 905, 347, 215, 836, 26, 527, 602, 946, 504, 219, 750, 848};

    radixsort(arr, 15);

    // 输出
    for (int i = 0; i < 15; i++)
        printf("%d ", arr[i]);
    return 0;
}

基数排序的应用

  • 其他应用

    1、由于整数也可以表示字符串和特定格式浮点数，所以基数排序也适用于其他数据类型
    2、基数排序也可以理解为按关键字排序，比如待排序数列最大三位数，关键字分别为个位、十位、百位。此外桶的个数可以灵活调整，比如按月份排序可以分配 $12$ 个桶，按日期排序可以分配 $31$ 个桶

STL 的排序技巧

  • 模板-排序去重

    /* 去重 - vector */
vector<int> vec = {1, 13, 2, 5, 10000, 2, 13}; // 使用 vector 保存原始数据
sort(vec.begin(), vec.end());                  // 使用 sort 排序
// unique 函数返回一个迭代器，指向不重复序列的尾后位置(即被排到末尾的重复元素的首元素位置)
// erase 从重复元素首元素，删除到末尾，删除掉所有重复元素
vec.erase(unique(vec.begin(), vec.end()), vec.end());

/* 去重 - 数组 */
int n = 7;                                     // 实际数组长度
int arr[100001] = {1, 13, 2, 5, 10000, 2, 13}; // 使用数组保存原始数据
sort(arr, arr + n);                            // 使用 sort 排序
// 使用 unique 返回的位置，减去首元素位置，得到不重复数列的长度
// 后面程序使用数组，只需要使用 arr[0] 到 arr[len] 即可，后面部分是重复元素，无法删除但使用时可以忽略
int len = unique(arr, arr + n) - arr;

  • 模板-结构体按照指定优先级排序

    /* 要求将 Book 按照成员 a-b-c 的优先级排序 */
struct Book
{
    int a, b, c;

    // 方法 1：重载该结构的 < 运算符
    bool operator<(const Book &rhs)
    {
        // 比较函数的写法，通常将更高优先级的比较写在最下，依次向上使用 if 限制比较
        // 左值 lhs < 右值 rhs 表示升序
        if (a == rhs.a && b == rhs.b)
            return c < rhs.c;
        if (a == rhs.a)
            return b < rhs.b;
        return a < rhs.a;
    }
} p[100];

// 方法 2：单独写一个比较函数，传给 sort 做参数
bool compare(Book &lhs, Book &rhs)
{
    // 比较函数的写法，通常将更高优先级的比较写在最下，依次向上使用 if 限制比较
    // 左值 lhs < 右值 rhs 表示升序
    if (lhs.a == rhs.a && lhs.b == rhs.b)
        return lhs.c < rhs.c;
    if (lhs.a == rhs.a)
        return lhs.b < rhs.b;
    return lhs.a < rhs.a;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i].a >> p[i].b >> p[i].c;

    // 使用方法 1 时可以直接这样用 sort
    sort(p, p + n);
    // 使用方法 2 时需要将自定义的比较函数传给 sort
    sort(p, p + n, compare);
    // 方法 3：直接使用 lambda 表达式给 sort 做参数
    sort(p, p + n, [](Book &lhs, Book &rhs) -> bool {
        if (lhs.a == rhs.a && lhs.b == rhs.b)
            return lhs.c < rhs.c;
        if (lhs.a == rhs.a)
            return lhs.b < rhs.b;
        return lhs.a < rhs.a;
    });
    return 0;
}

  • 优先队列(堆)的使用

    // priority_queue 默认为大根堆，其堆顶始终保持最大值(内部自动维护)
// 如下为 priority_queue<int> 的默认值，通过 vector<int> 实现，通过 less<int> 维护
priority_queue<int, vector<int>, less<int>> pq;
pq.push(12);        // 通过 push 压入堆内
int x = pq.top();   // 通过 top 获取堆顶元素
pq.pop();           // 通过 pop 弹出堆顶元素

// 更改优先队列的优先规则的方式，如下通过 greater 维护(仅适用于内置类型)，该堆为小根堆
priority_queue<int, vector<int>, greater<int>> pq;

// 如果类型为自定义的结构，需要自定义比较函数，或者重载结构的 < 运算符
bool compare(Book &lhs, Book &rhs)
{
    return lhs.price > rhs.price;
}
priority_queue<Book, vector<Book>, compare> pq;

页底评论