数据结构-基于C++语言（微课版） 课件 1-2 希尔排序

希尔排序的概念；希尔排序的基本思想；本节目录：本节内容：希尔排序希尔排序希尔排序的步骤；概念在直接插入排序算法中，关键字移动的次数主要与哪些因素有关？希尔排序顺序一：

233023354050456080顺序二：

233080605035454023移动次数：2例给定下面9个已经有序的关键字，如果关键字排序前的顺序不同，那么使用直接插入排序算法，关键字移动的次数是多少？关键字：232330354045506080移动次数：20结论1、关键字基本有序2、关键字个数尽可能少概念希尔排序就是将待排序的关键字划分成若干组，对每个组进行直接插入排序，从而减少参与直接插入排序的数据量和空间移动的时间开销。当经过几次分组排序后，每组关键字的排列已经基本有序，这个时候再对所有的关键字实施直接插入排序，减少数据移动的开销。这种缩小增量的直接插入排序方法，就是希尔排序方法。希尔排序关键字：

3015297020134815

1045236034433035

12345768

910111213151416希尔排序步骤1、关键字分组。假设待排序的关键字个数为n，以关键字间的距离d（步长因子）为划分标准，将距离相同的关键字划分为一组。如先取整数d=n/2，将所有距离为d的关键字构成一组，从而将整个待排序关键字序列分割成为d个子序列，即将关键字划分为d个组。希尔排序关键字：

3015297020134815

1045236034433035

12345768

910111213151416步长因子：d=n/2=8，分割序列，颜色相同的为一组关键字。希尔排序步骤1、关键字分组；2、组内排序。对每个分组分别进行直接插入排序；希尔排序关键字：

3015297020134815

1045236034433035

12345768

910111213151416组内组内直接插入排序步长因子：d=8

1015236020133015

3045297034434835d=8分组:希尔排序步骤1、关键字分组；2、组内排序。对每个分组分别进行直接插入排序；3、缩小间隔d=8，例如，取d=d/2=4；重复步骤1和2，对每组直接插入排序;希尔排序关键字：

1015236020133015

3045297034434835

12345768

910111213151416

1015236020133015

3045297034434835

1015131520233035

3045296034434870d=4,分组：d=4排序结果：希尔排序关键字：

3015297020134815

1045236034433035

12345768

910111213151416

1015236020133015

3045297034434835d=8结果:

1015131520233035

3045296034434870d=4结果：

1015131520233035

2945304834436070d=2结果：d=1结果：

1013151520292330

3034354345604870希尔排序完整演示排序方法不稳定希尔排序步骤1、关键字分组；2、组内排序。对每个分组分别进行直接插入排序；3、缩小间隔d=8，例如，取d=d/2=4；重复步骤1和2，对每组直接插入排序;4、直到最后取d=1，即将所有关键字放在一组进行一次直接插入排序，最终将所有关键字重新排列成按关键字有序的序列。希尔排序

12345768

91011121315141