冒泡排序中，为什么正反序排列中，循环次数会不同呢？ 求指导~~~

小飞侠

问题在代码的注释里（望大家帮助，很费解~~）;

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. void sort(int a[],int n, char style);
   
5. 
   
6. int main()
   
7. {
   
8. int a[60] , i , count = 0 , number = 0;
   
9. char style ;
   
10. 
    
11. printf("\n请输入有多少人数(number<60):\n");
    
12. scanf("%d" , &number);
    
13. 
    
14. printf("\n请输入学生的分数 :\n");
    
15. for(i = 0 ; i < number ; i++)
    
16. scanf("%d" , &a[i]);
    
17. 
    
18. printf("\n请问你希望怎样对成绩进行排列(a:升序 / d:降序):\n");
    
19. scanf(" %c" , &style);//注意" %c" %c前得空格;
    
20. 
    
21. sort(a , number , style);
    
22. 
    
23. for(i = 0 ; i < number ; i++)
    
24. {
    
25. printf("%4d" , a[i]);
    
26. }
    
27. printf("\n");
    
28. 
    
29. system("pause");
    
30. }
    
31. 
    
32. void sort(int a[] , int n , char style)
    
33. {
    
34. void ascending(int *p , int n);
    
35. void descending(int *p , int n);
    
36. 
    
37. 
    
38. if('d' == style)
    
39. {
    
40. descending(a , n);
    
41. }
    
42. 
    
43. else
    
44. if('a' == style)
    
45. {
    
46. ascending(a , n);
    
47. }
    
48. 
    
49. else
    
50. {
    
51. printf("\n输入有误!!!....\n");
    
52. }
    
53. }
    
54. 
    
55. void ascending(int *p , int n)
    
56. {
    
57. int i , j , temp;
    
58. 
    
59. printf("\n好的!我们将按照 升序 将成绩进行排列:\n");
    
60. 
    
61. for(i = 0 ; i < n ; i++)
    
62. {
    
63. for(j = 0 ; j < n-i-1 ; j++) //注意这里的j < n-i-1;只有这种情况是可行的;
    
64. {
    
65. if(*(p+j) > *(p+j+1))
    
66. {
    
67. temp = *(p+j);
    
68. *(p+j) = *(p+j+1);
    
69. *(p+j+1) = temp;
    
70. }
    
71. }
    
72. }
    
73. }
    
74. 
    
75. void descending(int *p , int n)
    
76. {
    
77. int i , j , temp;
    
78. printf("\n好的我们将按照 降序 将成绩进行排列:\n");
    
79. 
    
80. for(i = 0 ; i < n ; i++)
    
81. {
    
82. for(j = 0 ; j <= n-i ; j++)//你会发现以下两种情况都是可行的:j<n-i & j<=n-i; 误解中求解答;
    
83. {
    
84. if(*(p+j) < *(p+j+1))
    
85. {
    
86. temp = *(p+j);
    
87. *(p+j) = *(p+j+1);
    
88. *(p+j+1) = temp;
    
89. }
    
90. }
    
91. }
    
92. }

复制代码

liao4155289

冒泡排序实际就是每一次把最小的放在追后面。
比如说有4个数，a[0],a[1],a[2],a[3]，n=4
第一次i=0,n-i = 4 ，即把前面4个数中最小的放在最后面。
在这次循环中（即i=0这个循环），最后一次比较应该是 a[2]和a[3]，此时的j=n-i-1-1 = 2 也就是 j<n-i-1（而不是j<n-i,j<=n-i）

第二次i=1,n-i =3,    即把前面3个数中最小的放在最后面，即选出第二小的数放在a[2]（因为a[3]已经是四个数中最小的了）
这个循环中，最后一次比较的应该是a[1]和a[2],    j=n-i-1  -1 = 1 , 也就是 j<n-i-1（而不是j<n-i,j<=n-i）


依次类推

所以只有  j<n-i-1 是对的。 而 j<n-i不行，因为 在第一次循环中，会访问到a[4],由于a[4]是一个不确定的值，通常是一个很小的负数。
所以就算  你写的是 j<n-i，  a[3]也会大于 a[4]，同样不会交换它们的值。所以尽管写的是 j < i-1 & j<= i -1，在降序排序中结果是一样的。但是在升序中就不对了。你可以自己试试看

小飞侠

liao4155289 发表于 2011-6-19 18:32

                               
登录/注册后可看大图

冒泡排序实际就是每一次把最小的放在追后面。
比如说有4个数，a[0],a[1],a[2],a[3]，n=4
第一次i=0,n-i = ...

谢谢回答，我好好研究下~~  祝开心快乐！！