shell排序有问题阿 !

wuhu

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int iList[10]={30,80,68,43,70,90,45,51,25,100};
   
5. int iSize = 10;
   
6. int iGap=iSize/2;
   
7. int iTemp;
   
8. int iSwap;
   
9. int
   
10. main(void)
    
11. {   
    
12.     while( iGap > 0)
    
13.     {
    
14.                 for (int iSub = 0; iSub < iSize-iGap; iSub++)
    
15.                 {
    
16.                       if (iList[iSub] > iList[iSub+iGap])
    
17.                       {
    
18.                            iTemp = iList[iSub];
    
19.                            iList[iSub] = iList[iSub+iGap];
    
20.                            iList[iSub+iGap] = iTemp;
    
21.    
    
22.                       }
    
23.                }
    
24.           iGap=iGap/2;
    
25.           printf("iGap is %d\n", iGap);
    
26.         
    
27.     }
    
28.     printf("list1 is %d\n", iList[1]);   
    
29.     for (int i = 0; i < 10; i++)
    
30.     printf("new list is :%d\n", iList[i]);
    
31.     getchar();
    
32. }
    

复制代码

我写的一个shell排序，怎么出来的结果不对啊，不全是从小到大的，中间有几个数字错了！还是我写错了？

masterdemon

Shell排序这种经典算法不可能有错。如果你结果不对是对程序写错了。

masterdemon

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int iList[10]={30,80,68,43,70,90,45,51,25,100};
   
5. int iSize = 10;
   
6. int iGap=iSize/2;
   
7. int iTemp;
   
8. int iSwap;
   
9. 
   
10. void shellSort(int numbers[], int array_size)
    
11. {
    
12.   int i, j, increment, temp;
    
13. 
    
14.   increment = array_size / 2;
    
15.   while (increment > 0)
    
16.   {
    
17.     for (i=0; i < array_size; i++)
    
18.     {
    
19.       j = i;
    
20.       temp = numbers[i];
    
21.       while ((j >= increment) && (numbers[j-increment] > temp))
    
22.       {
    
23.         numbers[j] = numbers[j - increment];
    
24.         j = j - increment;
    
25.       }
    
26.       numbers[j] = temp;
    
27.     }
    
28.     if (increment/2 != 0)
    
29.       increment = increment/2;
    
30.     else if (increment == 1)
    
31.       increment = 0;
    
32.     else
    
33.       increment = 1;
    
34.   }
    
35. }
    
36. 
    
37. int
    
38. main(void)
    
39. {   
    
40.     shellSort( iList, iSize );
    
41.     for (int i = 0; i < 10; i++)
    
42.     printf("new list is :%d\n", iList[i]);
    
43.     getchar();
    
44. }
    

复制代码

这个一定对。

JBug

你的排序中少了最里面小数组的排序, shell的算法
给定数组a[n]

for (gap = n/2; gap > 0; gap /=2)
    for(int i = 0; i < gap; i++)
        Sort 子队列a, a[i + gap], a[i + 2 * gap] ...;