排序算法--------Shell排序(希尔排序/缩小增量排序)
Shell排序(希尔排序/缩小增量排序)
- 1.简介
- 2.改进了什么?
- 3.思想的体现
- 4.算法复杂度的分析
- 5.举个例子
- 6.java代码实现
- 7.对比直接插入排序
1.简介
希尔排序是非稳定排序算法。 希尔排序因DL.Shell于1959年提出而得名。 是对直接插入排序的一个优化。
2.改进了什么?
由于直接插入排序是一步一步移动的而,我们不希望它是一步一步的移动,而是大步大步的移动。所以为了达到这个条件希尔排序就被发明出来了,它也是当时打破效率 O(n^2)的算法之一。
3.思想的体现
(1) 由于直接插入排序复杂度是O(n^2),因此用Gap分组后,每组的数据量变少,则每组的直接插入排序耗时就会大幅降低;
(2) 不管选用几次Gap,只要最后一次Gap=1,总能完成排序;
(3) 显然,最终的排序耗时是和Gap的选择策略有关的。
4.算法复杂度的分析
希尔排序的关键并不是随便分组后各自排序,而是将相隔某个“增量”的记录组成一个字序列,实现跳跃式的移动,使得排序的效率提高。这的“增量”选取就非常关键了。我们采用的是arr.lenght/2的方式选取。可究竟选取一个什么样的值,最好呢?目前1还是数学难题(有兴趣可以参考:https://en.wikipedia.org/wiki/Shellsort)
5.举个例子
(1)第一趟: 选择gap=5,则共得到5组数据(相同颜色为一组),为每一组分别使用直接插入排序;
(2)第二趟选择gap=2,则共得到2组数据(相同颜色为一组),为每一组分别使用直接插入排序;
(3)第三趟: 选择gap=1,对所有数据使用一次直接插入排序。
注 :图中有两个相等数值的元素 5 和 下划线5 在排序过程中,两个元素位置交换了 ==》不稳定性的体现。
6.java代码实现
package com.lsl.datastructure;
public class ShellSort {
public static void main(String[] args) {
int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
System.out.println("排序前:");
ShellSort.printAll(array);
System.out.println("排序后:");
ShellSort.shellSort(array);
}
public static void shellSort(int[] arr){
if (arr == null || arr.length == 0) {
//判断数组是否为空
System.out.println("该数组为空!");
} else {
int len = arr.length;
for (int gap = len / 2; gap > 0; gap /= 2) {
for (int i = gap; i < len; i++) {
//从第gap个元素,逐个对其所在组进行直接插入排序操作
int j = i;
while (j - gap >= 0 && arr[j] < arr[j - gap]) {
int temp = arr[j];
arr[j] = arr[j - gap];
arr[j - gap] = temp;
//插入排序采用交换法
j -= gap;
}
}
}
ShellSort.printAll(arr);
}
}
private static void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
}
运行结果:
7.对比直接插入排序
- 直接插入排序是稳定的;而希尔排序是不稳定的。
- 直接插入排序更适合于原始记录基本有序的集合。
- 希尔排序的比较次数和移动次数都要比直接插入排序少,当N越大时,效果越明显。
- 在希尔排序中,增量序列gap的取法必须满足:最后一个步长必须是 1 。
- 直接插入排序也适用于链式存储结构;希尔排序不适用于链式结构。
版权声明:本博客为记录本人自学感悟,转载需注明出处!
https://me.csdn.net/qq_39657909
还没有评论,来说两句吧...