部分插入排序

Question

是否可以使用插入排序原则仅对数组中的前 k 个元素进行排序？

因为当算法遍历数组时，它会相应地排序。

由于要检查所有的元素（找出谁最小），所以最终会排序。

示例：

原始数组：{5, 3, 8, 1, 6, 2, 8, 3, 10}

k = 3的预期输出：{1, 2, 3, 5, 8, 6, 8, 3, 10}（仅对前 k 个元素排序，其余元素未排序）

Answer 1

这样的部分排序是可能的，而结果方法看起来像是选择排序的混合体——在数组尾部搜索最小元素的部分，和插入排序——在移动元素的部分（但没有比较） .排序保留尾元素的顺序（虽然没有明确要求）

Ideone

void ksort(int a[], int n, int k)
  { int i, j, t;
    for (i = 0; i < k; i++)
      { int min = i;
        for (j = i+1; j < n; j++) 
            if (a[j] < a[min]) min = j;
        t = a[min];
        for (j = min; j > i; j--) 
            a[j] = a[j-1];
        a[i] = t;
      } 
  }

Answer 2

是的，这是可能的。这将运行及时 O(k n) 其中 n 是数组的大小。

你最好使用堆排序。它将运行及时 O(n + k log(n)) 代替。 heapify步骤是O(n)，那么每个提取的元素是O(log(n)).

技术说明。如果你够聪明，你可以将堆反向建立到数组的末尾。所以当你把它想象成一棵树时，把第 n-2i, n-2i-1 个元素放在第 n-i 个元素的下面。所以拿你的数组：

{5, 3, 8, 1, 6, 2, 8, 3, 10}

那是一棵像这样的树：

当我们堆化我们得到树：

也就是说数组：

{5, 3, 8, 10, 6, 3, 8, 2, 1}

现在每次提取元素都需要将最后一个元素交换到最终位置，然后让大元素"fall down the tree"。像这样：

# swap
{1*, 3, 8, 10, 6, 3, 8, 2, 5*}
# the 5 compares with 8, 2 and swaps with the 2:
{1, 3, 8, 10, 6, 3, 8?, 5*, 2*}
# the 5 compares with 3, 6 and swaps with the 3:
{1, 3, 8, 10, 6?, 5*, 8, 3*, 2}
# The 5 compares with the 3 and swaps, note that 1 is now outside of the tree:
{1, 5*, 8, 10, 6, 3*, 8, 3, 2}

数组树表示中的哪个是：

再次重复，我们得到：

# Swap
{1, 2, 8, 10, 6, 3, 8, 3, 5}
# Fall
{1, 2, 8, 10, 6, 5, 8, 3, 3}

又名：

再一次：

# swap
{1, 2, 3, 10, 6, 5, 8, 3, 8}
# fall
{1, 2, 3, 10, 6, 8, 8, 5, 3}

或

以此类推

Answer 3

以防万一将来有人需要它，我想出了一个“纯粹”的解决方案，即不是原始插入排序和其他排序算法之间的混合体。

void partialInsertionSort(int A[], int n, int k){
    int i, j, aux, start;
    int count = 0;
    for(i = 1; i < n; i++){
        aux = A[i];

        if (i > k-1){
            start = k - 1;
            //This next part is needed only to maintain
            //the original element order
            if(A[i] < A[k])
                A[i] = A[k];
        }
        else start = i - 1;

        for(j = start; j >= 0 && A[j] > aux; j--)
                A[j+1] = A[j];

        A[j+1] = aux;
    }
}

基本上，此算法对前 k 个元素进行排序。然后，第k个元素就像一个枢轴：只有当剩余的数组元素小于这个枢轴时，它才会被插入到排序后的k个元素之间的正确位置，就像在原始算法中一样。

最佳情况：数组已排序

考虑到比较是基本操作，那么比较的次数就是2n-k-1→Θ(n)

最坏情况：数组倒序

考虑到比较是基本操作，那么比较的次数就是(2kn - k² - 3k + 2n)/2→Θ(kn)

（两者都考虑了为维护数组顺序所做的比较）

部分插入排序

Partial Insertion Sort

algorithm

insertion-sort

partial-sort