Shell Sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shell Sort is to allow exchange of far items. In shell Sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.
前言 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序 希尔排序思想:
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
希尔排序解析:
希尔排序动图:
希尔排序代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 public class ShellSort { public static void main (String[] args) { int [] arr = new int [80000 ]; for (int i = 0 ; i < 80000 ; i++) { arr[i] = (int ) (Math.random() * 80000 ); } long start = System.currentTimeMillis(); shellSortGression(arr); long end = System.currentTimeMillis(); System.out.println("80000个数字排序所用时间:" + (end - start)); } public static void shellSortGression (int [] arr) { for (int gap = arr.length / 2 ; gap > 0 ; gap /= 2 ) { for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[j]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } } } public static void shellSortExchange (int [] arr) { int temp = 0 ; for (int gap = arr.length / 2 ; gap > 0 ; gap /= 2 ) { for (int i = gap; i < arr.length; i++) { for (int j = i - gap; j >= 0 ; j -= gap) { if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } } }
延伸 ShellSort 希尔排序 shell sort 理解希尔排序的排序过程 韩顺平数据结构和算法 五分钟学会一个高难度算法:希尔排序
<
Design Patterns(十二) Template Method
Algorithm Insertion Sort
>