使用Insertion Sort按排序顺序返回数组的k个最小元素

Question

我正在准备软件开发人员的工作面试和复习算法问题.我无法弄清楚如何修改插入排序算法,以便它按排序顺序返回大小为n的数组的k个最小元素.

插入排序算法

for i = 1 to n
  j = i
  while j > 0 and A[j-1] > A[j]
    swap A[j] and A[j-1]
    j = j - 1

在算法结尾添加for循环以获取前k个元素不计算在内.

Answer 1

通过正常的插入排序,您可以从头到尾循环,并且每个项目都会向上移动直到它就位.使用此插入排序,您仍然可以从头到尾循环,但如果您所在的项目是> =第k个项目,则保留它; 如果更少,将其移动到位置k,然后向上移动直到它到位.

for i = 1 to k
  j = i
  while j > 1 and A[j-1] > A[j]
    swap A[j] and A[j-1]
    j = j - 1

现在排序前k个项目.

for i = k + 1 to n
  if A[i] < A[k]
    swap A[i] and A[k]
    j = k
    while j > 1 and A[j-1] > A[j]
      swap A[j] and A[j-1]
      j = j - 1