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

Problem Description

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

Input

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

Output

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

Sample Input

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

Sample 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

我们先来看希尔排序：
参考：https://www.cnblogs.com/chengxiao/p/6104371.html

 void shellsort(int arr[],int len){
    for(int gap=len/2;gap>=1;gap/=2){
        for(int i=gap;i<len;i++){
            int j=i;
            while(j-gap>=0&&arr[j]<arr[j-gap]){                 
                swap(arr[j],arr[j-gap]);
                j-=gap;
             }
         }
 }
}

题破：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
int a[10000];
int b[10000];
using namespace std;
void shellsort(int arr[],int gap,int len);
 int main(){
    int t;
    while(cin>>t){
        for(int i=0;i<t;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<t;i++)
            b[i]=a[i];
        shellsort(a,t/2,t);
        shellsort(b,1,t);
        for(int i=0;i<t;i++){
            if(i==t-1)
                printf("%d\n",a[i]);
            else
            printf("%d ",a[i]);     
        }       
        
        for(int i=0;i<t;i++){       
         if(i==t-1)
            printf("%d\n",b[i]);
        else 
            printf("%d ",b[i]); 
        } 
                                
    }
 }
 //这是一个为了应付题目希尔排序，不是正规的 
 void shellsort(int arr[],int gap,int len){
        for(int i=gap;i<len;i++){
            int j=i;
            while(j-gap>=0&&arr[j]<arr[j-gap]){                 
                swap(arr[j],arr[j-gap]);
                j-=gap;
             }
         }
 }
 

/***************************************************
User name: lin99
Result: Accepted
Take time: 0ms
Take Memory: 200KB
Submit time: 2018-09-15 18:37:39
****************************************************/