希尔排序

黎子卿

#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]。

#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) / sizeof(arr[0]) / 2; gap > 0; gap /= 2)
    {
        for (int j = gap; j < sizeof(arr) / sizeof(arr[0]); j++)
        {
            int temp = arr[j];
            int k;
            for (k = j; k >= gap && temp < arr[k - gap]; k -= gap)
            {
                arr[k] = arr[k - gap];
            }
            arr[k] = temp;
        }
    }

    for (int i = 0; i < 10; i++)
    {
        cout << arr[i] << endl;
    }

    return 0;
}

yinda_peng

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

#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) / sizeof(arr[0]) / 2; gap > 0; gap /= 2)
    {
        for (int j = gap; j < sizeof(arr) / sizeof(arr[0]); j++)
        {
            int temp = arr[j];
            int k;
            for (k = j; k >= gap && temp > arr[k - gap]; k -= gap)
            {
                arr[k] = arr[k - gap];
            }
            arr[k] = temp;
        }
    }

    for (int i = 9; i >= 0; i--)
    {
        cout << arr[i] << endl;
    }

    return 0;
}