希尔排序
2020-06-21
思想 #
- 先将整个待排序列中的记录按照指定的下标进行分组，并对每个组内的记录采用直接插入法排序
- 然后依次减少下标量，即使每组包含的记录增多，再继续对每组组内的记录采用直接插入法排序
- 依此类推，当下标增量减少到1时，整个待排序记录序列已成为一组，但由于此前所做的直接插入排序工作，整个待排序记录序列已经基本有序，最终完成了排序
代码实现 #
for(int dk=n.length/2;dk>=1;dk=dk/2){ //增量因子
for(int i=dk;i<n.length;i++){ //下面的代码类似插入排序
if(n[i]<n[i-dk]){
int temp=n[i];
int j;
//比temp大的往后挪，直到遇到比temp更小的
for(j=i-dk;j>=0&&temp<n[j];j=j-dk)
n[j+dk]=n[j];
n[j+dk]=temp;//将temp放在停的位置上
}
}
}
复杂度 #
时间复杂度：O(n²)
空间复杂度：O(1)
不稳定的排序算法