部分插入排序

这样的部分排序是可能的,而产生的方法看起来像是选择排序的混合-在数组尾部最小元素的搜索部分,和插入排序-在移位元素的部分(但没有比较)。排序保留尾部元素的顺序(尽管没有明确要求)

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

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

你最好用heapsort。它将及时运行 O(n + k log(n)) O(n) ,则提取每个元素 O(log(n)) .

n-2i, n-2i-1 下的元素 n-i 第1个。所以拿你的阵型来说:

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

那是一棵这样的树:

 10
     3
         2
             3
             5
         6
     8
         1
         8

当我们把树堆起来时:

 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

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

最佳情况:阵列已订购

考虑到比较是最基本的操作,那么比较的次数是 2n-k-1

最坏情况:数组顺序相反

(2kn - k² - 3k + 2n)/2 (千牛)

(两者都考虑了为保持数组顺序而进行的比较)