| 词条 | Shell排序 |
| 释义 | 希尔排序是一种快速排序法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。 § 基本思想 不断把待排序的对象分成若干个小组，对同一小组内的对象采用直接插入法排序，当完成了所有对象都分在一个组内的排序后，排序过程结束。每次比较指定间距的两个数据项，若左边的值小于右边的值，则交换它们的位置。间距d按给定公式减少： di+1 =（di +1）/2 ，直到d等于1为止。D可以选取{9，5，3，2，1}。 § 算法步骤 Step1 将n个元素个数列分为5个小组，在每个小组内按直接插入法排序； step2 在第i步，分组个数取 di+1 =（di +1）/2 {9，5，3，2，1}；相临两组之间的对应元素进行比较，如果ai>aj，则交换它们的位置； Step3 当dK = 1的循环过程完成后，排序过程结束。 希尔排序举例：设有字符数列"f d a c b e"，执行Shell排序： § SHELL排序算法的描述 算法讨论： Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。研究证明，若增量的取值比较合理，Shell排序算法的时间复杂度约为O（n（ldn）2）。由于Shell排序算法是按增量分组进行的排序，所以Shell排序算法是一种不稳定的排序算法。 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。