P1177

PengDave · 2023-12-11 13:05:52 · 题解

发现竟然十大排序中题解没有希尔排序，于是写了一篇

首先简单介绍一下希尔排序 希尔排序对不相邻的元素进行比较和移动：

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2. 对这些子序列进行插入排序；
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。

希尔排序一般能够达到 O(n\log_{2}{n} ) 的时间复杂度，最坏 O(n\log^{2}{n}) ，虽然不如快排，但比插入排序好多了，能过这道题

举个例子

3 5 1 2 4 7 8 6

设比较元素间距为 gap

1.将第1、5个，2、6个，3、7个，4、8个分别插入排序 gap 为4

3 5 1 2 4 7 8 6

2.将第1、3、5、7个，2、4、6、8个分别插入排序 gap 为2

1 2 3 5 4 6 8 7

3.将1~8个插入排序 gap 为1

1 2 3 4 5 6 7 8

话不多说，代码：

#include<bits/stdc++.h>
using namespace std;
int a[100100];
//希尔排序函数
void shellsort(int a[],int len){
    for(int gap=len/2;gap>0;gap/=2){
        //插入排序 不过是把距离改为gap，其他的没变
        for(int i=gap+1;i<=len;i++){
            int j=i-gap;
            while(j>=1&&a[j]>a[j+gap]){
                swap(a[j],a[j+gap]);
                j-=gap;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    shellsort(a,n);
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}