本文主要是介绍两段已序子数组 就地排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
输入：数组 a，分成两段；第一段长度为 m，已序，第二段长度为 n，已序
要求：将整个数组 a 排列为全部有序，只使用一个临时变量，即空间复杂度为 O(1)
解决思路
设定数组 a[m+n]，第一段为 a[i]， 0 < i < m-1；第二段为 a[j]， m < j < m+n-1。
方法：将第二段的元素依次插入到第一段已序的子数组中，即特殊的插入排序。
何时插入过程结束？
分两种情况：
1、当第二段最后一个元素 a[m+n-1] 插到第一段中( j == m+n-1 )。这意味着第二段的全部元素均已插入。
2、当第二段一个元素 >= 第一段最后一个元素，相当于插入在当前位置，即位置不变( i == j-1 )。这意味着数组已经全部有序，无需对第二段还剩下的元素继续插入。
源码如下：
void sortInPlace (int *a, int m, int n)
{
int i, j, p, temp;
i = 0;
j = m;
while ( j < m + n &&
i < j )
{
if ( a[i] > a[j] )
{
temp = a[j];
for ( p = j; p > i; --p )
a[p] = a[p-1];
a[p] = temp;
++i;
++j;
}
else
{
++i;
}
}
}
这篇关于两段已序子数组 就地排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
