一个数组,内部是由两个有序的数组构成的,例如4 7 8 6 2 ,如果已经知道内部有序的位置3 ,通过设计算法,得到整体有序(从小到大)数组 2 4 6 7 8
题目要求:
最坏情况下时间复杂度为:O(n)
辅助空间为:O(1)
- 问题思考
将两个数组按照从小到大的顺序先排序(交换位置即可),然后前后比较;具体过程:
4 7 8 6 2
4 7 8 2 6
2 7 8 4 6
2 4 8 7 6 --> 6 7
2 4 6 8 7 --> 7 8
得到结果 2 4 6 7 8
代码如下:
#include<stdio.h>
//合并两个排好顺序的子数组
void sort_1(int a[],int low,int high)
{
int temp,i;
if(a[low] < a[high]) return; //如果是降序,就不交换位置
else
{
temp = a[low];
a[low++] = a[high];
a[high--] = temp;
}
}
void swap_1(int a[],int low,int mid,int high)
{
int temp;
//前后比较
while(low < high)
{
if(a[low] > a[mid +1])
{
temp = a[low];
a[low] = a[mid+1];
a[mid+1] = temp;
sort_1(a,mid+1,high);
}
low++;
}
}
void main(){
int i; int num; int k;
printf("请输入数组长度\n");
scanf("%d",&num);
int a[num];
for(i = 0; i < num; i++)
{
scanf("%d",&a[i]);
}
printf("请输入有序断点\n");
scanf("%d",&k);
sort_1(a,0,k-1);
sort_1(a,k,num-1);
swap_1(a,0,k-1,num-1);
for(i = 0; i < num; i++)
{
printf("%d ",a[i]);
}
}

网友评论