数据结构中的排序问题

Question

1. 若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行希尔排序，首次增量为5，写出每步过程及结果。

Answer 1

排序前:[10,7,36,4,8,56,10,11,77,15]
-------增量d=5-------
数组情况:[10,7,36,4,8,56,10,11,77,15]
未排序分组:
第0分组[10,56]
第1分组[7,10]
第2分组[36,11]
第3分组[4,77]
第4分组[8,15]
排序后分组:
第0分组[10,56]
第1分组[7,10]
第2分组[11,36]
第3分组[4,77]
第4分组[8,15]
数组情况:[10,7,11,4,8,56,10,36,77,15]
-------增量d=3-------
数组情况:[10,7,11,4,8,56,10,36,77,15]
未排序分组:
第0分组[10,4,10,15]
第1分组[7,8,36]
第2分组[11,56,77]
排序后分组:
第0分组[4,10,10,15]
第1分组[7,8,36]
第2分组[11,56,77]
数组情况:[4,7,11,10,8,56,10,36,77,15]
-------增量d=1-------
数组情况:[4,7,11,10,8,56,10,36,77,15]
未排序分组:
第0分组[4,7,11,10,8,56,10,36,77,15]
排序后分组:
第0分组[4,7,8,10,10,11,15,36,56,77]
数组情况:[4,7,8,10,10,11,15,36,56,77]
排序后:[4,7,8,10,10,11,15,36,56,77]

#define SHELL_MAX_SIZE 10
/*
 定义希尔排序的数据结构
 */
typedef struct{
    int data[SHELL_MAX_SIZE];//定义数组
    int lenth;//当前数组的长度
}Shell;

/*
 希尔排序:执行的时间依赖于增量数组.
 增量数组:
 1.建议是降序的.会按照增量的数组顺序做每次的插入排序.
 2.尽量避免增量序列中的增量为互为倍数情况.
 3.最后一个肯定是1,因为最后一次操作是要将整个数组进行排序.
 优势在于:按照前面增量进行排序后,有形成阶段范围的有序,减少了比较次数和移动结点次数
 shell:待排序数组信息
 d[]:增量的数组,会按照增量的数组顺序做每次的插入排序.最后一个元素肯定是1.
 dSize:增量数组的长度
 */
void shellSort(Shell shell,int d[],int dSize);


/*
 希尔排序中的一次排序
 每个分组内使用插入排序进行排序
 shell:希尔数据对象
 d:增量.分组中元素相差的间距
 */
Shell shellOnceSort(Shell shell,int d);

/*
 打印数组中的分组
 shell:希尔数据对象
 d:增量.分组中元素相差的间距
 第0组:[0,0+dk,0+2*dk,0+3*dk,....]
 第1组:[1,1+dk,1+2*dk,1+3*dk,....]
 第d-1组:[2,2+dk,2+2*dk,2+3*dk,....]
 */
void printShellGroup(Shell shell,int d);

/*
 打印Shell数据
 */
void printShell(Shell shell,int start,int end);


/*
 希尔排序
 shell:待排序数组信息
 d[]:增量的数组,会按照增量的数组顺序做每次的插入排序.
 dSize:增量数组的长度
 */
void shellSort(Shell shell,int d[],int dSize){
    printf("排序前:");
    printShell(shell,0,shell.lenth-1);
    int i=0;
    //遍历增量数组
    for(i=0;i<dSize;i++){
        //按照增量分组,组内进行排序进行排序
       shell= shellOnceSort(shell, d[i]);
    }
    printf("排序后:");
    printShell(shell,0,shell.lenth-1);
    
}

/*
 希尔排序中的一次排序
 每个分组内使用插入排序进行排序
 shell:希尔数据对象
 d:增量.分组中元素相差的间距
 */
Shell shellOnceSort(Shell shell,int d){
    //1.按照增量d将待排序数组分成d-1组.0~d-1
    //2.开始遍历角标范围:d~shell.length.往每个分组中使用插入排序进行插入.
    //默认情况
    //第0组:有序:[0] 无序:[0+dk,0+2*dk,0+3*dk,....]
    //第1组:有序:[1] 无序:[1+dk,1+2*dk,1+3*dk,....]
    //第d-1组:有序:[d-1] 无序:[2+dk,2+2*dk,2+3*dk,....]
    printf("-------增量d=%d-------\n",d);
    printf("数组情况:");
    printShell(shell, 0, shell.lenth-1);
    printf("未排序分组:\n");
    printShellGroup(shell, d);
    int i,j;
    int temp;//插入排序用到的临时变量
    //3.[d~shell.lenth-1]是无序的,那么就遍历此范围,插入到自己所属的分组中
    for(i=d;i<shell.lenth;i++){
        //3.1:分组内进行插入排序
        if(shell.data[i]<shell.data[i-d]){
            temp=shell.data[i];
            j=i-d;
            //3.2.此时需要找到组内插入的位置
            while (j>=0 && temp<shell.data[j]) {
                //寻找插入的位置,并且组内进行移动数据
                shell.data[j+d]=shell.data[j];
                //组内往前查找
                j=j-d;
            }
            //3.3找到了组内插入的位置,将值插入即可
            shell.data[j+d]=temp;
        }
    }
    //4.打印当前增量排序后情况
    printf("排序后分组:\n");
    printShellGroup(shell, d);
    printf("数组情况:");
    printShell(shell, 0, shell.lenth-1);
    return shell;
}
/*
 打印分组情况
 */
void printShellGroup(Shell shell,int d){
    int  i,j;
    for(i=0;i<d;i++){
        printf("第%d分组[",i);
        for(j=i;j<shell.lenth;j+=d){
            if(j==i){
                printf("%d",shell.data[j]);
            }else{
                printf(",%d",shell.data[j]);
            }
        }
        printf("]\n");
    }
}

/*
 打印Shell数据
 */
void printShell(Shell shell,int start,int end){
    printf("[");
    for(int i=start;i<=end;i++){
        if(i==start){
            printf("%d",shell.data[i]);
        }else{
            printf(",%d",shell.data[i]);
        }
    }
    printf("]\n");
}

int main(int argc, const char * argv[]) 
{
    Shell shell={{10,7,36,4,8,56,10,11,77,15},10};
    //增量数组
    int  ds[]={5,3,1};
    //希尔排序
    shellSort(shell,ds,3);
    return 0;
}