首页  

希尔排序     所属分类 algo 浏览量 92
希尔排序 Shell Sort 是插入排序的一种 
又称 缩小增量排序 Diminishing Increment Sort 
是直接插入排序的改进版本 ,非稳定排序算法
因 D.L.Shell 于 1959 年提出而得名

将一个原序列分成几个子序列,对每个子序列都进行一次插入排序
将原序列进行处理 使其变得有序一些
插入排序  O(n^2) 
越是有序的序列,需要的时间越少,甚至在某些情况下可以逼近O(n) 

首先将间隔 gap 设定为n/2,然后跳跃进行插入排序
再来间隔n/4,跳跃进行排序动作 
继续 间隔 n/8  n/16 ...  直到间隔为1  
由于上一次的排序动作将固定间隔内的元素排序好
间隔越来越小时,越来越有序 

3,2,1,9,4,8,7,5,6

gap=4
3 2 1 5 4 8 7 9 6 
gap=2
1 2 3 5 4 8 6 9 7 
gap=1
1 2 3 4 5 6 7 8 9 


public class ShellSort { public static void main(String[] args) throws Exception { int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 }; shellSort(arr); } private static void shellSort(int[] arr) { final int N = arr.length; int gap = N / 2; int i, j; while (gap > 0) { for (i = 0; i < gap; i++) { for (j = i + gap; j < N; j += gap) { for (int k = j - gap; k >= i; k -= gap) { if (arr[k] > arr[gap + k]) { swap(arr, k, gap + k); } } } } // for debug System.out.println("gap=" + gap); printArr(arr); gap /= 2; } } private static void printArr(int[] arr) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < arr.length; i++) { sb.append(arr[i]).append(" "); } System.out.println(sb.toString()); } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
https://gitee.com/dyyx/hellocode/blob/master/src/algo/sort/ShellSort.java
冒泡选择和插入排序比较

上一篇     下一篇
关于数学的名言

冒泡选择和插入排序比较

金庸小说人物英文名

快速排序

Java assert

图论基础