对近乎排序、k 排序或几乎排序的数组进行排序

在本文中，我们将详细学习如何对一个几乎排序的数组进行排序。

对几乎排序的数组进行排序是什么意思？

当我们能够通过以下方式之一对数组进行排序时：

1. 交换两个值，
2. 反转数组的一个子段，
3. 或将某些元素移动 k 个位置，

那么这种情况就被认为是“对几乎排序、k-排序或近似排序的数组进行排序”。

例如

上面给出的数组是几乎排序的，其中一些元素要么错位了 k 个位置，要么少数元素以相反的顺序排列。

最简单的想法是使用最好的排序算法（如归并排序）来对数组进行排序，时间复杂度为 O(n logn)。但是，有更高效的方法来对几乎排序的数组进行排序。下面讨论了对几乎排序数组进行排序的最佳方法。

方法 1

通过使用插入排序，这种方法的时间复杂度为 T(n) = O(n k)，其中 n 是问题或数组的大小，外部的 for 循环最多运行 n 次，而内部的 while 循环最多运行 k 次。

空间复杂度 = O(1)，因为不需要额外的空间。

下面给出了用不同编程语言对几乎排序的数组进行排序的程序。

C++ 代码

示例输出

Sorted Array = {3, 4, 5, 6, 7, 8, 9, 10, 13}

C 代码

示例输出

Sorted Array = {21, 22, 23, 24, 32, 33, 34, 35, 36}

Python 代码

示例输出

Sorted array = [5, 6, 7, 9, 10, 11, 12, 13, 15]

方法 2

通过使用最小堆，可以借助最小堆来解决上述问题。在这种方法中，我们使用了最小堆的思想。

第一步 - 我们创建一个大小为 k+1 的最小堆，并将前 k+1 个元素插入其中。我们创建一个大小为 k+1 的最小堆是因为在排序后的数组中，元素可能与其最终位置相差 k 个距离。这个过程需要 O(k) 的时间。

第二步 - 我们从堆中移除最小的元素，并将其插入到数组中。每次从堆中移除一个元素后，我们从原数组中取出下一个元素插入到堆中，并对剩下的 n-k 个元素重复相同的过程。添加和移除元素的方法需要 O(log k) 的时间。

程序的实际时间复杂度等于 T(n) = O(k) + O(n-k) * O(log k) = O(m * log k)，其中 m = n-k。有时，它也被认为是 T(n) @ O(n * log k)。

C++ 代码

示例输出

Original array = 5 7 4 6 12 8 9 10
Sorted array = 4 5 6 7 8 9 10 12

时间复杂度：T(n) = O(k) + O(n-k) * O(log k) = O(m * log k)，其中 m = n-k

空间复杂度：= O(k)

同样的问题可以用 AVL 树（自平衡树）以相同的时间复杂度解决，因为插入和删除操作可以在 O(log k) 时间内完成。其总成本为 O(n logk)。但最小堆比 AVL 树更受青睐，因为它不需要额外的空间来存储左右指针，并且比 AVL 树更简单。

方法 3

上述问题可以使用快速排序算法来解决，以获得比上述方法更好的时间复杂度。如果您不了解快速排序算法的工作原理，请通过给定的链接学习快速排序算法的技术细节。< https://tpointtech.cn/quick-sort>

在这种方法中，我们遵循两个思路：

1. 选择中间元素作为枢轴，而不是第一个或最后一个元素。
2. 扫描范围是从 max(left, mid - k) 到 min(mid + k, right)，而不是从左到右。

选择中间元素作为枢轴的想法是为了将数组分成两半，以获得更好的对数时间复杂度。该方法的实现如下所示。

C++ 代码

示例输出

Given array = 2 5 2 4 4 6 7 7 12 12 10 9 8 
Sorted array = 2 2 4 4 5 6 7 7 8 9 10 12 12

C 代码

示例输出

Given array = 6 5 5 3 1 3 1 11 14 12 12 13 
Sorted array = 1 1 3 3 5 5 6 11 12 12 13 14

时间复杂度: T(n) = O(k Logn)

空间复杂度: O(Logk)

我们可以从时间和空间复杂度中观察到，这种方法比前两种方法更好。