【希尔排序】数据结构实验之排序六：希尔排序

- 日理万妓 2022-06-03 05:13 233阅读 0赞

Think:  
1知识点：希尔排序  
2希尔排序基本思想(分组插入)：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 < d1重复上述的分组和排序，直至所取的增量dk = 1(dk < d(k-1)… < d2 < d1)，即所有记录放在同一组中进行直接插入排序为止[——参考自【百度百科】][Link 1]  
3算法理解：  
![SouthEast][][——参考自【常用算法—OC希尔排序(二)】][OC]

数据结构实验之排序六：希尔排序  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
我们已经学习了各种排序方法，知道在不同的情况下要选择不同的排序算法，以期达到最好的排序效率；对于待排序数据来说，若数据基本有序且记录较少时， 直接插入排序的效率是非常好的，希尔排序就是针对一组基本有序的少量数据记录进行排序的高效算法。你的任务是对于给定的数据进行希尔排序，其中增量dk=n/(2^k)(k=1,2,3……)

Input  
连续输入多组数据，每组输入数据的第一行给出一个正整数N(N <= 10000)，随后连续给出N个整数表示待排序关键字，数字间以空格分隔。

Output  
输出dk=n/2和dk=1时的结果。

Example Input  
10  
10 9 8 7 6 5 4 3 2 1  
10  
\-5 9 7 -11 37 -22 99 288 33 66

Example Output  
5 4 3 2 1 10 9 8 7 6  
1 2 3 4 5 6 7 8 9 10  
\-22 9 7 -11 37 -5 99 288 33 66  
\-22 -11 -5 7 9 33 37 66 99 288

Hint

Author  
xam

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int rec[14014];
    
    void shell_sort(int n, int dx);
    void pri_rec(int n);
    
    int main(){
        int n, i, dx;
        while(~scanf("%d", &n)){
            for(i = 1; i <= n; i++)
                scanf("%d", &rec[i]);
            for(i = 2; i <= n; i <<= 1){
                dx = n/i;
                shell_sort(n, dx);
                if(dx == n/2 || dx == 1) pri_rec(n);
            }
        }
        return 0;
    }
    void pri_rec(int n){
        for(int i = 1; i <= n; i++)
            printf("%d%c", rec[i], i == n? '\n': ' ');
        return;
    }
    void shell_sort(int n, int dx){
        int i, j;
        for(i = dx+1; i <= n; i++){
            if(rec[i] < rec[i-dx]){
                rec[0] = rec[i];
                for(j = i-dx; j > 0 && rec[j] > rec[0]; j -= dx){
                    rec[j+dx] = rec[j];
                }
                rec[j+dx] = rec[0];
            }
        }
        return;
    }

[Link 1]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin
[SouthEast]: /images/20220603/2cf44afdee484824babc7683d6eed101.png
[OC]: http://www.jianshu.com/p/4bad71cc50c7