部分插入排序
是否可以使用插入排序原则对数组中的第一个k元素进行排序？
因为当算法在数组上运行时，它将进行相应的排序。
因为它需要检查所有的元素(找出谁是最小的)，所以它最终会对整个事情进行排序。
示例：
原始数组：{5，3，8，1，6，2，8，3，10}
k = 3的预期输出：{1，2，3，5，8，6，8，3，10} (只有第一个k元素被排序，其余的元素没有排序)
回答 3
Stack Overflow用户
发布于 2018-09-14 17:19:12
这样的部分排序是可能的，而产生的方法看起来像是选择排序的混合--在数组尾部搜索最小元素的部分，在移位元素的部分(但没有比较)。排序保留尾元素的顺序(尽管没有显式要求)
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;
}
}Stack Overflow用户
发布于 2018-09-14 17:49:14
是的，这是可能的。这将在time O(k n)中运行，其中n是数组的大小。
你最好使用堆排序。它将在时间O(n + k log(n))中运行。heapify步骤是O(n)，然后提取的每个元素都是O(log(n))。
一份技术性说明。如果您很聪明，您将将堆反向建立到数组的末尾。所以当你把它看作一棵树的时候，把n-2i, n-2i-1th元素放在n-ith元素下面。因此，拿出你的数组：
{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诸若此类。
Stack Overflow用户
发布于 2018-09-20 23:36:18
为了防止将来有人需要这样做，我想出了一个“纯”的解决方案，它不是原始插入排序算法和其他排序算法之间的混合体。
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)。
(两者都考虑到为维护数组顺序而进行的比较)
https://stackoverflow.com/questions/52336098
复制相似问题
腾讯云开发者
