在一个有序数列中插入一个任意数；阵列仍然保持有序，并输出。

seablue

练习题：
ver0.3 改进了一下，增加了通用性

1. 
   
2. /* 在一个有序数列中插入一个任意数；要求插入后
   
3. * 阵列仍然保持有序，并输出。
   
4. * 阵列如：0, 1, 2, 3, 5, 6, 7, 8, 9
   
5. *     Copyright seablue at linuxsir.cn
   
6. *          Version 0.3.0
   
7. *           2004-05-21
   
8. */
   
9. #include <stdio.h>
   
10. void insort(x,l,n)
    
11. int l,x[],n;
    
12. { int i,k;
    
13.         /* l为数组总长度，n是数组实际长度；
    
14.          * 如果数组没有多余空间，给出警告信息。
    
15.          */
    
16.         if (l <= n) printf("\nArray full!\n");
    
17.         else
    
18.                                 /* 输入一个任意数。
    
19.                                  */
    
20.         { printf("\nPlease input the value for inserting:\n");
    
21.                 scanf("%d",&k);
    
22. 
    
23.         /*
    
24.          * 找到输入的数k的合适位置，并把大于k的数向右移动一个位置。
    
25.          */
    
26. 
    
27.                 for (i = n-1; (i >= 0)&&(k < x[i]); i--)
    
28.                                 x[i+1]=x[i];
    
29.                 x[i+1]=k;
    
30. 
    
31. 
    
32.         /*
    
33.          * 打印插入后的有序数列。
    
34.          */
    
35. 
    
36.          for (i = 0; i < (n+1); i++)
    
37.                          printf("%d ",x[i]);
    
38.                          printf("\n");
    
39.         }
    
40. }
    
41. 
    
42. main()
    
43. { int a[10] = { 0, 1, 2, 3, 5, 6, 7, 8, 9 };
    
44. 
    
45.         /*
    
46.          * insort()自定义函数的用法，调用。
    
47.          * insort(array_name, length_of_array_defined, length_of_array_used)
    
48.          */
    
49. 
    
50.         insort(a,10,9);
    
51. }
    

复制代码

home_king

很简单的也很经典的C语言专业课练习题。

home_king

采用优化的查找算法——斐波那契算法来解决此类插值问题试试看。

seablue

:thank
我正参考C手册第五版，上面提到KS算法的改进版可以达到O(n的1.25次方)
你说的是这个吗？

摘录引人gap的Knuth和Sedgewich的shell改进版排序算法函数，供参考
（不会有版权问题吧？）：

1. 
   
2. void shellsort(register int v[], int n)
   
3. {
   
4.         registor int gap, i, j, temp;
   
5.         gap = 1;
   
6.         do (gap = 3*gap + 1); while (gap <= n);
   
7.         for (gap /= 3; gap > 0; gap /= 3)
   
8.             for (i = gap; i< n; i++) {
   
9.                 temp = v[i];
   
10.                 for (j = i-gam; (j >= 0)&&(v[j] > temp); j-=gap)
    
11.                     v[j+gap] = v[j];
    
12.                 v[j+gap] = temp;
    
13.             }
    
14. }
    

复制代码

home_king

试试看啊。

seablue

看看是否是楼上的那个？

home_king

看得头都晕了，我指的不是这个，你把这个算法描述一下吧。
还有，shell改进算法？什么意思？

seablue

:sorry我看了5遍了，也是没看明白:p
是个shell程序吧「函数」

把手册的内容给你抄下来

是Kernighan和Ritchie著作《C编程语言》中的shell排序例子的改进，改进的三个地方：

1）gap初始化时寻找不大于n的序列（1、4、13、40、121、。。。）中的最小值，每次遍历外循环时除以3。这样可以使排序加快20％-30％（这样选择gap作为初始值比用n更合适）。

2）内循环中的赋值次数从3次减少到一次。

3）增加了register和void存储类。可以大大提高性能。