希尔排序
希尔排序是简单插入排序的改进,它是一种不稳定排序算法。由D.L.Shell在1959年提出。希尔排序实质上是一种分组插入方法。
算法描述
1、对于n个待排序的数列,取一个小于n的整数gap(称为步长)将待排序元素分成若干个组子序列,所有距离为gap的倍数的记录放在同一个组中。
2、然后对各组内的元素进行直接插入排序,这一趟排序完成之后,每一个组的元素都是有序的。
3、接下来减小gap的值,并重复执行上述的分组和排序。
4、重复这样的操作,当gap=1时,整个数列就是有序的。
图文演示
下面以数列{23,20,32,45,6,8,9,15}为例,演示它的希尔排序过程。
第1趟:(gap=4)
当gap=4时,意味着将数列分为4个组: {23,6},{20,8},{32,9},{45,15}。 对应数列: {23,20,32,45,6,8,9,15}
对这4个组分别进行排序,排序结果: {6,23},{8,20},{9,32},{15,45}。 对应数列: {6,8,9,15,23,20,32,45}
第2趟:(gap=2)
当gap=2时,意味着将数列分为2个组:{6,9,23,32}, {8,15,20,45}。 对应数列: {6,8,9,15,23,20,32,45}
注意:{6,9,23,32}实际上是上一步中的两个有序数列{6,23}和{9,32}组成。
{8,15,20,45}实际上是上一步中的两个有序数列{8,20}和{15,45}组成。
对这2个组分别进行排序,排序结果:{6,9,23,32}, 8,15,20,45}。 对应数列: {6,8,9,15,23,20,32,45}。
这一步其实啥都没做,这也可以看出希尔排序的不稳定性。
第3趟:(gap=1)
当gap=1时,意味着将数列分为1个组:{6,8,9,15,23,20,32,45}
注意:{6,8,9,15,23,20,32,45}实际上是上一步中的两个有序数列{6,9,23,32},和{8,15,20,45}组成。
对这1个组分别进行排序,排序结果:{6, 8, 9, 15, 20, 23, 32, 45}
代码实现
Java
1 | package com.test; |
排序结果:[6, 8, 9, 15, 20, 23, 32, 45]
JavaScript
1 | function shellSort(arr){ |
(8) [6, 8, 9, 15, 20, 23, 32, 45]