希尔排序

黎子卿

#include <iostream>
using namespace std;
int main()
{
        int arr[10];
        int num;
        for (int i = 0; i < 10; i++)
        {
                cin >> num;
                arr[i] = num;
        }
        for (int gap = sizeof(arr) / 2 / 2; gap > 0; gap/=2)
        {
                for (int j = gap; j >=0; j--)
                {
                        int temp = arr[j];
                        int k;
                        for (k = j+gap; k<sizeof(arr)/2 and temp > arr[k]; k = k+gap)
                        {
                                arr[k-gap] = arr[k];
                        }
                        arr[k] = temp;
                }
        }
        for (int i = 0; i < 10; i++)
        {
                cout << arr[i] << endl;
        }
        return 0;
}这个希尔排序为什么不对

yinda_peng

循环那里有问题，你用j >= 0可能会导致越界，用j >= gap保证arr[j-gap]不会越界；然后就是temp，你的循环条件为temp > arr[k]，当temp小于等于arr[k]时，循环就会结束。应该改为temp < arr[k-gap]。

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.     int arr[10];
   
7.     int num;
   
8.     for (int i = 0; i < 10; i++)
   
9.     {
   
10.         cin >> num;
    
11.         arr[i] = num;
    
12.     }
    
13. 
    
14.     for (int gap = sizeof(arr) / sizeof(arr[0]) / 2; gap > 0; gap /= 2)
    
15.     {
    
16.         for (int j = gap; j < sizeof(arr) / sizeof(arr[0]); j++)
    
17.         {
    
18.             int temp = arr[j];
    
19.             int k;
    
20.             for (k = j; k >= gap && temp < arr[k - gap]; k -= gap)
    
21.             {
    
22.                 arr[k] = arr[k - gap];
    
23.             }
    
24.             arr[k] = temp;
    
25.         }
    
26.     }
    
27. 
    
28.     for (int i = 0; i < 10; i++)
    
29.     {
    
30.         cout << arr[i] << endl;
    
31.     }
    
32. 
    
33.     return 0;
    
34. }

复制代码

yinda_peng

如果是逆序，就修改temp<arr[k-gap]为大于就可以

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.     int arr[10];
   
7.     int num;
   
8.     for (int i = 0; i < 10; i++)
   
9.     {
   
10.         cin >> num;
    
11.         arr[i] = num;
    
12.     }
    
13. 
    
14.     for (int gap = sizeof(arr) / sizeof(arr[0]) / 2; gap > 0; gap /= 2)
    
15.     {
    
16.         for (int j = gap; j < sizeof(arr) / sizeof(arr[0]); j++)
    
17.         {
    
18.             int temp = arr[j];
    
19.             int k;
    
20.             for (k = j; k >= gap && temp > arr[k - gap]; k -= gap)
    
21.             {
    
22.                 arr[k] = arr[k - gap];
    
23.             }
    
24.             arr[k] = temp;
    
25.         }
    
26.     }
    
27. 
    
28.     for (int i = 9; i >= 0; i--)
    
29.     {
    
30.         cout << arr[i] << endl;
    
31.     }
    
32. 
    
33.     return 0;
    
34. }
    

复制代码