3.==========================================希尔排序==================================================
1. 希尔排序的基本思想 希尔排序方法又称为缩小增量排序，其基本思想是是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序 。 所谓"基本有序"是指，在序列中的各个关键字之前，只存在少量关键字比它大的记录。
2. 具体步骤可以描述如下： 先看一个具体例子的希尔排序的过程。例如一个含11个关键字的序列 (16，25，12，30，47，11，23，36，9，18，31)，先对它进行“增量为5”的插入排序，即分别使 (R1、R6 、R11) 、(R2、R7) 和(R3、R8)、(R4、R9)、(R5、R10) 为有序序列，然后将增量“缩小到3”，排序结果使 (R1、R4、R7、R10) 、(R2、R5、R8) 和(R3、R6、R9) 分别成为有序序列，之后经过增量“缩小到1”的最后一趟插入排序即得到有序序列。
源码：
#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 #define OVERFLOW_ERROR -1 typedef int KeyType; typedef int Status; typedef int OtherInfo; typedef struct { KeyType key;//关键字 OtherInfo info;//其他相关的信息 } RedType;//关键字的相关信息 //线性表的相关信息 typedef struct { RedType *elem;//元素 int length;//元素长度 } Shell_Sort; int number;//数组的具体长度 int flag_maker = 0;//次数转变的变量 int maker = 0;//标识排序的具体次数 //打印好已经排序好的序列和刚开始初始化时的序列 Status print_Sort(Shell_Sort shell_array) { int i = 0; for(i = 1; i<=number; i++ ) { printf(" %d", shell_array.elem[i].key); } printf("\n"); return TRUE; } //直接初始化和赋值 Status Init_Shell_Sort(Shell_Sort &shell_array) { int elem; //分配长度 shell_array.elem = new RedType[MAXSIZE]; //存储元素数据应该从数组的第一位开始存储 shell_array.length = 0; //文件操作 FILE *pFile; //返回的是文件的地址 pFile = fopen("liuwenhao.txt","r"); //文件打开失败 if(pFile == NULL) { printf("cannot open file liuwenhao.txt"); return FALSE; exit(OVERFLOW_ERROR); } //从文件里面取值，是一个一个的取值 fscanf(pFile,"%d",&number); for(int i = 0; i<=number; i++) { shell_array.elem[i].key = NULL;//地址初始化为NULL } for(int i = 1; i<=number; i++) { //获取关键字 fscanf(pFile,"%d",&elem); shell_array.elem[shell_array.length+1].key = elem; shell_array.length = shell_array.length + 1; } return TRUE; } //排序 Status shell_Sort(Shell_Sort &shell_array, int elemType) { int j; //对顺序表shell_array 做一次增量为elemType的希尔插入排序 for(int i = elemType + 1; i<=shell_array.length; i++) { if(shell_array.elem[i].key < shell_array.elem[i-elemType].key) { //不成立的哨兵位置 shell_array.elem[0].key = shell_array.elem[i].key; maker = maker + 1; //查找待插入的位置 for(j = i-elemType; j>0&& shell_array.elem[0].key < shell_array.elem[j].key; j = j-elemType) { shell_array.elem[j + elemType].key = shell_array.elem[j].key; maker = maker + 1; } //找到了待插入的位置 shell_array.elem[j + elemType].key = shell_array.elem[0].key; maker = maker + 1; } } return TRUE; } //直接插入算法 Status shell_Insert_Sort(Shell_Sort &shell_array, int temp[]) { for(int i = 2; i>=0; i--) { shell_Sort(shell_array, temp[i]); } return TRUE; } //主函数 int main(void) { Shell_Sort shell_array; int temp[3] = {5, 3, 1}; Init_Shell_Sort(shell_array); printf("\t输出排序前序列...\n"); print_Sort(shell_array); printf("\n"); shell_Insert_Sort(shell_array, temp); printf("\t输出排序后序列...\n"); print_Sort(shell_array); printf("\n"); return 0; } 结果：
