排序部分排序的数组 [英] Sorting a partially sorted array

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/2726785/interview-q-sorting-an-almost-sorted-array-elements-misplaced-by-no-more-than-k">Interview问：排序几乎排序的数组（元素放错地方不超过k）的

我有一个完全排序的数组，每个元素是它的正确排序位置D单元中的属性。我想知道如果有一种方法，以这个数组排序 - 通过利用这一事实 - 在不到的n log n倍

I have a partially sorted array with the property that every element is within d units of its properly sorted position. I am wondering if there is a way to sort this array -- by exploiting this fact -- in less than n log n time.

推荐答案

关闭我的头顶......

Off the top of my head...

创建尺寸2D的滑动窗口。

Create a "sliding window" of size 2d.

开始它在[0,2d）。排序的窗口中的元素;现在元素0到d-1，保证是正确的。

Start it at [0,2d). Sort the elements in the window; now elements 0 through d-1 are guaranteed to be correct.

用d滑动窗口前进，所以现在它的[2D，3D）。排序那些元素，低保元素通过2D-1 D是正确的。

Slide the window forward by d, so now it's [d,3d). Sort those elements, guaranteeing that elements d through 2d-1 are correct.

向前滑动另一个研发，所以现在它的[2D，4D）。排序的。等等。

Slide it forward another d, so now its [2d,4d). Sort those. And so on.

每个排序是O（D记录D），这需要N / D步骤去年底，所以这是O（N / D * D记录D）= O（N日志D）。如果d是不变的，那是为O（n）。

Each sort is O(d log d), and it takes n/d steps to get to the end, so this is O(n/d * d log d) = O(n log d). If d is constant, that's O(n).

您做出评论好点;我没有证明每次迭代preserves每一个元素是它应有的位置D单元中的属性。

You make a good point in a comment; I did not prove that each iteration preserves the property that every element is within d units of its proper position.

所以...

引理：如果A是与每一个元素是它应有的位置D单元内的财产的数组，你理清内的任何连续子创建一个数组A'，然后每在一个元素'是D单元内它的正确位置。

Lemma: If A is an array with the property that every element is within d units of its proper position, and you sort any contiguous subsequence within A to create an array A', then every element in A' is within d units of its proper position.

证明：由于这是一个引理约排序（而不是性能）的特性，它并不重要算法，我们用它来进行排序。因此，使用冒泡排序。查找在乱序的序列任意两个元素，并交换它们。只有三种情况：这两种元素在数组中的适当位置之前;两者都是在数组中的适当位置后，或它们的阵列在其适当的位置之间移动。

Proof: Since this is a lemma about the properties of a sort (not performance), it does not matter what algorithm we use to sort. So use bubble sort. Find any two elements in the subsequence that are out of order, and swap them. There are only three cases: Both elements are before their proper positions in the array; both are after their proper positions in the array; or they are between their proper positions in the array.

例如，假设A [1]所属位置i'和[J]所属的位置j'，I＆LT; Ĵ，但A [1]> A [J]。由此可见，我'> J'（因为这是元素属于，和A [1]> A [J]）。案例1：假设我'和j'都大于i和j;即，为了变为I＆其中; J＆LT; J'＆LT;一世'。但是，假设，我'是我唯一的D单元，所以这整个航程只有D单元宽最多。所以j是也D单元内的我'，我为j的D单元内'，所以当我们交换A [I]与A [J]，两种元素都仍然在的D属于他们的地方。在分析案例2和案例3是相似的。

For example, suppose A[i] belongs at position i' and A[j] belongs at position j', i < j, but A[i] > A[j]. It follows that i' > j' (because that is where the elements "belong", and A[i] > A[j]). Case 1: Suppose i' and j' are both greater than i and j; that is, the order goes i < j < j' < i'. But by hypothesis, i' is only d units from i, so this entire range is only d units wide at most. So j is also within d units of i' and i is within d units of j', so when we swap A[i] with A[j], both elements are still within d of where they belong. The analysis for Case 2 and Case 3 are similar.

所以冒泡排序的每个步骤 - 对A的任何亚序列 - 将preserve所期望的性质，从它遵循的整个冒泡排序将preserve所期望的性质，从它如下是的任意的排序将preserve所需属性。 Q.E.D。

So each step of a bubble sort -- on any subsequence of A -- will preserve the desired property, from which it follows that the entire bubble sort will preserve the desired property, from which it follows that any sort will preserve the desired property. Q.E.D.

这篇关于排序部分排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！