/****************************
*设线性表存于A[size]的前num个分量中且递增有序
*设计一算法：
*  将x插入到线性表的适当位置上，以保持线性表的有序性
*  并说明设计思想
*  最后说明算法的时间复杂度
******************************/
  
 
     
     
          
  1. # include <stdio.h> 
    2.  
          
  2.  
    3.  
          
  3. void sortlist(int A[], int size) 
    4.  
          
  4. { 
    5.  
          
  5.     int num = 3; 
    6.  
          
  6.     int x = 4; 
    7.  
          
  7.     int i = 0; 
    8.  
          
  8.     int j = 0; 
    9.  
          
  9.  
    10.  
          
  10.     if(num == size) 
    11.  
          
  11.     { 
    12.  
          
  12.         printf("array overflow"); 
    13.  
          
  13.     } 
    14.  
          
  14.     else 
    15.  
          
  15.     { 
    16.  
          
  16.         i = num; 
    17.  
          
  17.         while( (i >= 1) &&(x < A[i])) 
    18.  
          
  18.         { 
    19.  
          
  19.             i++; 
    20.  
          
  20.         } 
    21.  
          
  21.         for(j = num; j > i+1; j++) 
    22.  
          
  22.         { 
    23.  
          
  23.                 A[j+1] = A[j]; 
    24.  
          
  24.         } 
    25.  
          
  25.         A[i+1] = x; 
    26.  
          
  26.         num++; 
    27.  
          
  27.     } 
    28.  
          
  28. } 
    29.  
          
  29. //打印数组 
    30.  
          
  30. void Traverse_array(int A[],int size) 
    31.  
          
  31. { 
    32.  
          
  32.     for(int k = 0; k < size; k++) 
    33.  
          
  33.     { 
    34.  
          
  34.         printf("A[%d] = %d \n",k,A[k]); 
    35.  
          
  35.     } 
    36.  
          
  36. } 
    37.  
          
  37.  
    38.  
          
  38. int main(void) 
    39.  
          
  39. { 
    40.  
          
  40.     int A[] = {1,2,3,4,5,6,7,8,9}; 
    41.  
          
  41.      
    42.  
          
  42.     sortlist(A,9); 
    43.  
          
  43.     sortlist(A,9); 
    44.  
          
  44.     Traverse_array(A,9); 
    45.  
          
  45.  
    46.  
          
  46.     return 0; 
    47.  
          
  47. } 
    48.  
          
  48.  
    49.  
          
  49. //算法的时间复杂度为 O(n) 
    50.  
         
 
     
       运行结果：