希尔排序

黎子卿

#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 i = sizeof(arr) / 4 / 2; i > 0; i = i / 2)
        {
                for (int j = i; j < 10; j++)
                {
                        int temp = arr[j];
                        int index;
                        bool flag = false;
                        for (int k = j-i; k > 0; k = k - i)
                        {
                                if (arr[k] > arr[k-j])
                                {
                                        arr[k] = arr[k - i];
                                }
                                else
                                {
                                        index = k - i;
                                        flag = true;
                                        break;
                                }
                        }
                        if (flag)
                        {
                                arr[index] = temp;
                        }
                }
        }
        for (int i = 0; i < 10; i++)
        {
                cout << arr[i] << endl;
        }
        return 0;
}
这个希尔排序怎么不对啊
而且会报错

isdkz

这段代码中的希尔排序实现有一些问题。首先，希尔排序的核心思想是将数组分成若干个子序列，分别进行插入排序，然后逐渐缩小增量直至为1，最终对整个数组进行一次插入排序。而你的代码中并没有按照这一思路来实现希尔排序。

此外，代码中的一些变量命名和逻辑也存在问题，导致了程序报错和排序结果不正确。

以下是经过修正的希尔排序的示例代码：

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

复制代码

这段修正后的代码中，shellSort函数实现了希尔排序的核心逻辑，而且变量命名和逻辑更加清晰。在主函数中，我们输入数组后调用shellSort函数进行排序，然后输出排序结果。

Mike_python小

这段代码存在以下几个问题：

1. 希尔排序的增量序列选取不当，可能会导致算法效率较低。实际上，希尔排序的增量序列有很多种，选取不同的增量序列可能会得到不同的排序效果。

2. 内部的插入排序实现有误，导致排序结果错误。具体来说，内部排序的时候应该将当前元素与已排好序的序列中的元素进行比较，而不是与数组中前一个元素比较。

3. 程序中存在一些语法错误，如循环条件不正确、变量名重复等。

下面是修改后的代码：

1. ++
2. #include <iostream>
3. using namespace std;
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) / 4 / 2; gap > 0; gap /= 2)
15.     {
16.         for (int i = gap; i < 10; i++)
17.         {
18.             int temp = arr[i];
19.             int j;
20.             for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
21.             {
22.                 arr[j] = arr[j - gap];
23.             }
24.             arr[j] = temp;
25.         }
26.     }
27.     for (int i = 0; i < 10; i++)
28.     {
29.         cout << arr[i] << endl;
30.     }
31.     return 0;
32. }

复制代码

修改后的代码中，我们选取了希尔排序的一个常用增量序列：$n/2$，$n/4$，$n/8$，...，$1$。内部排序使用了插入排序算法，并且将数组元素与已排好序的序列中的元素进行比较。同时，我们也修正了一些语法错误，使得程序能够正确运行。

ba21

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.         int arr[11] = {8, 11, 2, 3, 9, 7, 4, 6, 10, 1, 5};
   
7.         int i, j, gap, len, end, tmp;
   
8. 
   
9.         len = sizeof(arr) / sizeof(int);
   
10.         for (gap=len/2; gap>0; gap/=2) // 计算出组数
    
11.         {
    
12.                 for (i=0; i<gap; i++) // 遍历每组
    
13.                 {
    
14.                         // 使用直接排序法对每组数据进行排序
    
15.                         for (end=i+gap; end<len; end+=gap)
    
16.                         {
    
17.                                 if(arr[end-gap]>arr[end])
    
18.                                 {
    
19.                                         tmp = arr[end];
    
20.                                         for(j=end-gap; arr[j]>tmp && j+gap!=i; j-=gap) // 在直接排序的基础上加上 起始位置 j+gap!=i
    
21.                                         {
    
22.                                                 arr[j+gap] = arr[j];
    
23.                                         }
    
24.                                         arr[j+gap] = tmp;
    
25.                                 }
    
26.                         }
    
27.                 }
    
28.         }
    
29. 
    
30. 
    
31.         for (i=0; i<len; i++)
    
32.         {
    
33.                 cout << arr[i] << endl;
    
34.         }
    
35.         return 0;
    
36. }
    

复制代码