您现在的位置是:首页 >技术教程 >希尔排序(C++)网站首页技术教程

希尔排序(C++)

qaaaaaaz 2023-07-07 00:00:03
简介希尔排序(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)

稳定性

排序过程中会交换元素位置,所以不是稳定的。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。