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

我是个汉子

将互不相同元素的升序排列，重新存入数组a中，返回升序排列后互不相同元素的个数。

1. 
   
2. 
   
3. #include <stdio.h>
   
4. int sort(int a[],int n)
   
5. {
   
6.     int i,j,k,low,high,mid,t;
   
7.     for(k=i=1;i<n;i++)
   
8.     {
   
9.         low=0;
   
10.         high=k-1;
    
11.         while(low<=high)
    
12.         {
    
13.             mid=(low+high)/2;
    
14.             if(a[mid]>=a[i]) high=mid-1;
    
15.             else  low=mid+1;
    
16.         }
    
17.         if(low>=k||a[low]!=a[i])
    
18.         {
    
19. /*******************FOUND*******************/
    
20.             t=a[i];
    
21. /*******************FOUND*******************/
    
22.             for(j=k-1;j>=low;j--)
    
23.                 a[j+1]=a[j];
    
24.             a[low]=t;
    
25.             k++;
    
26.         }
    
27.     }
    
28.     return k;  
    
29. }
    
30. int main()
    
31. {
    
32.     int a[ ]={6,2,7,5,4,3,4,6,5,4};
    
33.     int i,n;
    
34.     n=sizeof(a)/sizeof(int);
    
35.     for(i=0;i<n;i++)
    
36.         printf("%d\t",a[i]);
    
37. /*******************FOUND*******************/
    
38.     n=sort(a,n);                    
    
39.     printf("\nAfter sorting:\n");
    
40.     for(i=0;i<n;i++)
    
41.     printf("%d\t",a[i]);
    
42.     printf("\n");
    
43.     return 0;
    
44. }

复制代码

最佳答案

月排行榜 / 总排行榜

Croper

2019-3-1 20:47:54

思路是从第二个数开始使用二分查找法，然后把元素插入找到的位置，时间复杂度应该是O(nlogn)

1. #include <stdio.h>
   
2. int sort(int a[], int n)
   
3. {
   
4.         int i, j, k, low, high, mid, t;
   
5.         for (k = i = 1; i < n; i++)
   
6.         {
   
7.                 low = 0;
   
8.                 high = k - 1;
   
9.                 while (low <= high)    //二分查找，现在前k个数已经排序完毕，需要插入一个数a[i]
   
10.                 {
    
11.                         mid = (low + high) / 2;
    
12.                         if (a[mid] >= a[i]) high = mid - 1;
    
13.                         else  low = mid + 1;
    
14.                 }                      //返回时，low==high+1。low的为第一个大于等于a[i]的位置,height为第一个小于a[i]的位置；
    
15.                 if (low >= k || a[low] != a[i])        //当a[i]不与排列好的数字重复时
    
16.                 {
    
17.                         /*******************FOUND*******************/
    
18.                         t = a[i];
    
19.                         /*******************FOUND*******************/
    
20.                         for (j = k - 1; j >= low; j--)      //把大于a[i]的元素都向后挪一步
    
21.                                 a[j + 1] = a[j];
    
22.                         a[low] = t;                          //插入a[i]
    
23.                         k++;                               //现在有k+1个元素排列好了
    
24.                 }
    
25.         }
    
26.         return k;
    
27. }
    
28. int main()
    
29. {
    
30.         int a[] = { 6,2,7,5,4,3,4,6,5,4 };
    
31.         int i, n;
    
32.         n = sizeof(a) / sizeof(int);
    
33.         for (i = 0; i < n; i++)
    
34.                 printf("%d\t", a[i]);
    
35.         /*******************FOUND*******************/
    
36.         n = sort(a, n);
    
37.         printf("\nAfter sorting:\n");
    
38.         for (i = 0; i < n; i++)
    
39.                 printf("%d\t", a[i]);
    
40.         printf("\n");
    
41.         return 0;
    
42. }

复制代码

跳转到最佳答案楼层

Croper

思路是从第二个数开始使用二分查找法，然后把元素插入找到的位置，时间复杂度应该是O(nlogn)

1. #include <stdio.h>
   
2. int sort(int a[], int n)
   
3. {
   
4.         int i, j, k, low, high, mid, t;
   
5.         for (k = i = 1; i < n; i++)
   
6.         {
   
7.                 low = 0;
   
8.                 high = k - 1;
   
9.                 while (low <= high)    //二分查找，现在前k个数已经排序完毕，需要插入一个数a[i]
   
10.                 {
    
11.                         mid = (low + high) / 2;
    
12.                         if (a[mid] >= a[i]) high = mid - 1;
    
13.                         else  low = mid + 1;
    
14.                 }                      //返回时，low==high+1。low的为第一个大于等于a[i]的位置,height为第一个小于a[i]的位置；
    
15.                 if (low >= k || a[low] != a[i])        //当a[i]不与排列好的数字重复时
    
16.                 {
    
17.                         /*******************FOUND*******************/
    
18.                         t = a[i];
    
19.                         /*******************FOUND*******************/
    
20.                         for (j = k - 1; j >= low; j--)      //把大于a[i]的元素都向后挪一步
    
21.                                 a[j + 1] = a[j];
    
22.                         a[low] = t;                          //插入a[i]
    
23.                         k++;                               //现在有k+1个元素排列好了
    
24.                 }
    
25.         }
    
26.         return k;
    
27. }
    
28. int main()
    
29. {
    
30.         int a[] = { 6,2,7,5,4,3,4,6,5,4 };
    
31.         int i, n;
    
32.         n = sizeof(a) / sizeof(int);
    
33.         for (i = 0; i < n; i++)
    
34.                 printf("%d\t", a[i]);
    
35.         /*******************FOUND*******************/
    
36.         n = sort(a, n);
    
37.         printf("\nAfter sorting:\n");
    
38.         for (i = 0; i < n; i++)
    
39.                 printf("%d\t", a[i]);
    
40.         printf("\n");
    
41.         return 0;
    
42. }

复制代码