Sch*_*mer 14 sorting algorithm
我有一个部分排序的数组,其属性是每个元素都在其正确排序位置的d个单位内.我想知道是否有一种方法可以在不到n log n的时间内对这个数组进行排序 - 通过利用这一事实.
是; 可以在O(nd)时间内排序.一种解决方案是插入排序的简单修改.我们从头到尾处理输入数组; 对于每个元素,我们查看输出数组的最后d个元素,并将新元素插入其适当的位置.
当然,可能有更快的算法; 这种特殊的算法选择是为了更容易证明渐近界.
脱离我的头顶......
创建一个大小为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的d个单位,所以整个范围最多只有d个单位.所以j也在i'的d个单位内,并且i在j'的d个单位内,所以当我们用A [j]交换A [i]时,两个元素仍然在它们所属的d的范围内.案例2和案例3的分析是相似的.
因此,冒泡排序的每一步 - 在A的任何子序列上 - 将保留所需的属性,从中可以得出整个冒泡排序将保留所需的属性,从中可以得出任何排序都将保留所需的属性.QED