vlambda博客
学习文章列表

排序算法(五):Shell Sort 希尔排序

品冠-多花一点时间疗伤 From ProjectDaedalus 04:08

基本排序算法中的插入排序虽然逻辑较为简单,但当排序规模较大时,经常需要将元素一位一位地从一端移动到另一端,效率非常低。于是Donald Shell设计了一种基于插入排序的改进版排序算法,故被命名为 Shell Sort 希尔排序

算法思想

插入排序效率低下是因为其移动元素每次只能移动一位,当排序元素的规模较大时,需要将元素一位一位地从一端移动到另一端。而如果我们能够让元素一次性地移动到较远的位置上,这样无疑就可以避免多次一位一位地移动操作。希尔排序正是基于此原理来优化、提高插入排序的效率。通过指定步长step,将原数组分为step个互相独立子数组,然后通过插入排序对这些子数组分别进行排序(即分组排序),这时我们称其为step有序数组。当step很大时,我们就可以将元素一次性移动到很远的位置上,为下一次较小的step有序创造便利;不断缩小步长step,重复上述过程建立step有序数组,达到局部有序的目的。当step最终为1做最后一次step有序时,就是我们平常所熟悉的插入排序了,由于该数组已经多次被较大的step进行分组排序了,此时只需要较少次数的元素移动就可以实现整个数组全局有序

排序算法(五):Shell Sort 希尔排序

在希尔排序中,需要经历若干次step有序。在每一次step有序过程中,分组所使用的step步长越来越小直到其为1,即其是一个最后项为1的递减序列。关于step序列的选取问题,不建议大家自行设计,这里给出一个合适并简单的step序列的通项公式。在实际使用时,根据排序规模计算到合适的第n项,然后将该数列反序。即为我们进行希尔排序时所用到的step序列

Java 代码示例

这里即是一个希尔排序的示例

 
   
   
 
  1. /**

  2. * 希尔排序

  3. */

  4. public class ShellSort {

  5. /**

  6. * 升序排列

  7. */

  8. public static void sort() {

  9. int[] array = getTestCase();

  10. int size = array.length;


  11. System.out.println("before sort: " + Arrays.toString(array) );


  12. int step = 1; // 希尔排序的步长

  13. // 根据排序规模计算step序列到第n项

  14. while( step < size/3 ) {

  15. step = 3 * step + 1; // step(n) = 1/2*(3^n-1) 的递推公式

  16. }


  17. while( step>=1 ) {

  18. // 按指定步长step进行分组,对array[i]进行排序,使之step有序

  19. for( int i=step; i<size; i++ ) {

  20. // 将array[i]插入到array[i-step],array[i-2*step],array[i-3*step]...当中

  21. for(int j=i; j-step>=0 && less(array[j], array[j-step]); j-=step ) {

  22. exchange(array, j, j-step);

  23. }

  24. }

  25. // 更新步长

  26. step = step/3;

  27. }


  28. System.out.println("after sort: " + Arrays.toString(array) );

  29. }


  30. /**

  31. * 判定a是否比b小

  32. * @param a

  33. * @param b

  34. * @return

  35. */

  36. private static boolean less(int a, int b) {

  37. if(a<b) {

  38. return true;

  39. }

  40. return false;

  41. }


  42. /**

  43. * 交换数组中 i、j 位置的元素

  44. * @param array

  45. * @param i

  46. * @param j

  47. */

  48. private static void exchange(int[] array, int i, int j) {

  49. int temp = array[i];

  50. array[i] = array[j];

  51. array[j] = temp;

  52. }


  53. /**

  54. * 获取测试用例

  55. */

  56. private static int[] getTestCase() {

  57. int[] caseArray = {-54,12,16,44,36,99,2,88,5,33,26,4,64,3,-44,-2,62,71,27,10,49,83,92};

  58. return caseArray;

  59. }

  60. }

测试结果如下:

特性

空间复杂度

由于希尔排序是原地排序算法,故其空间复杂度为O(1)

时间复杂度

希尔排序的时间复杂度很大程度取决于step序列的设计,故此在前文中不建议大家自行设计step序列。对于本文所给出的step序列,其时间复杂度不超过平方阶。就到底什么样的step序列是最优的,目前该问题依然无解。但我们可以知道的是,在中等规模的排序需求中,一般情况下直接使用希尔排序已经足够了。如果经实际测试确实需要优化,此时再考虑使用快排等排序算法也不迟

稳定性

不稳定

参考文献

  1. 算法(第4版) Robert Sedgewick、Kevin Wayne 著

  2. 计算机程序设计艺术(第3卷):排序与查找 高德纳(Donald E.Knuth) 著