0%

常用排序算法汇整

注:文章中的 GIF 均来源于网络,定义来源于百度百科

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
插入排序 O(n2) O(n) O(n2) O(1) 稳定
归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定
快速排序 O(n log n) O(n log n) O(n2) O(n log) 不稳定
计数排序 O(n + k) O(n + k) O(n + k) O(k) 稳定

请注意,这个表格中以下几种排序方法需要交换元素

  • 冒泡排序
  • 选择排序
  • 快速排序

总之,只要在下方提供的代码中发现有 swap() 函数的都是需要交换元素

冒泡排序

冒泡可以求逆序对个数,就是统计交换个数

重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从 A 到 Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成

  1. 相邻元素两两一对(例如1, 2, 3中就有(1, 2)(2, 3)这两对)
  2. 依次比较每对中的两个数,比如(A, B)中,若A > B(规则可自定)则交换两个数的位置

↓ 百度百科中数组从 0 开始的代码:

#include <cstdio>
#include <algorithm>

const int n = 8; // (int) sizeof(a) / sizeof(*a)
int a[] = {5, 6, 3, 1, 8, 7, 2, 4};

int main()
{
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (a[j] > a[j + 1])
                std::swap(a[j], a[j + 1]);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

也可以这么写(数组从 1 开始):

for (int i = 1; i <= n; i++)
    for (int j = 1; j < n; j++)
        if (a[j] > a[j + 1])
            std::swap(a[j], a[j + 1]);

也可以这么写(数组从 1 开始):

for (int i = n - 1; i > 0; i--)
    for (int j = 1; j < i + 1; j++)
        if (a[j] > a[j + 1])
            std::swap(a[j], a[j + 1]);

选择排序

第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

  1. 第一重循环 i:从左往右依次枚举
  2. 第二重循环:在 i 的位置往后寻找比 a[i] 最小的数
  3. 若存在,则交换

↓ 百度百科中数组从 0 开始的代码:

#include <cstdio>
#include <algorithm>

const int n = 5;
int a[] = {2, 5, 1, 3, 4};

int main()
{
    for (int i = 0; i < n - 1; i++)
    {
        int tmp = i;
        for (int j = i + 1; j < n; j++)
            if (a[tmp] > a[j])
                tmp = j;

        if (tmp != i)
            std::swap(a[tmp], a[i]);
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

也可以这么写(数组从 1 开始):

for (int i = 1; i < n; i++)
{
    int tmp = i;
    for (int j = i + 1; j <= n; j++)
        if (a[tmp] > a[j])
            tmp = j;

    if (tmp != i)
        std::swap(a[tmp], a[i]);
}

插入排序

将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为 O(n2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中

每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止

↓ 百度百科中数组从 0 开始的代码:

#include <cstdio>

const int n = 5;
int a[] = {2, 5, 1, 3, 4};

int main()
{
    for (int i = 1; i < n; i++)
    {
        int tmp = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > tmp)
            a[j + 1] = a[j], j--;

        if (j != i - 1)
            a[j + 1] = tmp;
    }

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);

    return 0;
}

也可以这么写(数组从 1 开始):

for (int i = 2; i <= n; i++)
{
    int tmp = a[i];
    int j = i - 1;

    while (j >= 0 && a[j] > tmp)
        a[j + 1] = a[j], j--;

    if (j != i - 1)
        a[j + 1] = tmp;
}

归并排序

归并排序不仅可以排序,还可以求逆序对数

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序

两个有序表合并成一个有序表,称为二路归并

  1. 不断地把一段数据分成两部分直到不能分
  2. 两两合并最终组成一段有序数组

推荐阅读 归并排序详解,Java版描述。 - 过道 - 博客园

注:代码实现的是归并排序 + 求逆序对,如不需要求逆序对,只需要删除有关“ans”变量的内容即可

逆序对实战 考试鄙视 | rcxzsc

#include<cstdio>

int a[1005], r[1005], n, ans;
void msort(int s, int t)
{
    if (s >= t)
        return;
    int mid = s + t >> 1;
    msort(s, mid), msort(mid + 1, t);

    int i = s, j = mid + 1, k = s;
    while (i <= mid && j <= t)
        if (a[i] <= a[j])
            r[k++] = a[i++];
        else
            r[k++] = a[j++], ans += mid - i + 1; 
    while (i <= mid)
        r[k] = a[i], k++, i++;
    while (j <= t)
        r[k] = a[j], k++, j++;
    for (int i = s; i <= t; i++)
        a[i] = r[i];
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    msort(1, n);

    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);

    printf("\n%d\n", ans);
    return 0;
}

快速排序

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

  1. 选择一个数为基准
  2. 小于基准的移到左边,大于基准的移到右边
  3. 对基准左边右边的两个子集不断重复上述过程

关于快排,stl 中有一些实现快排的函数,比如 sort()

#include <cstdio>
#include <algorithm>

const int n = 9;
int a[] = {0, 5, 6, 3, 1, 8, 7, 2, 4};

void qsort(int l, int r)
{
    if (r <= l)
        return;
    int i = l, j = r + 1, key = a[l];
    while (true)
    {
        while (a[++i] < key)
            if (i == r)
                break;

        while (a[--j] > key)
            if (j == l)
                break;

        if (i >= j)
            break;

        std::swap(a[i], a[j]);
    }
    std::swap(a[l], a[j]);

    qsort(l, j - 1);
    qsort(j + 1, r);
    return;
}

int main()
{
    qsort(1, n);

    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
    return 0;
}

计数排序

这是最快最简单的排序算法,但同时也是最浪费内存的一种算法

举例{5, 2, 3, 1, 1}

a[1] a[2] a[3] a[4] a[5]
2 1 1 0 1

最后遍历数组,输出{1, 1, 2, 3, 5}

#include <cstdio>

int n, a[1005];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        a[x]++;
    }


    for (int i = 1; i <= 1000; i++)
        for (int j = 1; j <= a[i]; j++)
            printf("%d ", i);
    return 0;
}

↑ 其实这是一种不规范的做法,我写成这样是为了便于理解

另:推荐阅读:

  1. 排序算法gif动图+javascript - 简书
  2. 前端面试必备 —— 基本排序算法
  • 本文作者: rcxzsc
  • 本文链接: https://rcxzsc.com/archives/748/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY 许可协议。转载请注明出处!