Python解决方案：排序K排序数组

在此问题中，我们将得到一个整数数组。该数组将是 k 排序的。k 排序数组是指数组中的每个元素距离最终排序数组（目标排序数组）最多只有 k 步。

让我们来看一些例子来理解这个问题

示例

输入： 数组 = [5, 3, 2, 10, 9], K = 3

输出： 数组 = {2, 3, 5, 9, 10}

输入： 数组 = [10, 9, 7, 4, 60, 50], k = 4

输出： 数组 = [4, 7, 9, 10, 50, 60]

方法 - 1

我们将使用插入排序算法来解决此问题。在此方法中，插入排序会将数组中的每个元素放置在正确的位置，从而对数组进行排序。这是一种有效的解决此问题的方法，因为我们可以使用每个元素的索引，该索引最多可以改变 k 个索引。

以下是我们将要遵循的解决此问题的步骤。

• 我们将从第一个索引开始遍历数组直到最后一个索引。
• 然后，在每次迭代中，我们将当前索引处的元素与前一个元素进行比较。
• 如果当前元素小于前一个元素，那么我们将此元素与前一个元素之前的元素进行比较。我们将继续进行此操作，直到找到一个小于当前元素的前驱元素。一旦找到前驱元素的索引，我们将当前元素插入到该前驱元素之后。
• 我们将继续对数组中的每个元素执行此操作。最后，我们将得到最终排序的数组。

下面是展示如何使用插入排序解决此问题的 Python 代码。

代码

输出

[4, 7, 9, 10, 50, 60]

时间复杂度： 由于我们使用了嵌套循环，此方法的时​​间复杂度是非线性的。内循环将遍历最多 k 次。外循环将针对数组的每个元素运行。因此，它将运行 N 次。因此，此方法的最终时间复杂度为 O(N * k)。

辅助空间： 我们没有使用任何额外的空间来解决此问题；因此，此方法的空间复杂度为 O(1)。

方法 - 2

在第二种方法中，我们将考虑 k 排序数组的属性。之前，每当当前元素不在正确顺序时，我们都会将每个元素向右移动。这会花费额外的时间，因为一个向左移动 x 次的元素如果在其左侧添加了 x 个元素，可能会再次回到相同的位置。因此，在此方法中，我们将仅在当前元素距离正确位置超过 k 个位置时才移动元素。此方法将优化程序的时​​间复杂度。此方法效果很好，因为给定的数组几乎是排序的；因此，我们不需要将每个元素都放到其正确的位置。已经执行了 k 次排序操作。

下面是此方法的实现。

代码

输出

4 7 9 10 50 60  

时间复杂度： 此方法的时​​间复杂度比前一种方法要好。但是，这两种方法的最坏情况时间复杂度是相同的。时​​间复杂度相同，因为可能存在每个元素距离正确位置 k 的距离的情况。在这种情况下，内循环将最多运行 k 次。因此，这两种方法的最坏情况时间复杂度相同，即 O(N * k)。

辅助空间： 我们没有使用任何额外的空间来解决此问题；因此，此方法的空间复杂度为 O(1)。

方法 - 3

在此方法中，我们将使用堆来解决此问题。

我们将遵循以下步骤来解决此问题。

• 我们将初始化一个大小为 k + 1 的最小堆。我们创建大小为 k + 1 的堆是因为给定数组中的元素距离正确位置的索引最多可能有 k 的距离。
• 然后，我们将使用另一个循环从堆中删除最小元素，然后将该元素放入最终排序的数组中。

下面是该方法在 Python 中的实现。

代码

输出

4 7 9 10 50 60  

时间复杂度： 此方法的时​​间复杂度为 O(K) + O(m * log(k))

辅助空间： 此方法的空间复杂度为 O(K)，这是存储堆所需的空间。