排序 - 竞技编程&排序算法

可能在学习排序算法的时候会有一个疑惑，无论是c 还是 c++都已经提供了sort函数，为什么还需要花大量的时间去学习排序算法, 还不如把时间都用在学习别的算法上，但是这个想法是片面的 虽然接下来要学的排序算法，在以后做题的一半以上都不会用到，但是不要单纯的想着往后做题会用到他们. 这些算法思想将会伴随着我们学习后面的知识，比如, 堆排序中的贪心思想, 归并排序中的分治思想, 快速排序中的递归思想等等，这些算法能起到预习的作用，后续学习的相应的算法使能够更加的得心应手 除了算法思想，我们在学习这些算法的过程中，还会锻炼: 如何处理写代码时的细节问题, 如何优化算法, 遇见bug如何调试, 分析时空复杂度等等.

---

后续所有的排序算法, 考虑的都是升序的情况. 只要能搞懂原理, 逆序也是一样的

洛谷排序模板题: https://www.luogu.com.cn/problem/P1177

---

插入排序

Insert Sort 插入排序类似于玩扑克牌的理牌(插牌)过程: 每次将一个待排序的元素按照关键字大小插入到前面已经有序的序列中, 按照这种方式将所有元素全部插入完成即可

样例代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int arr[N];

void insertSort(int arr[], int n)
{
    for (int i = 2; i <= n; i++)
    {
        int key = arr[i];
        int p = i - 1;

        while (key < arr[p] && p != 0)
        {
            arr[p + 1] = arr[p];
            p--;
        }
        arr[p + 1] = key;
    }
}


int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

    insertSort(arr, n);

    for (int i = 1; i <= n; i++)
    {
        cout << arr[i] << ' ';
    }
    return 0;
}

时间复杂度O(n^2)

• 最好情况: 整个数组已经升序了, O(n)
• 最坏情况: 整个数组逆序, O(n^2)

稳定性

是稳定的

---

选择排序

Selection Sort 选择排序是一种特别直观的排序算法: 每次找出未排序序列中最小的元素, 然后放进有序序列的后面

样例代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int arr[N];

void selectSort(int arr[], int n)
{
    for (int head = 1; head < n; head++)
    {
        // 从无序区间[head, n] 找出最小值的下标
        int min = head;
        for (int j = head + 1; j <= n; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }
        swap(arr[head], arr[min]);
    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

    selectSort(arr, n);

    for (int i = 1; i <= n; i++)
    {
        cout << arr[i] << ' ';
    }
    return 0;
}

时间复杂度O(n^2)

由于每交换一个数它都要找一遍最小值, 相当于两个for嵌套在一起了, 所以不管它是否已经升序了, 他的时间复杂度都是O(n^2)

稳定性

选择排序的稳定性取决于其具体实现．

倘若使用链表实现，由于链表的任意位置插入和删除均为 𝑂(1)，故无需使用 swap（交换两个元素）操作：每次从未排序部分选择最小元素（若有多个，选取第 1 个）后，将其插入到未排序部分的第 1 个元素之前，这样就能够保证稳定性．

假如使用数组实现（OI 中一般的实现方式），由于数组任意位置插入和删除均为 𝑂(𝑛)，故只能使用 swap 将未排序部分的元素移到已排序部分．swap 操作使得数组实现的选择排序不稳定．

---