Shell排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL. Shell 于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

程序实现

• Python

def shell_sort(nums):
    gap = len(nums)//2
    while gap >0:
        for i in range(gap,len(nums),gap):
            for j in range(i,gap-1,-gap):
                if nums[j] < nums[j-gap]:
                    nums[j],nums[j-gap] = nums[j-gap],nums[j]
                else:
                    break
        gap = gap//2
    return nums

• C++

void shell_sort(int nums[],int n){
    int gap = n/2;
    while (gap){
        for (int i=gap;i<n;i+=gap){
            for (int j=i;j>gap-1;j-=gap){
                if (nums[j]<nums[j-gap]){
                    swap(nums[j],nums[j-gap]);
                }
                else{
                    break;
                }
            }
        }
        gap = gap/2;
    }
}

复杂度和稳定性

• 时间复杂度为：O(n^1.3 )，最坏时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定