[已解决]哪位大佬可以帮忙解释一下，感激（明天考试）急

我是个汉子

将互不相同元素的升序排列，重新存入数组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[mid]>=a[i]) high=mid-1;
            else  low=mid+1;
        }
        if(low>=k||a[low]!=a[i])
        { 
/*******************FOUND*******************/
            t=a[i];
/*******************FOUND*******************/ 
            for(j=k-1;j>=low;j--)
                a[j+1]=a[j];
            a[low]=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[i]);
/*******************FOUND*******************/
    n=sort(a,n);                    
    printf("\nAfter sorting:\n");
    for(i=0;i<n;i++)
    printf("%d\t",a[i]);
    printf("\n");
    return 0;
}

最佳答案

月排行榜 / 总排行榜

Croper

2019-3-1 20:47:54

思路是从第二个数开始使用二分查找法，然后把元素插入找到的位置，时间复杂度应该是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[i]
                {
                        mid = (low + high) / 2;
                        if (a[mid] >= a[i]) high = mid - 1;
                        else  low = mid + 1;
                }                      //返回时，low==high+1。low的为第一个大于等于a[i]的位置,height为第一个小于a[i]的位置；
                if (low >= k || a[low] != a[i])        //当a[i]不与排列好的数字重复时
                {
                        /*******************FOUND*******************/
                        t = a[i];
                        /*******************FOUND*******************/
                        for (j = k - 1; j >= low; j--)      //把大于a[i]的元素都向后挪一步 
                                a[j + 1] = a[j];
                        a[low] = t;                          //插入a[i]
                        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[i]);
        /*******************FOUND*******************/
        n = sort(a, n);
        printf("\nAfter sorting:\n");
        for (i = 0; i < n; i++)
                printf("%d\t", a[i]);
        printf("\n");
        return 0;
} 

跳转到最佳答案楼层

Croper

思路是从第二个数开始使用二分查找法，然后把元素插入找到的位置，时间复杂度应该是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[i]
                {
                        mid = (low + high) / 2;
                        if (a[mid] >= a[i]) high = mid - 1;
                        else  low = mid + 1;
                }                      //返回时，low==high+1。low的为第一个大于等于a[i]的位置,height为第一个小于a[i]的位置；
                if (low >= k || a[low] != a[i])        //当a[i]不与排列好的数字重复时
                {
                        /*******************FOUND*******************/
                        t = a[i];
                        /*******************FOUND*******************/
                        for (j = k - 1; j >= low; j--)      //把大于a[i]的元素都向后挪一步 
                                a[j + 1] = a[j];
                        a[low] = t;                          //插入a[i]
                        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[i]);
        /*******************FOUND*******************/
        n = sort(a, n);
        printf("\nAfter sorting:\n");
        for (i = 0; i < n; i++)
                printf("%d\t", a[i]);
        printf("\n");
        return 0;
}