电面遇到一个没见过的排序算法

题目：
给定一个大数据量未排序数组和int k
这个数组满足这样的条件:
排序过之后数组和原数组比较，每个位置的移动范围小于k
写出排序算法

我想到的思路是，类似冒泡排序，但是只需要做k轮冒泡。
挂了

没明白面试官的思路，他想要考察什么。大家有好的想法么？


补充内容

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

出，这个是geeksforgeeks上的那个k sorted array排序    用Insert sort 复杂度是O(n*k), 用最小堆是O(n*logk)

xujun 发表于 2015-7-9 01:03
如果第一个数是最大的数，你这个算法是必然会排到最后的。

好像是那个geeksforgeeks上的那个k sorted array排序， 题目是意思是input的数组本身就满足排序之后每个数都移动不超过k这个性质, 不是说让找到一个算法满足这个性质   所以只需要维护K大小的heap，时间是NlogK

解题思路是：

使用一个大小为K的最小堆，开始将前K个建一个最小堆，然后将最小的取出，然后将第K+1个元素添加到最小堆，然后取第二个最小，然后将第K+2个放入最小堆，...

如此可以使用O(N*log(K))的时间可以排序。

证明为什么可以使用最小堆来做：

1. 首先可以证明最小的一个一定出现在前K个元素中，否则排序之后最小的元素和原来的位置相差一定超过K。

2. 利用1的性质可以知道第二小的元素一定出现在去掉最小元素后的堆和K+1的元素集合中，而不可能出现在第K+2及其以后的元素中

搜索一下，原来这也不是新题

dylanwang 发表于 2015-7-8 14:14
解题思路是：

使用一个大小为K的最小堆，开始将前K个建一个最小堆，然后将最小的取出，然后将第K+1个元 ...

如果第一个数是最大的数，你这个算法是必然会排到最后的。

这是典型的insertion sort, 复杂度可以做到O(n*k)，可以看一下它的wiki，并且insertion sort是online sorting，可以处理大数据。

补充内容 (2015-7-9 05:56):
不对，我看错题目了，我以为“每个位置的移动范围小于k”是assumption，不好意思楼主！

补充内容 (2015-7-9 06:00):
不过又看了下评论，好像“每个数组的位置和它sorted的位置差k”确实是条件？

这样吧：如果是条件，可以用insertion sort，O(n*k)
             如果是需要实现成这样，那么可以用quicksort，设置constant cutoff为k

补充内容 (2015-7-9 06:41):
不过用heap那样做nlog(k)确实是更好的方法

额想 问个 比较 小白的问题 。。。。 排序后 可不可以 不是 “严格 完成 排序”

也就是说  排序的同时 要考虑 每个位置的 限制
如果是这样 就有点像 排列任务 不仅有 优先级还有 时间周期

那额 感觉可以 用一个 k长度的 doubly list和 k大小的 heap来实现
排序完前 k－1个 元素后：先check list的 head item(如果 后面的item是 一次放入tail的话) 如果周期未结束 再extract heap的(heap 的每个 item 也有一个 指向list的 指针 有点像 LRU)

补充内容 (2015-7-9 06:51):
list里面的 每个 item 也要有一个 指针指向 heap

running time 应该是 O(n log k)

请问是google的店面题吗? 楼上sliding window + heap 是正解！

larry_cn 发表于 2015-7-9 06:46
额想 问个 比较 小白的问题 。。。。 排序后 可不可以 不是 “严格 完成 排序”

也就是说  排序的同时  ...

给定的数组，再引入double list有点麻烦了吧，没看太明白