前言说明

本文均以升序为例

表格分析

算法名称	平均时间	最优时间	最差时间	空间	排序方式	稳定性
冒泡	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	内部	稳定
选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	内部	不稳定
插入	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	内部	稳定
希尔	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (1)$	内部	不稳定
快速	$O (n l o g n)$	$O (n l o g n)$	$O(n^2)$	$O (n l o g n)$	内部	不稳定
归并	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (n)$	外部	稳定
堆	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (1)$	内部	不稳定

专业性介绍

衡量一个排序的参数，一般为 时间复杂度,空间复杂度,稳定性,

稳定性： 指数列中相同的元素，在排序完成后相对顺序是否改变

如(这里用下标表示)：原来数列 $2_0, 1_0, 1_1]$

稳定： $1_0, 1_1， 2_0]$

不稳定： $1_1, 1_0, 2_0]$

分类介绍

按时间复杂度分类

${O(n^2)}$
${O(nlogn)}$
${O(n)}$

按照排序方式分类

比较型
非比较型

按辅助空间分类

内部排序
外部排序

题集

牛客：简单的排序

数据范围：

$1 < = n < = 1000$

适合练习简单的排序

洛谷： P1177 【模板】快速排序

数据范围：

对于 $20\%$ 的数据，有 $N\leq 10^3$ ；

对于 $100\%$ 的数据，有 $N\leq 10^5$ 。

力扣： 912. 排序数组

数据范围：

$1 <= nums.length <= 5 * 10^4$

$5 * 10^4 <= nums[i] <= 5 * 10^4$

时间复杂度 ${O(n^2)}$

冒泡排序 (bubble sort)

不断比较相邻的两个数据，使得较大(或较小)的数据不断往一边靠

有冒泡和沉底两种思路，但核心都差不多

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    // 确定一遍的i个数据已成为有序
    for (int i = 0; i < n; i++) {
        // 不断比较相邻数据 -i可以免去再次比较已经排好的数据
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

选择排序 (select sort)

不断在未排好的区间内找到最大(最小)值

将该值与已排序的边缘外一个元素交换

void selectSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        int minn = i;
        for (int j = i; j < n; j++) {
            if (arr[minn] > arr[j]) {
                minn = j;
            }
        }
        swap(arr[minn], arr[i]);
    }
}

插入排序 (insert sort)

循序枚举每个元素，以一个方向去判断大小

若相对大小不合格，则逆向覆盖掉来向的数据，最后记得存储一个枚举的数据

写的时候还有不少细节，需要注意

注意： 插入排序没最后排好之前，无法保证任何元素是否在最终位置。这点与冒泡和选择不同

void insertSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        // 暂存需要插入的数据
        int cur = arr[i];
        // 从该数据的前一个位置开始试着判断插入
        int j = i-1;
        for (j = i-1; j >= 0 && cur < arr[j]; j--) {
            // 若符合则往后覆盖
            arr[j+1] = arr[j];
        }
        // 退出循环只有两个情况
        // 1.j==-1, 2.j处比cur还小
        // 因此是j的后一个位置要被cur覆盖
        arr[j+1] = cur;
    }
}

时间复杂度 ${O(nlogn)}$

希尔排序 (shell sort)

时间复杂度约 $O(n^{1.3})$ 并非严格的 $O (n l o g n)$

希尔排序是插入排序的一种改良版，是一种缩小增量排序

朴素的插入排序的每次比较的数值是相邻的数值，差值为1

而希尔排序通过不断的将差值从大到小递减(直到1)，来使一些元素相对位置提前排好便于后面的排序能减少插入次序

当n较小的时候，与 $O(n^2)$ 差别不大

此处展示的是增量2倍递减的形式

上述的力扣 5e4 可过; 洛谷 1e5可过

void insertSort(vector<int>& arr, const int step) {
    int n = arr.size();
    for (int i = step; i < n; i++) {
        int cur = arr[i];
        int j = i-step;
        for (j = i-step; j >= 0 && cur < arr[j]; j -= step) {
            arr[j+step] = arr[j];
        }
        arr[j+step] = cur;
    }
}
void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int step = n>>1; step > 0; step >>= 1) {
        insertSort(arr, step);
    }
}

快速排序 (quick sort)

大名鼎鼎的快速排序

各种平台为了卡特殊情况，设置了长段有序数列，从而让快排的时间复杂度退化到了 $O(n^2)$

为了解决这个问题，要随机获得一个序列的值，以该值来快排，可以避免一直出现有序而效率退化的问题

加了随机后力扣可过，洛谷最后一个测试样例还是不可过

实现思路：

传入区间是闭区间 $[s t a r t, e n d]$

在该区间内获得一个随机值
将该值交换到序列的某一端处（此处交换到最左端）
记录此时(交换后的)的最左端值 int pivot = arr[left];
此时arr[left]是一个空位
====================前置准备========================
因为此时是左边有空置位置，所以先搜索右边
右边搜索完，与左边的空置位置交换，此时空置位置到了右边
开始搜索左边
。。。循环操作。。。
当letf == right时终止
将最后的空置位置存储最开始存储的pivot
==================一轮排序完毕======================
此时letf 就是分割点
分治递归该分割点的两边

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
private:
    // 范围0~n-1
    void quickSort(vector<int>& arr, const int start, const int end) {
        if (start >= end) {
            return ;
        }

        int left = start;
        int right = end;
        
        // 区间内随机捕获的一个数值
        int pivotIdx = rand()%(right-left+1) + left;
        // 将该随机获得的数值靠到边界
        swap(arr[pivotIdx], arr[left]);
        
        // 获取对照值
        int pivot = arr[left];
        while (left < right) {
            // left处可存值，因此先搜索右边
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            arr[left] = arr[right];
            // 右边搜索完毕，left空位存值完毕，而right处变为可供存值
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            arr[right] = arr[left];
        }
        // left == right 退出，此处就是用来存最后的pivot
        arr[left] = pivot;

        pivotIdx = left;
        quickSort(arr, start, pivotIdx-1);
        quickSort(arr, pivotIdx+1, end);
    }

};

归并排序 (merge sort)

直观的解释，就是合并两个有序序列

与快排有点类似，不断分割小区间，将每次分割的两个区间有序合并

若当前的两个小区间均有序，则合并的大区间必然有序

递归return 条件左右指针相碰
先均分当前的区间
递归两段分割的区间，使得两段成为有序序列
合并两段有序序列，达到当前大区间排序好
从合并的格外空间抄回原数组

class Solution {
private:
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }
private:
    void mergeSort(vector<int>& arr, const int start, const int end) {
        if (start >= end) {
            return ;
        }

        int mid = (end-start)/2 + start;
        // 先将两部分进行排序
        mergeSort(arr, start, mid);
        mergeSort(arr, mid+1, end);

        // 到了这步，就是说明两边已经有序了
        // 注意：这里的边界要与前面递归的相同
        int leftIdx = start;
        int rightIdx = mid+1;
        int tmpIdx = 0;
        // 合并两个有序序列
        while (leftIdx <= mid && rightIdx <= end) {
            if (arr[leftIdx] <= arr[rightIdx]) {
                tmp[tmpIdx++] = arr[leftIdx++];
            } else {
                tmp[tmpIdx++] = arr[rightIdx++];
            }
        }
        while (leftIdx <= mid) {
            tmp[tmpIdx++] = arr[leftIdx++];
        }
        while (rightIdx <= end) {
            tmp[tmpIdx++] = arr[rightIdx++];
        }

        // 注意：这里不能直接用tmp把arr覆盖，因为每次都是一个规定的闭区间的操作
        for (int i = 0; i < tmpIdx; i++) {
            arr[i+start] = tmp[i];
        }
        return ;
    }
};

堆排序 (heap sort)

个人认为very nice 的一个排序

将数组当作一颗完全二叉树

大顶堆获得递增序列

建堆(大顶堆)
因为是完全二叉树，所以后一半的叶子节点可以直接掠过
自底向上调整，可以保证大数值能不断向顶部跑

不断交换首元素和未排序的末尾元素，使得最后元素称为未排序的最大元素
每次交换完后调整堆：调整顶点
堆的调整
退出条件：该点的概念上的孩子均超出最大范围
若左右孩子中有一个比当前点大，则交换
并重新调整交换位置的子树

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }

private:
    void modifyHeap(vector<int>& arr, int cur, int last) {
        // 这是一个完全二叉树
        // 该点在未排序范围内还有孩子
        while ((cur<<1)+1 <= last) {
            // 数组下标0~n-1
            // 所以左右孩子是 2*i+1；2*i+2
            int leftSon = (cur<<1)+1;
            int rightSon = (cur<<1)+2;
            int large = cur;

            // 分别判断左右是否还有孩子，且比父节点大
            if (leftSon <= last && arr[leftSon] > arr[large]) {
                large = leftSon;
            }
            if (rightSon <= last && arr[rightSon] > arr[large]) {
                large = rightSon;
            }
            // 所比父节点大
            if (large != cur) {
                // 交换，保证父节点大于孩子
                swap(arr[cur], arr[large]);
                // 交换的那个孩子节点继续调整
                cur = large;
            } else {
                // 无更新，则直接退出循环
                break;
            }
        }
    }

    void buildMaxHeap(vector<int>& arr) {
        int last = arr.size()-1;
        // 逆序初始化大顶堆
        // 完全二叉树，直接略过后一半的叶子节点
        for (int i = last/2; i >= 0; i--) {
            modifyHeap(arr, i, last);
        }
    }

    void heapSort(vector<int>& arr) {
        // 建堆
        buildMaxHeap(arr);

        for (int last = arr.size()-1; last >= 1; last--) {
            // 将最大值交换到最后
            swap(arr[0], arr[last]);
            // last位置有序不可用了
            // 从顶部开始调整
            modifyHeap(arr, 0, last-1);
        }

        return ;
    }

};

其他有趣的排序

猴子排序 (monkey sort)

随机打乱，那只要打乱次数的基数大，理论上就有可能排序成功

void monkeyShuffle(const int n) {
    vector<int> arr(n);
    iota(arr.begin(), arr.end(), 0);

    int cnt = 0;
    random_shuffle(arr.begin(), arr.end());
    while(!is_sorted(arr.begin(), arr.end()) ) {
        cnt++;
        printf("第%05d次猴子打乱\t", cnt);
        random_shuffle(arr.begin(), arr.end());
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " \n"[i == n-1];
        }
    }

    return ;
}

煎饼排序 (pancake sort)

固定首位置，不断寻找未排序的最大值

先将[0, maxx] 翻转，使得0位置最大

在将0位置的最大值反转到尾部

力扣：969. 煎饼排序

class Solution {
public:
    vector<int> pancakeSort(vector<int>& arr) {
        int n = arr.size();

        vector<int> ans;
        for (int i = n-1; i >= 0; i--) {
            int idx = max_element(arr.begin(), arr.begin()+i+1) - arr.begin();
            reverse(arr.begin(), arr.begin()+idx+1);
            ans.push_back(idx+1);
            reverse(arr.begin(), arr.begin()+i+1);
            ans.push_back(i+1);
        }

        return ans;
    }
};