希尔排序问题：gap=1时第二个C#版本失效的原因及相关疑问

第一个版本无需重复gap=1排序的原因 #

当gap=1时，第一个版本的逻辑就是标准直接插入排序：

• 从数组第2个元素（i=gap=1）开始，保存当前元素temp，然后向前遍历已排序的前半部分（j=i-gap）；
• 只要前面的元素比temp大，就将其向后移动gap位（此时为1位），直到找到合适的插入位置，再把temp放入；
• 每处理完一个元素，前面的子数组都会保持有序，遍历完所有元素后，整个数组自然完成排序，因此不需要重复执行gap=1的循环。

第二个版本排序卡住的问题 #

第二个版本的遍历逻辑完全错误：

• 它从数组第1个元素（i=0）开始，保存temp=int_array[i]，然后向后（j=i+gap）寻找比temp小的元素，将这些元素向前移动gap位，最后把temp放到j-gap的位置；
• 当gap=1时，这种逻辑并非标准插入排序，无法保证前面的子数组有序，一次遍历只能移动部分元素，无法完成全数组排序。比如数组[3,2,1]，经过一次gap=1遍历后会变成[2,1,3]，并未完全排好，但代码只执行一次gap=1循环，因此出现“卡住”的情况。

关于你参考的回答说明 #

你看到的“gap=1时需重复排序直到无交换”的结论，针对的是用冒泡逻辑实现的希尔排序（比如每个gap组内用冒泡排序）。而你的第一个版本是用插入排序逻辑实现的，当gap=1时就是标准插入排序，一次遍历即可完成排序，因此不需要重复。

内容的提问来源于stack exchange，提问作者Emanul Yang