如果您查看阵列并对位置进行编号
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
30 20 29 19 28 18 27 17 26 16 25 15 24 14 23 13 22 12 21 11
在 shell 排序中,您所做的是以跳过编号(在您的情况下为 3)开始,因此要制作第一个“列表”,您需要一个数字并跳过。对于 3,这将是第 1、第 4、第 7 等。
所以你会有一个列表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
30 19 27 16 24 13 21
和第二个清单
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 28 17 25 14 22 11
第三个列表是剩余的项目。
对于下一轮,您可以少做一个……所以奇数位置的项目和偶数位置的项目。
回应下面的评论
Shell 排序是一种就地排序——这意味着您不会将项目删除到新列表或创建任何新数据结构。您正在使用数组来“处理”在数组位置方面“相距很远”的项目彼此相邻。您实际上并没有创建新列表或新数组(这就是我展示图表的原因);你只要看看这些位置。
为什么?
因为这意味着当您开始时(例如从 3 开始),您将把东西移动得更远)——例如,从位置 16 开始的 13 在第一遍中被移动到位置 1。然后,随着您减少数量,您开始进行更多的本地更改。这意味着您比典型的冒泡排序获得了优势。仍然不好 - 但比冒泡排序要好得多。