您现在的位置是:首页 >技术教程 >希尔排序(C++)网站首页技术教程
希尔排序(C++)
简介希尔排序(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)
稳定性
排序过程中会交换元素位置,所以不是稳定的。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。