这里总结如下算法:

  • 基于比较的排序算法:
    冒泡排序
    选择排序
    插入排序
    归并排序
    快速排序
  • 不基于比较的排序算法:
    计数排序
    基数排序

# 写在前面

这次的算法实现全都使用 C 语言,并不是说 C 有多好,只是因为 C 比较接近底层,掌握 C 的写法后,其他语言的写法也很好实现,其次,也是因为现在很多算法的讲解也使用 C。

然后,本文的算法实现可能还不够完美,虽然都经过了测试用例,但难免还有些疏忽,如有错误或是有更好的意见,欢迎提出。

# 基于比较的排序算法 - O (N^2)

# 冒泡排序

# 核心原理

从左到右,依次将较大的元素交换到后面,那么一次一次排序后,最大的元素就在数组末尾,然后不断重复。

给定一个 N 个元素的数组,冒泡法排序将:

  1. 如果元素大小关系不正确,交换这两个数(在本例中为 a> b)
  2. 比较一对相邻元素(a,b)
  3. 重复步骤 1 和 2,直到我们到达数组的末尾(最后一对是第(N-2)和(N-1)项,因为我们的数组从零开始)
  4. 到目前为止,最大的元素将在最后的位置。 然后我们将 N 减少 1,并重复步骤 1,直到 N = 1。

(引用 VisuAlgo)

可视化见 VisuAlgo

# 算法实现

#define BOOL size_t
#define FALSE 0
#define TRUE 1
// 原地排序
void bubbleSort(int *arr, int len)
{
    BOOL exchanged = FALSE;
    int last = len; //last 随着冒泡次数而减小
    do
    {
        for (int i = 0; i < last; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                // 交换前后项
                //int 整数型可以使用这种算法,不使用中间变量
                arr[i] ^= arr[i + 1];
                arr[i + 1] ^= arr[i];
                arr[i] ^= arr[i + 1];
                // 交换过了
                exchanged = TRUE;
            }
        }
        last--;// 当 last 减到 0 时,说明已经遍历结束,结束排序
    } while (exchanged && last > 0); // 如果一次冒泡后没有发生交换,说明数组已经有序,结束排序
}

# 选择排序

# 核心原理

从左到右,选择未被排序的数里最小的那个,与数组第一个数交换,然后第二个… 不断重复。

给定 N 个项目和 L = 0 的数组,选择排序将:

  1. 在 [L … N-1] 范围内找出最小项目 X 的位置
  2. 用第 L 项交换 X
  3. 将下限 L 增加 1 并重复步骤 1 直到 L = N-2。

(引用 VisuAlgo)

可视化见 VisuAlgo

# 算法实现

// 原地排序
void selectSort(int *arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        // 找出未被排序的数里最小的那个
        int min = arr[i];
        int minIdx = i;
        for (int j = i; j < len; j++)
        {
            if (min > arr[j])
            {
                min = arr[j];
                minIdx = j;
            }
        }
        // 交换
        arr[minIdx] = arr[i];
        arr[i] = min;
    }
}

# 插入排序

# 核心原理

将未排序的数依次插入到排序好的数中

插入排序类似于大多数人安排扑克牌的方式。

  1. 从你手中的一张牌开始
  2. 选择下一张卡并将其插入到正确的排序顺序中
  3. 对所有的卡重复上一步。

(引自 VisuAlgo)

可视化见 VisuAlgo

# 算法实现

// 原地排序
void insertSort(int *arr, int len)
{
    for (int i = 1; i < len; i++) // 这里默认第一个数就是排好序的,所以索引从第二个数开始
    { 
        // 将未排序的数插入到排序好的数中
        for (int j = 0; j < i; j++)
        {
            if (arr[i] < arr[j]) // 插入
            { 
                // 先缓存要插入的数,因为后面要移动前面的数列,会覆盖它
                int n = arr[i];
                // 移动数列
                for (int k = i; k > j; k--)
                    arr[k] = arr[k - 1];
                // 放入正确的位置
                arr[j] = n;
            }
        }
    }
}

# 优点 & 缺点

# 优点

这几个排序算法比较简单,容易想到,也比较容易理解算法原理。

# 缺点

在数据量变大时,运行效率会非常低,不是很实用。

# 基于比较的排序算法 - O (N log N)

# 归并排序

# 核心原理

将待排序的数组一分为二,分别对左右数组排序,排序时再一分为二,直到分成单个元素,排序完成后再依次合并。

给定一个 N 个项目的数组,归并排序将:

  1. 将每对单个元素(默认情况下,已排序)归并为 2 个元素的有序数组
  2. 将 2 个元素的每对有序数组归并成 4 个元素的有序数组,重复这个过程…
  3. 最后一步:归并 2 个 N / 2 元素的排序数组(为了简化讨论,我们假设 N 是偶数)以获得完全排序的 N 个元素数组。

(引自 VisuAlgo)

可视化见 VisuAlgo

# 算法实现

注:需要 O (n) 的额外空间

// 借助临时数组进行排序
void merge(int *arr, int low, int mid, int high) // 归并排序子函数
{
    int N = high - low + 1;                   // 要排序的数字个数
    int *b = (int *)malloc(N * sizeof(int));  // 创建一个新的数组用来排序
    int lIdx = low, rIdx = mid + 1, bIdx = 0; //lIdx-> 左边数组索引,rIdx-> 右边数组索引,bIdx-> 数组 b 的索引
    // 因为在 low~mid 和 mid+1~high 之间的数都是有序的(从小到大的),所以可以这样
    while (lIdx <= mid && rIdx <= high)
    {
        if (arr[lIdx] < arr[rIdx])
        {
            b[bIdx] = arr[lIdx];
            lIdx++;
        }
        else
        {
            b[bIdx] = arr[rIdx];
            rIdx++;
        }
        bIdx++;
    }
    // 可能左数组或右数组还有剩余项
    // 比如:左数组所有数都小于右数组数的情况下
    while (lIdx <= mid)
        b[bIdx++] = arr[lIdx++];
    while (rIdx <= high)
        b[bIdx++] = arr[rIdx++];
    // 现在数组 b 中是已经排好序的数,再给它们复制回 arr 中
    for (int i = 0, j = low; i < N; i++, j++)
    {
        arr[j] = b[i];
    }
    free(b);
}
void mergeSort(int *arr, int low, int high) // 归并排序
{
    if (low < high)
    {
        // 将待排序的数组一分为二,递归
        int mid = (low + high) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high); // 注:这里的 mid+1 只要和 merge 子函数里 rIdx 的值保持相同就行
        // 归并
        merge(arr, low, mid, high); //mid 从这里传入,在 merge 子函数中 rIdx=mid+1
    }
}

在此基础上还可以加以改进,使得归并排序在原地排序(不借用中间数组),降低空间复杂度,但是似乎会提升时间复杂度O(N log^2 N)-wikipedia

# 快速排序 - O (N^2)/O (N log N)

# 核心原理

  • 经典的快速排序 - O (N^2)/O (N log N):在一开始先选择第一个数作为枢轴点 p,遍历剩余数,把所有小于 p 的数放在左边,所有大于 p 的数放在右边,然后把 p 放在中间;然后对左边的数组和右边的数组再分别重复上面的步骤。(不稳定)
  • 随机快速排序 - O (N log N):在经典快速排序的基础上,每次随机选择枢轴点 p。(比较稳定)

划分步骤:

  1. 选择一个项目 p(称为枢轴点)
  2. 然后将 a [i…j] 的项目分为三部分:a [i…m-1],a [m] 和 a [m + 1…j]。 a [i…m-1](可能为空)包含小于 p 的项目。 a [m] 是枢轴点 p,例如:指数 m 是已排序数组 a 的排序顺序中 p 的正确位置。 a [m + 1…j](可能为空)包含大于或等于 p 的项目。
  3. 然后,递归地对这两部分进行排序。

可视化见 VisuAlgo

# 算法实现

// 原地排序
int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
    int p = arr[low]; // 选取第一个数作为枢轴点
    int m = low;      // 分界点,因为左右区域一开始都是空的,所以 m 要在 0 的位置
    for (int i = low + 1; i <= high; i++)
    {
        // 如果 arr [i]>=p,什么都不用做,继续下一次循环即可 (i++)
        if (arr[i] < p)
        {
            // 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
            m++;
            // 交换 arr [m] 和 arr [i]
            int tmp = arr[m];
            arr[m] = arr[i];
            arr[i] = tmp;
            // 进入下一次循环 i++
        }
    }
    // 交换枢轴点和分界点
    arr[low] = arr[m];
    arr[m] = p;
    // 返回枢轴点所在位置
    return m;
}
void quickSort(int *arr, int low, int high)// 快速排序
{
    if (low < high) // 如果 low>high,说明已经划分为单个
    {
        // 先划分为左右两个区域
        int m = partition(arr, low, high);
        // 再递归对左右两个区域排序
        // 注:m 所在位置已经在正确的位置了,所以不需要包括进去
        quickSort(arr, low, m - 1);
        quickSort(arr, m + 1, high);
    }
}

上面是经典快速排序,使用随机快速排序只需要让 p 随机选取即可。

int partition(int *arr, int low, int high) // 快速排序子函数 - 划分
{
    int pIdx = (rand() % (high - low + 1)) + low; // 随机选取 [low,high]
    // 交换 arr [pIdx] 和 arr [low]
    int p = arr[pIdx];
    arr[pIdx] = arr[low];
    arr[low] = p;
    int m = low; // 分界点,因为左右区域一开始都是空的,所以 m 要在 0 的位置
    for (int i = low + 1; i <= high; i++)
    {
        // 如果 arr [i]>=p,什么都不用做,继续下一次循环即可 (i++)
        if (arr[i] < p)
        {
            // 这里的算法详见 https://visualgo.net/zh/sorting?slide=12-6
            m++;
            // 交换 arr [m] 和 arr [i]
            int tmp = arr[m];
            arr[m] = arr[i];
            arr[i] = tmp;
            // 进入下一次循环 i++
        }
    }
    // 交换枢轴点和分界点
    arr[low] = arr[m];
    arr[m] = p;
    // 返回枢轴点所在位置
    return m;
}
void quickSort(int *arr, int low, int high) // 随机快速排序
{
    srand((unsigned)time(NULL));
    if (low < high) // 如果 low>high,说明已经划分为单个
    {
        // 先划分为左右两个区域
        int m = partition(arr, low, high);
        // 再递归对左右两个区域排序
        // 注:m 所在位置已经在正确的位置了,所以不需要包括进去
        quickSort(arr, low, m - 1);
        quickSort(arr, m + 1, high);
    }
}

# 优点 & 缺点

# 优点

在基于比较的排序算法中已经是最快的了(当然还可以针对不同的数据继续优化),比较实用,在数据量大的情况下表现也不错,可能是现在使用最多的排序算法。

# 缺点

归并排序需要额外的空间,快速排序不是稳定的排序(即它会交换同样大小的数字的顺序)。

# 不基于比较的排序算法

# 计数排序 - O (n+k)

# 核心原理

针对小范围自然数,统计每个数字出现的次数,然后按照从小到大依次输出。

如果要排序的项目是小范围的整数,我们可以计算每个整数(在这个小范围内)的出现频率,然后通过循环该小范围来按排序顺序输出项目。

(引自 VisuAlgo)

# 算法实现

注:需要 O (n+k) 的额外空间

// 借助临时数组排序
void countSort(int *arr, int len, int maxNum) // 计数排序
{
    int *con = (int *)calloc(maxNum + 1, sizeof(int));
    for (int i = 0; i < len; i++)
    {
        con[arr[i]]++; // 统计每个数字出现次数
    }
    for (int i = 0, idx = 0; i <= maxNum; i++)
    {
        while (con[i]-- > 0)
        {
            arr[idx++] = i; // 复制回去
        }
    }
    free(con);
}

# 基数排序 - O (kN)

# 核心原理

针对范围大但数位小自然数,创建 10 个桶 (0-9),按照指定数位,依次放入对应桶中,再放入顺序取出,对每个数位从低到高重复操作。

如果要排序的项目是大范围但小数位的整数,我们可以将计数排序(Counting Sort)思想与基数排序(Radix Sort)结合起来,以实现线性时间复杂度。
在基数排序中,我们将每个项目排序为一个 w 数字串(如果需要,我们填充小于 w 数字的前几个零的整数)。
对于最低有效位(最右边)到最高有效位(最左边),我们通过 N 个项目并将它们按照活动数字放到 10 个队列中(每个数字 [0…9] 一个),就好像 一个修改的计数排序,因为这保留了稳定性。 然后我们再次重新连接组,以便进行后续迭代。

(引自 VisuAlgo)

# 算法实现

注:需要 O (N+k) 的额外空间

void radixSort(int *arr, int len) // 基数排序
{
    int N = len / 10;         // 桶初始化可以装下的元素数 & 后续每次增加量
    int count[10] = {0};      // 每个桶当前装载的元素数量
    int maxCount[10] = {len}; // 每个桶当前能装下的最大元素数量,0 桶设置为 len,原因见下面
    // 初始化桶
    int **con = (int **)malloc(10 * sizeof(int *));
    // 最后遍历完所有数位后,所有的数都会过一遍 0 桶,所以一开始就设置为 len 的长度
    con[0] = (int *)malloc(len * sizeof(int));
    for (int i = 1; i < 10; i++)
    {
        con[i] = (int *)malloc(N * sizeof(int));
        maxCount[i] = N;
    }
    // 遍历每个数位
    BOOL ended = FALSE;
    for (int Bit = 10; Bit <= INT_MAX && !ended; Bit *= 10)
    {
        ended = TRUE;
        for (int i = 0; i < len; i++)
        {
            // 提取当前数位,并将该数放入桶中
            int radix = arr[i] % Bit / (Bit / 10); // 当前数位
            if (count[radix] >= maxCount[radix])
            {
                // 桶满了,重新分配内存空间
                maxCount[radix] *= 2;
                con[radix] = (int *)realloc(con[radix], maxCount[radix] * sizeof(int *));
                if (con[radix] == NULL)
                {
                    // 内存分配失败
                    exit(0);
                }
            }
            con[radix][count[radix]] = arr[i];
            count[radix]++;
        }
        for (int i = 1; i < 10; i++)
        {
            // 判断是否已经遍历结束
            if (count[i] > 0)
            {
                ended = FALSE;
                break;
            }
        }
        for (int i = 0, aIdx = 0; i < 10; i++)
        {
            // 把桶中的元素按照放入顺序放回数组
            for (int cIdx = 0; cIdx < count[i]; cIdx++)
            {
                arr[aIdx++] = con[i][cIdx];
            }
            count[i] = 0;
        }
    }
    for (int i = 0; i < 10; i++)
    {
        free(con[i]);
    }
    free(con);
}

# 优点 & 缺点

# 优点

基于比较的算法有 O (N log N) 的时间复杂度下限,而这些不基于比较的排序可以突破这个下限,使时间复杂度降到线性,针对于特定的数据是最优解。

# 缺点

对数据类型的要求比较苛刻,只在一些特定的数据集时有效。


参考文章:
VisuAlgo - 排序
Wikipedia - 排序算法

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

TagBug 微信支付

微信支付

TagBug 支付宝

支付宝