排序算法 | CS

说几个你懂的排序算法，并说明其时间空间复杂度

冒泡排序：通过相邻元素的比较和交换，每次将最大（或最小）的元素逐步“冒泡”到最后（或最前）。时间复杂度：最好情况下O(n)，最坏情况下O(n²)，平均情况下O(n²)。空间复杂度：O(1)。
插入排序：将待排序元素逐个插入到已排序序列的合适位置，形成有序序列。时间复杂度：最好情况下O(n)，最坏情况下O(n²)，平均情况下O(n²)，空间复杂度：O(1)。
选择排序（Selection Sort）：通过不断选择未排序部分的最小（或最大）元素，并将其放置在已排序部分的末尾（或开头）。时间复杂度：最好情况下O(n²)，最坏情况下O(n²)，平均情况下O(n²)，空间复杂度：O(1)。
快速排序（Quick Sort）：通过选择一个基准元素，将数组划分为两个子数组，使得左子数组的元素都小于（或等于）基准元素，右子数组的元素都大于（或等于）基准元素，然后对子数组进行递归排序。时间复杂度：最好情况下O(nlogn)，最坏情况下O(n²)，平均情况下O(nlogn)，空间复杂度：最好情况下O(logn)，最坏情况下O(n)。
归并排序（Merge Sort）：将数组不断分割为更小的子数组，然后将子数组进行合并，合并过程中进行排序。时间复杂度：最好情况下O(nlogn)，最坏情况下O(nlogn)，平均情况下O(nlogn)。空间复杂度：O(n)。
堆排序（Heap Sort）：通过将待排序元素构建成一个最大堆（或最小堆），然后将堆顶元素与末尾元素交换，再重新调整堆，重复该过程直到排序完成。时间复杂度：最好情况下O(nlogn)，最坏情况下O(nlogn)，平均情况下O(nlogn)。空间复杂度：O(1)。

讲一下冒泡排序算法

冒泡排序：通过相邻元素的比较和交换，每次将最大（或最小）的元素逐步“冒泡”到最后（或最前）

冒泡排序的最好时间复杂度出现在以下情况：当待排序数组已经有序时，即每个元素都比其前面的元素小，那么在第一次遍历数组时就可以确定排序已经完成，因此时间复杂度为O(n)。
冒泡排序的时间复杂度为O(n²)。因为在排序过程中，需要进行多次遍历和元素交换，而每次遍历都需要比较相邻的元素并决定是否进行交换，这种操作需要花费O(n)的时间。因此，冒泡排序的时间复杂度通常为O(n²)。

public void bubbleSort(int[] arr) {
    int n = arr.length;
    // 外层循环控制比较轮数
    for (int i = 0; i < n - 1; i++) 
        for (int j = 0; j < n - i - 1; j++) 
            if (arr[j] > arr[j + 1]) 
                swap(arr[j],arr[j+1]);        
}

讲一下快排原理

快排使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，再把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

快排的过程简单地说只有三步：

首先从序列中选取一个数作为基准数
将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边（一次快排partition）
然后分别对基准的左右两边重复以上的操作，直到数组完全排序

具体按以下步骤实现：

1，创建两个指针分别指向数组的最左端以及最右端
2，在数组中任意取出一个元素作为基准
3，左指针开始向右移动，遇到比基准大的停止
4，右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
5，重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
6，然后分别对基准的左右两边重复以上的操作，直到数组完全排序

注意这里的基准该如何选择？最简单的一种做法是每次都是选择最左边的元素作为基准，但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过Math.random()来随机选取一个数作为基准。

int partation(int *nums,int left,int right) {
    int &num=nums[left];
    while (left<right) {
        while (left<right&&nums[right]>=num)--right;
        while (left<right&&nums[left]<=num)++left;
        swap(nums[left],nums[right]);
    }
    swap(nums[left],num);
    return left;
}

void quick_sort(int *nums,int left,int right) {
    if (left>=right)
        return;
    int pos=partation(nums,left,right);
    quick_sort(nums,left,pos-1);
    quick_sort(nums,pos+1,right);
}

堆排序算法原理，稳定吗？

如果每个节点大于等于子树中的每个节点，我们称之为大顶堆，小于等于子树中的每个节点，我们则称之为小顶堆。

堆的要求：

必须是完全二叉树
堆中的每一个节点，都必须大于等于（或小于等于）其子树中每个节点的值。

堆通常是使用一维数组进行保存，节省空间，不需要存左右子节点的指针，通过下标就可定位左右节点和父节点。

父节点i的左子节点在(2i+1)的位置
父节点i的右子节点在(2i+2)的位置
子节点i的父节点在(i-1)/2向下取整的位置

我们可以把堆排序的过程大致分为两大步骤，分别是建堆和排序。

建堆：建堆操作就是将一个无序的数组转化为最大堆的操作，首先将数组原地建一个堆。“原地”的含义就是不借助另一个数组，就在原数组上操作。我们的实现思路是从后往前处理数据，并且每个数据都是从上向下调整。
排序：建堆结束后，数组中的数据已经按照大顶堆的特性进行组织了，数组中的第一个元素就是堆顶，也就是最大的元素。我们把它和最后一个元素交换，那最大的元素就放到了下标为n的位置，此时末尾元素就是最大值，将剩余元素重新堆化成一个大顶堆。继续重复这些步骤，直至数组有序排列

归并排序和快速排序的使用场景

归并排序是稳定排序算法，适合排序稳定的场景；

快速排序是不稳定排序算法，不适合排序稳定的场景，快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

什么是排序稳定性？

排序算法的稳定性是指在排序过程中，当有多个具有相同关键字的元素时，这些元素在排序后的序列中保持它们原有的相对顺序。

换句话说，如果两个元素有相同的键值，那么在排序前，如果第一个元素在第二个元素之前，排序后第一个元素也应该在第二个元素之前。

稳定和不稳定排序算法有什么特点？

稳定排序算法的特点：
- 相同元素的相对位置不会改变，排序后仍然保持原始顺序。
- 适用于需要保持元素间相对顺序关系的场景，如按照年龄排序后按姓名排序。
不稳定排序算法的特点：
- 相同元素的相对位置可能会改变，排序后不保证原始顺序。
- 可能会更快，但不适用于需要保持元素间相对顺序关系的场景。

说说快排流程，时间复杂度

快速排序的流程如下：

从数组中选择一个基准元素（通常是数组中间位置的元素）。
将数组分成两部分，小于基准元素的放在左边，大于基准元素的放在右边。
递归地对左右两部分进行快速排序。

快速排序的时间复杂度为(O(n \log n))，其中n为数组的长度。最坏情况下时间复杂度为(O(n^2))，发生在每次选择的基准元素都是最大或最小值时。平均情况下时间复杂度为(O(n \log n))，效率较高。

快排为什么时间复杂度最差是O（n²）

主要是因为在每次划分时选择的基准元素不合适导致的。当每次选择的基准元素都是当前子数组中的最大或最小元素时，就会导致每次划分只能减少一个元素，而不是均匀地分成两部分，从而造成时间复杂度达到O(n²)。

这种情况通常发生在数组已经有序或基本有序的情况下。为了避免最坏情况发生，可以通过随机选择基准元素或者使用三数取中法等策略来提高快速排序的性能。

快排这么强，那冒泡排序还有必要吗？

冒泡排序在一些特定场景下仍然有其优势，比如：

对于小规模数据或基本有序的数据，冒泡排序可能比快速排序更简单、更直观。
冒泡排序是稳定排序算法，相对于快速排序的不稳定性，在某些情况下可能更适合要求稳定性的场景。
冒泡排序是原地排序算法，不需要额外的空间，适合空间复杂度要求严格的场景。

如果要对一个很大的数据集，进行排序，而没办法一次性在内存排序，这时候怎么办？

可以使用外部排序来解决，基本思路分为两个阶段。

部分排序阶段

我们根据内存大小，将待排序的文件拆成多个部分，使得每个部分都是足以存入内存中的。然后选择合适的内排序算法，将多个文件部分排序，并输出到容量可以更大的外存临时文件中，每个临时文件都是有序排列的，我们将其称之为一个“顺段”。

在第一个阶段部分排序中，由于内存可以装下每个顺段的所有元素，可以使用快速排序，时间复杂度是O(nlogn)。

归并阶段

我们对前面的多个“顺段”进行合并，思想和归并排序其实是一样的。以2路归并为例，每次都将两个连续的顺段合并成一个更大的顺段。

因为内存限制，每次可能只能读入两个顺段的部分内容，所以我们需要一部分一部分读入，在内存里将可以确定顺序的部分排列，并输出到外存里的文件中，不断重复这个过程，直至两个顺段被完整遍历。这样经过多层的归并之后，最终会得到一个完整的顺序文件。

归并阶段有个非常大的时间消耗就是IO，也就是输入输出。最好就是让归并的层数越低越好，为了降低归并层数，可以使用败者树。

在败者树中，左右孩子比较后，胜者继续向上参与下一轮比较，而败者则被存入当前的非终端节点；整个树的非终端节点里存的都是 “败者”，最终的全局胜者会单独记录在一个额外的节点（比如根节点对应的 “冠军节点”）中。

现在有了败者树的加持，多路归并排序就可以比较高效地解决外部排序的问题了。

大致思路就是：

先用内排序算法（比如快速排序），尽可能多的加载源文件，将其变成n个有序顺段。
在内存有限的前提下每k个文件为一组，每次流式地从各个文件中读取一个单词，借助败者树选出字典序最低的一个，输出到文件中，这样就可以将k个顺段合并到一个顺段中了；反复执行这样的操作，直至所有顺段被归并到同一个顺段。