1

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

因为当算法在数组上运行时，它会相应地排序。

由于需要检查所有元素（找出谁是最小的），它最终会对整个事物进行排序。

例子：

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

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

4

3 回答 3

1

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

爱迪生

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;
      } 
  }
于 2018-09-14T17:19:12.400 回答
1

对的，这是可能的。这将及时运行，您的数组大小在O(k n)哪里。n

你最好使用堆排序。它会及时运行O(n + k log(n))。heapify 步骤是O(n)，然后提取的每个元素是O(log(n))。

技术说明。如果你够聪明，你会在数组末尾建立堆。因此，当您将其视为一棵树时，请将第n-2i, n-2i-1th 个元素放在第 th 个元素的下方n-i。所以带上你的数组：

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

那是一棵像这样的树：

 10
     3
         2
             3
             5
         6
     8
         1
         8

当我们 heapify 时，我们得到了树：

 1
     2
         3
             3
             5
         6
     8
         10
         8

也就是说数组：

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

现在每个元素提取都需要将最后一个元素交换到最终位置，然后让大元素“从树上掉下来”。像这样：

# 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}

在数组树表示中是：

{1}
2
    3
        3
             5
        6
    8
       10
        8

再次重复，我们得到：

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

又名：

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

然后再次：

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

或者

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

等等。

于 2018-09-14T17:49:14.793 回答
0

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

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)

（两者都考虑到为维护数组顺序而进行的比较）

于 2018-09-20T23:36:18.857 回答