Блог

Мой ответ был:

Сортировка оболочки делает избыточное сравнение, потому что, если во время сравнения для элементов, находящихся далеко друг от друга (когда h находится рядом 8 ), он сравнивает два элемента, которые будут соседними, а затем будет сравнивать один и тот же элемент снова, когда во время сравнения для элемента рядом друг с другом (когда h находится рядом 1 ). Например, если список 113 400 818 612 112 311 412 429 , когда h = 4 , он будет сравнивать 113 и 112 , и когда h = 1 , он будет сравнивать 113 и 112 снова, поскольку он будет сравнивать элементы, которые находятся ближе всего друг к другу.

Правильный ли мой ответ?

Ваш пример определенно тот, где происходит избыточность. На самом деле, избыточности нельзя избежать при сортировке оболочки. Как вы заметили, когда h = 1, он всегда сравнивает то, что сравнивалось в предыдущих препроцессах. Одна вещь, которую вы можете сделать, чтобы повысить производительность сортировки оболочки (т. Е. Уменьшить избыточные сравнения), — это разумно выбирать h. Например, если вы выбираете h равным 4, 2, 1, то 113 и 112 должны сравниваться три раза, а если вы выбираете h равным 5, 3, 1, избыточные сравнения значительно сокращаются. Общее правило выбора h — это не выбирать степени 2 и не выбирать кратные друг другу. Надеюсь, это поможет.