排序算法介绍

skystars · 发表于 2021-12-8 13:38:50

给出一个有n（n<=1000000）个数的数列a，请对该数列从小到大进行排序（数列a中所有数都是正整数，且不大于1000000）。

我们这次也使用洛谷作为评测工具（C++14 O2），对一些排序算法进行测试，测试数据分为子任务1和子任务2。

冒泡排序

冒泡排序是一种稳定的排序算法，这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序的最好情况（即数列已经有序）的时间复杂度为O(n)，最坏情况和平均情况为O(n^2)。

代码如下：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[1000005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[ i ]);
    }
    bool swapped = false; // 是否交换过
    do {
        swapped = false; // 初始化
        for (int i = 1; i < n; i++) { // 注意这里的循环条件是i<n，因为是将第i个数和第i+1个数比较
            if (a[ i ] > a[i + 1]) {
                swap(a[ i ], a[i + 1]); // 如果第i个数大于第i+1个数，交换
                swapped = true; // 标记为交换过
            }
        }
    } while (swapped); // 交换过，则继续进行排序，否则退出（已经有序）
    for (int i = 1; i <= n; i++) {
        printf("%d ", a[ i ]);
    }
    return 0;
}

测试结果如下图所示：

选择排序

选择排序的时间复杂度为 O(n^2)，排序过程如下：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[1000005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[ i ]);
    }
    for (int i = 1; i < n; i++) {
        int minn = i; // 将最小数位置设为未排序数列中的第一个数的位置
        for (int j = i + 1; j <= n; j++) { // i之前是排序数列，所以从i+1开始
            if (a[j] < a[minn]) { // 如果第j个数比之前找到的最小数小
                minn = j; // 则把最小数的位置设为第j个数的位置
            }
        }
        swap(a[ i ], a[minn]); // 将最小数放到排序数列中的最后一个位置
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", a[ i ]);
    }
    return 0;
}

测试结果（比冒泡排序快了很多）：

插入排序

最好情况时间复杂度为 O(n)，最坏情况和平均情况为 O(n^2)。

代码：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[1000005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[ i ]);
    }
    for (int i = 2; i <= n; i++) {
        int k = a[ i ]; // 确定待排序的数
        for (int j = i - 1; j >= 1; j--) { // i之前是排序序列，所以从i-1开始倒着循环向前比较
            if (a[j] > k) { // 如果第j个数大于待排序的数
                a[j + 1] = a[j]; // 插入
                a[j] = k;
            }
            else break; // 如果第j个数小于等于待排序的数，说明已经放到了正确的位置，不用再排序了
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", a[ i ]);
    }
    return 0;
}

测试结果（比选择排序又更快了）：

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

代码：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[1000005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[ i ]);
    }
    for (int gap = (1 + n) / 2; gap > 0; gap /= 2)
        for (int i = gap; i <= n; i++)
            for (int j = i - gap; j > 0 && a[j] > a[j + gap]; j -= gap)
                swap(a[j], a[j + gap]);
    for (int i = 1; i <= n; i++) {
        printf("%d ", a[ i ]);
    }
    return 0;
}

测试结果（已经通过了Subtask #1）：

skystars · 发表于 2021-12-9 13:12:44

快速排序

快速排序是C. A. R. Hoare于1960提出的一种算法，是对冒泡排序的一种改进。通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序的平均时间复杂度为 O(nlogn)，速度快，但它是不稳定的排序算法。

代码实现如下：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[1000005];
void quicksort(int l, int r) {
    int i = l, j = r, mid = a[(l + r) / 2]; // mid为中间数
    do {
        while (a[i] < mid) i++; // 查找左半部分比中间数大的数
        while (a[j] > mid) j--; // 查找右半部分比中间数小的数
        if (i <= j) { // 如果有一组不满足排序条件（左小右大）的数
            swap(a[i], a[j]); // 交换
            i++, j--; // 继续找
        }
    } while (i <= j);
    if (l < j) quicksort(l, j); // 递归搜索左半部分
    if (i < r) quicksort(i, r); // 递归搜索右半部分
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    quicksort(1, n);
    for (int i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

测试结果如下：

计数排序

计数排序就是建立一个数组，然后将每个数的数量存入数组中，最后从小到大循环输出结果即可完成排序。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[1000005];

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

测试结果如下：

虽然计数排序简单快捷，但是在数据范围过大时就不能使用这种算法了。

skystars · 发表于 2021-12-10 13:31:19

Timsort

TimSort 是一个归并排序做了大量优化的版本。对归并排序排在已经反向排好序的输入时做了特别优化。对已经正向排好序的输入减少回溯。对两种情况混合（一会升序，一会降序）的输入处理比较好。

代码如下（部分来自https://www.geeksforgeeks.org/timsort/）：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
int a[1000005];
#define RUN 32
void insertionSort(int arr[], int left, int right) // 插入排序
{
    for (int i = left + 1; i <= right; i++)
    {
        int temp = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > temp)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

void MERGE(int arr[], int l, int m, int r)
{

    int len1 = m - l + 1, len2 = r - m;
    vector<int> left(len1), right(len2);
    for (int i = 0; i < len1; i++)
        left[i] = arr[l + i];
    for (int i = 0; i < len2; i++)
        right[i] = arr[m + 1 + i];

    int i = 0;
    int j = 0;
    int k = l;


    while (i < len1 && j < len2)
    {
        if (left[i] <= right[j])
        {
            arr[k] = left[i];
            i++;
        }
        else
        {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < len1)
    {
        arr[k] = left[i];
        k++;
        i++;
    }

    while (j < len2)
    {
        arr[k] = right[j];
        k++;
        j++;
    }
}


void timSort(int arr[], int n)
{

    for (int i = 0; i < n; i += RUN) // 对大小为 RUN 的单个子数组进行排序
        insertionSort(arr, i, min((i + RUN - 1),(n - 1)));


    for (int SIZE = RUN; SIZE < n; SIZE = 2 * SIZE) {

        for (int left = 0; left < n; left += 2 * SIZE) {
            int mid = left + SIZE - 1;
            int right = min((left + 2 * SIZE - 1),
                (n - 1));
            if (mid < right)
                MERGE(arr, left, mid, right); // 合并
        }
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

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

测试结果如下：

最后，我们总结一下各种排序算法的时间复杂度和空间复杂度：

图片来源：https://www.bigocheatsheet.com/

skystars · 发表于 2021-12-10 13:40:05

同时通过两个子任务的排序算法耗时如下：

计数排序	847ms
快速排序	1.05ms

Timsort	1.08ms
希尔排序	1.45ms

第二个子任务超时的算法耗时如下（仅计算第一个子任务的耗时）：

插入排序	92ms
选择排序	167ms

冒泡排序

494ms

[算法] 排序算法介绍

本帖子中包含更多资源

评分

本帖子中包含更多资源

本帖子中包含更多资源

优秀版主

活跃会员

最佳新人

灌水之王