希尔排序（C++）
希尔排序
是插入排序的一种，也是缩小增量排序。希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
代码实现
class Solution {
public:
void ShellSort(vector<int>&nums,int n){
for(int dk=n/2;dk>=1;dk=dk/2){
for(int i=dk;i<n;i++){
if(nums[i]<nums[i-dk]){
int tmp=nums[i];
int j;
for(j=i-dk;j>=0&&tmp<nums[j];j-=dk){
nums[j+dk]=nums[j];
}
nums[j+dk]=tmp;
}
}
}
}
vector<int> sortArray(vector<int>& nums) {
ShellSort(nums,nums.size());
return nums;
}
};
运行结果
时空复杂度和稳定性
时间复杂度
最好情况
最好情况和步长是有关系的，但是目前还不能确定最合适的步长是多少
最坏情况
O ( n l o g n ) O(nlogn) O(nlogn)
###空间复杂度
O
(
1
)
O(1)
O(1)
稳定性
排序过程中会交换元素位置，所以不是稳定的。