每天三道面试算法题，坚持一百天✊

该仓库仅用来记录。。

快速排序和归并排序的稳定性差异

假设我们有一组订单数据，每个订单包含两个属性：订单号和交易日期。我们首先根据订单号对这些订单进行了排序，现在我们想根据交易日期再次进行排序。

初始数据（已按订单号排序）：

订单号	交易日期
001	2023-03-15
002	2023-03-12
003	2023-03-15
004	2023-03-14

使用稳定排序算法（如归并排序）：

订单号	交易日期
002	2023-03-12
004	2023-03-14
001	2023-03-15
003	2023-03-15

在这个例子中，订单001和订单003具有相同的交易日期（2023-03-15）。在使用稳定排序算法进行排序后，这两个订单的相对位置（按订单号）保持不变，即订单001仍然在订单003之前。

使用不稳定排序算法（如快速排序）：

订单号	交易日期
002	2023-03-12
004	2023-03-14
003	2023-03-15
001	2023-03-15

在使用不稳定排序算法进行排序后，具有相同交易日期的订单001和订单003可能会改变它们的相对位置。如上所示，订单003现在排在订单001之前，尽管它们的交易日期相同。

结论

• 在使用稳定排序算法时，具有相同关键字的元素将保持它们原始的相对顺序。
• 在使用不稳定排序算法时，具有相同关键字的元素可能会改变它们原始的相对顺序。

选择使用哪种排序算法取决于特定应用中是否需要保持元素的原始相对顺序。

快速选择算法和使用最小堆的方法在寻找第 k 个最大元素时的时间复杂度和空间复杂度。

• 快速选择算法 时间复杂度：

平均情况：O(n)，其中 n 是数组的长度。快速选择是基于快速排序的，但它只需要递归地处理数组的一个部分，而不是整个数组。 最坏情况：O(n^2)，在极端情况下（如每次都选到最大或最小元素作为基准），每次划分只减少一个元素。 空间复杂度：

O(1)（原地操作）。快速选择算法不需要额外的存储空间，它在原数组上进行操作。

• 使用最小堆 时间复杂度：

O(n log k)，其中 n 是数组的长度，k 是堆的大小。对于数组中的每个元素，我们都需要进行堆插入操作，每次插入操作的时间复杂度是 O(log k)。 空间复杂度：

O(k)，因为我们维护了一个大小为 k 的最小堆