排序算法（总结）-C++

篇幅较长请耐心看完

C++ 中实现排序算法有多种方式，这些算法各有优缺点，适用于不同的场景。以下是一些经典的排序算法及其简要说明和C++代码实现的概述：

冒泡排序 ($BubbleSort$)

• 原理：通过重复遍历要排序的数列，比较每对相邻元素的值，如果顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
• 复杂度：平均时间复杂度$O(n^2)$，最好情况$O(n)$，最坏情况$O(n^2)$，空间复杂度$O(1)$

选择排序 ($SelectionSort$)

• 原理：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
• 复杂度：无论最好、最坏还是平均情况，时间复杂度均为$O(n^2)$，空间复杂度$O(1)$。

插入排序 ($InsertionSort$)

• 原理：把待排序的数组分成已排序和未排序两部分，初始时已排序部分只包含第一个元素，然后依次从未排序部分取出元素插入到已排序部分的正确位置。
• 复杂度：最好情况$O(n)$，最坏情况$O(n^2)$，平均情况$O(n^2)$，空间复杂度$O(1)$。

希尔排序 ($ShellSort$)

• 原理：是插入排序的一种更高效的版本，通过将原始数据分割成若干子序列，先让这些子序列基本有序，然后再对全体记录进行一次直接插入排序。
• 复杂度：取决于间隔序列的选择，最坏情况可以达到$O(n^2)$，但通过好的间隔序列选择，可以降低到$O(nlogn)$。

归并排序 ($MergeSort$)

• 原理：采用分治法的思想，将数组分成两半分别排序，再将结果合并在一起。这是一个递归过程。
• 复杂度：时间复杂度为$O(nlogn)$，空间复杂度$O(n)$。

快速排序 ($QuickSort$)

• 原理：也是分治法，选择一个基准元素，通过一趟排序将待排记录分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序。
• 复杂度：平均时间复杂度$O(n$ $log$ $n)$，最坏情况$O(n^2)$，但通过随机选取基准可以优化至几乎总是$O(n$ $log$ $n)$，空间复杂度$O(log$ $n)$。

堆排序 ($HeapSort$)

• 原理：利用堆这种数据结构所设计的一种排序算法。将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
• 复杂度：时间复杂度$O(n$$log$$n)$，空间复杂度$O(1)$。

计数排序 ($CountingSort$)

• 原理：是一种非比较型整数排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，它对于小范围内的整数排序非常高效。
• 复杂度：时间复杂度$O(n+k)$，其中k为待排序数组中最大数与最小数的差值加$1$，空间复杂度O$(n+k)$。
这些算法在实际应用中，根据数据的特点和需求（如数据量大小、是否原地排序、稳定性要求等）选择最适合的算法。

快排

在$C++$标准库中，也提供了高效的排序函数
std::sort，它通常使用的是某种形式的快速排序，并且在特定情况下会自动切换到其他算法以保持高性能。

---

C++/Python排序算法
有一部分是已经出了文的，剩下的我会努力肝的！