我的希尔排序前两个数据顺序偶尔有问题，但我没找到问题啊

Question

template
void ShellSort(T arr[],int n) {
int i,index;
int interval=n/2;
while(interval>0) {
for(i=0; i<n-interval; i++) {
for(index=i; index+interval<n; index+=interval) {
if(arr[index]>arr[index+interval]) {
swap(arr[index],arr[index+interval]);
}
}

	}
	interval/=2;
}

}

Answer 1

liuyubobobo 2019-01-17 14:29:36

你的内层循环不是插入排序，而是冒泡排序：）

我在课程的补充代码中提供了一个希尔排序的源码，有兴趣可以参考：）

传送门：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-03-ShellSort-MergeSort-and-QuickSort-Comparision/ShellSort.h

加油：）

• 提问者 慕UI4716311 #1

  谢谢老师，我看了您的代码，您用了那个更优的插入排序，为什么性能可以这么好，我测试的时候记得是到1000万的数据量也才很短的时间。

• liuyubobobo 回复 提问者 慕UI4716311 #2

  希尔排序就是这么快。你的思路也不会太慢。如果使用VS的话，要使用release模式进行性能测试哦：）

• 提问者 慕UI4716311 回复 liuyubobobo #3

  我用的dev，不过下载您的代码会注释乱码，所以我准备下载一个clion

点开查看后面5条评论