数据结构：从插入排序到希尔排序

插入排序（C语言版）

说明：

算法思路： 每次从无序表中取出第一个元素，将其插入到有序表中的适当位置，使有序表的长度不断加长，完成排序过程。
n个待排序的元素由一个有序表和一个无序表组成,开始时有序表中只包含一个元素。 流程演示：
蓝色表示由有序表，黑色表示无序表！分析元素基本有序时，直接插入排序的时间复杂度接近于O（n）
元素数目n较少时，直接插入排序的效率较高

数据结构定义：

首先我们要构建一个顺序表来存放待排序的元素！

这是我排序的基础，我的所有的排序算法都会依赖于这个简单的顺序表！typedefintKeyType;// 定义关键字类型为整型typedefintInfoType;typedef struct{KeyTypekey;// 关键字项InfoTypeotherinfo;// 其他数据项}RedType; // 记录类型typedef struct {RedType r[MAXSIZE+1];// r[0]闲置或用作哨兵int length;// 顺序表长度}SqList;

编写了两个方法可以对顺序表进行初始化和遍历

void initSqList（SqList & S）{int t,count=0;while（scanf（"%d",&t）！=0）{count++;S.r[count].key=t;}S.length=count;}void traverseSqList（SqList S）{for（int i=1;i<=S.length;i++）printf（"%d",S.r[i].key）;}

优化的直接插入排序

我们在这里采用了优化，我们进行的是元素的移动和覆盖，而不仅仅是简单的交换。void sortByDirectlyInsert（SqList &L）{for（int i = 2; i <= L.length; i++）//第一个元素默认有序，所以直接从2开始if （L.r[i].key < L.r[i-1].key） {//这里进行了优化，如果i >i-1，说明从1～i这一段都是有序的，我们不需要进行后续操作L.r[0] = L.r[i];L.r[i] = L.r[i-1];int j;for（j = i - 2;L.r[0].key < L.r[j].key; j--）L.r[j+1] = L.r[j];L.r[j+1] = L.r[0];}//if}思路举例：
[ ]5 9 6 3 8 //待排序元素
[ ]5 9 //到这里是有序的
[ ]5 9 6 //到这里发现6小于9
[6 ]5 9 空 //将6移到监视哨，把它的位置空出来
[6 ]5 空 9 //让9来到原来6的位置，把9的位置空出来，看看6能不能填在那里
[6 ]5 6 9 //6可以填在那里，让空的位置等于监视哨
[]5 6 9 3
[3 ]5 6 9 空
[3 ]5 6 空 9
[3 ]5 空 6 9
[3 ]空 5 6 9
[3 ]3 5 6 9
[]3 5 6 9 8
[8 ]3 5 6 9 空
[8 ]3 5 6 空 9
[8 ]3 5 6 8 9
[]3 5 6 8 9

进一步优化版的插入排序

我们这样想，既然左半部分是是有序的，我们在有序的数组中找到插入位置，最好的方法非二分查找莫属。void sortByBinaryDirectlyInsert（SqList &L）{for（int i=2;i <= L.length; i++）{ L.r[0] = L.r[i];/* 保存待插入元素 */int low = 1,high = i-1;/* 设置初始区间 */while（low <= high） /* 确定插入位置 */{ int mid = （low+high）/2;if （L.r[0].key > L.r[mid].key）low = mid+1;/* 插入位置在高半区中 */elsehigh = mid-1; /* 插入位置在低半区中 */}/* while */for（int j = i - 1; j >= high +1;j--） /* high+1为插入位置 */L.r[j+1] = L.r[j];/* 后移元素，留出插入空位 */L.r[high+1] = L.r[0];/* 将元素插入 */}/* for */}

希尔排序

算法思想：

先将整个待排序元素序列分割成若干个小序列，在小序列内插入排序；
逐渐扩大小序列的长度（序列个数减少），使得整个序列基本有序；
最后再对全体元素进行一次直接插入排序。

代码实现：

void ShellInsert（SqList &L,int dk）{//对顺序表L作一趟希尔排序for（int i =dk+1; i <= L.length; i++）if （L.r[i].key < L.r[i-dk].key） {L.r[0] = L.r[i];int j;for（j = i - dk;j>0 &&L.r[0].key < L.r[j].key;j -= dk）L.r[j+dk] = L.r[j];L.r[j+dk] = L.r[0];}//if} //ShellInsertvoid ShellSort（SqList &L,int dlta[],int t）{//按增量序列dlta[0..t-1]进行希尔排序for（int k = 0; k < t; k++）ShellInsert（L,dlta[k]）; //一趟增量为dlta[k]的希尔排序} //ShellSort

说明：

1.希尔排序的实质是插入排序！希尔排序的分析是一个复杂的问题，增量序列的设置是关键，尚没有正式的依据说明何种设置最为合理！ 2.空间复杂度为O（1）,是一种不稳定的排序算法！本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-01/139059.htm