哪位大佬可以帮忙解释一下，感激（明天考试）急
将互不相同元素的升序排列，重新存入数组a中，返回升序排列后互不相同元素的个数。#include <stdio.h>
int sort(int a[],int n)
{
int i,j,k,low,high,mid,t;
for(k=i=1;i<n;i++)
{
low=0;
high=k-1;
while(low<=high)
{
mid=(low+high)/2;
if(a>=a) high=mid-1;
elselow=mid+1;
}
if(low>=k||a!=a)
{
/*******************FOUND*******************/
t=a;
/*******************FOUND*******************/
for(j=k-1;j>=low;j--)
a=a;
a=t;
k++;
}
}
return k;
}
int main()
{
int a[ ]={6,2,7,5,4,3,4,6,5,4};
int i,n;
n=sizeof(a)/sizeof(int);
for(i=0;i<n;i++)
printf("%d\t",a);
/*******************FOUND*******************/
n=sort(a,n);
printf("\nAfter sorting:\n");
for(i=0;i<n;i++)
printf("%d\t",a);
printf("\n");
return 0;
}
思路是从第二个数开始使用二分查找法，然后把元素插入找到的位置，时间复杂度应该是O(nlogn)
#include <stdio.h>
int sort(int a[], int n)
{
int i, j, k, low, high, mid, t;
for (k = i = 1; i < n; i++)
{
low = 0;
high = k - 1;
while (low <= high) //二分查找，现在前k个数已经排序完毕，需要插入一个数a
{
mid = (low + high) / 2;
if (a >= a) high = mid - 1;
elselow = mid + 1;
} //返回时，low==high+1。low的为第一个大于等于a的位置,height为第一个小于a的位置；
if (low >= k || a != a) //当a不与排列好的数字重复时
{
/*******************FOUND*******************/
t = a;
/*******************FOUND*******************/
for (j = k - 1; j >= low; j--) //把大于a的元素都向后挪一步
a = a;
a = t; //插入a
k++; //现在有k+1个元素排列好了
}
}
return k;
}
int main()
{
int a[] = { 6,2,7,5,4,3,4,6,5,4 };
int i, n;
n = sizeof(a) / sizeof(int);
for (i = 0; i < n; i++)
printf("%d\t", a);
/*******************FOUND*******************/
n = sort(a, n);
printf("\nAfter sorting:\n");
for (i = 0; i < n; i++)
printf("%d\t", a);
printf("\n");
return 0;
}
页:
[1]