我有一个部分排序的数组,其特点是每个元素都在其正确排序位置的d个单位内。我想知道是否有一种方法可以利用这个特点,在少于n log n的时间内对该数组进行排序。
我有一个部分排序的数组,其特点是每个元素都在其正确排序位置的d个单位内。我想知道是否有一种方法可以利用这个特点,在少于n log n的时间内对该数组进行排序。
就我所知...
创建一个大小为2d的“滑动窗口”。
从[0,2d)开始。对窗口中的元素进行排序;现在,0到d-1个元素被保证正确。
将窗口向前滑动d,现在是[d,3d)。对这些元素进行排序,保证了d到2d-1之间的元素是正确的。
再向前滑动d,现在是[2d,4d)。对这些元素进行排序。以此类推。
每次排序都是O(d log d),需要n/d步才能到达末尾,因此这是O(n/d * d log d) = O(n log d)。如果d是常数,那么就是O(n)。
[编辑]
您在评论中提出了一个很好的观点;我没有证明每个迭代都保留了每个元素都在其正确位置的d个单位的属性。
所以...
引理:如果A是具有每个元素都在其正确位置的d个单位内的属性的数组,并且您对A中的任何连续子序列进行排序以创建数组A',则A'中的每个元素都在其正确位置的d个单位内。
证明:由于这是关于排序性质(而不是性能)的引理,因此使用哪种算法对我们没有影响。所以使用冒泡排序。找到子序列中任意两个顺序不正确的元素并交换它们。只有三种情况:两个元素都在数组中的正确位置之前;两个元素都在数组中的正确位置之后;或者它们在数组中的正确位置之间。
例如,假设A[i]属于位置i',A[j]属于位置j',i<j,但A[i]>A[j]。那么i'>j'(因为这是元素“应该在”的地方,而且A[i]>A[j])。情况1:假设i'和j'都大于i和j;也就是说,顺序是i<j<j'<i'。但是根据假设,i'距离i仅有d个单位,因此整个范围最多只有d个单位宽。因此,j也在i'的d个单位内,i也在j'的d个单位内,因此当我们交换A[i]和A[j]时,两个元素仍然在它们应该在的位置附近d个单位内。情况2和情况3的分析类似。
因此,冒泡排序的每个步骤 - 在A的任何子序列上 - 都将保留所需的属性,从而可以得出整个冒泡排序将保留所需的属性,从而可以得出任何排序都将保留所需的属性。证毕。
是的,可以在O(nd)时间内进行排序。一种解决方案是对插入排序进行简单修改。我们从头到尾处理输入数组;对于每个元素,我们查看输出数组的最后d个元素,并将新元素插入到其适当的位置。
当然,可能会有更快的算法;选择这种特定的算法是为了更容易地展示渐近界限。
O(nd)
,但查找范围在 max 0 (i-d)
... min n (i+d)
之间。 - nlucaronii
之后的元素,因为我们还没有在那里插入任何元素。如果i
应该放在i+d
处,它将被稍后插入放置到那里。 - bdonlan是的,不管你信不信,冒泡排序可能是部分排序数组中最好的排序算法。当数组完全有序时,其最佳情况的性能为O(n)。
维基百科关于冒泡排序的介绍:http://en.wikipedia.org/wiki/Bubble_sort
编辑:具体来说,是“改进的冒泡排序”,带有一个标志以在已经按顺序排列时跳过交换操作。