希尔排序
所属分类 algo
浏览量 780
希尔排序 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
图论基础