赞
踩
希尔排序又叫“递减增量排序”,是一种插入排序,可以理解为直接插入排序的优化版。希尔排序将序列按照一定的增量划分为一个个小序列,每个小序列使用直接插入排序,完成后增量递减,每个小序列变大,继续进行直接插入排序,直到增量递减为1,进行最后的直接插入排序。
希尔排序使用于中规模数据量的排序。
希尔排序是直接插入排序的优化,其主要的思想:利用直接插入排序的优点和消灭直接插入排序的缺点来进行排序。
直接插入排序的优点:
1、如果序列中元素大部分有序,则排序较快
2、如果序列中的元素较少,则排序较快。
希尔排序先按照增量将其划分为一个个小序列,就是使用了直接插入排序的优点2,序列比较小,排序比较快,最后增量为1,由于序列中大部分元素已经有序,则排序比较快,使用了直接插入排序的优点1。
直接插入排序的缺点:排序时元素移动到其正确的位置通过比较慢慢移动
希尔排序使用增量来划分为一个个小序列,这样同一个序列中元素相隔一个增量,这导致直接插入排序时,如果元素移动,移动至少一个增量,移动速度快。
1、取序列长度的一半作为增量n,则前n-1个元素为各个序列的第一个元素,从n个元素开始遍历比较,n和索引为n-n比较,小的向前,序列右移,大于或者等于不变。
2、增量n遍历完成后,新的增量为n=n/2,重复操作1和2,直到增量为1,进行最后一次直接插入排序。
- public class ShellSort {
-
- /**
- * 希尔排序
- * @param args
- */
- public static void main(String[] args) {
- int[] arr = {1, 4, 9, 2, 5, 3, 7, 6, 22, 23, 24};
- shellSort(arr);
- for (int i = 0; i < arr.length; i++) {
- System.out.print(arr[i] + " ");
- }
- }
-
- private static void shellSort(int[] arr) {
- if (arr == null) {
- return;
- }
- int length = arr.length;
- // 设置增量为length/2
- for (int i = length / 2; i > 0; i = i / 2) {
- // 从第i个元素开始比较,相当于第二个元素
- for (int j = i; j < length; j++) {
- // 直接插入排序
- insertionSort(i, j, arr);
- }
- }
- }
-
- private static void insertionSort(int i, int j, int[] arr) {
- int temp = arr[j];
- int k = j;
- for (int l = j - i; l >= 0; l = l - i) {
- if (temp < arr[l]) {
- // 右移
- arr[l + i] = arr[l];
- k = l;
- }
- }
- arr[k] = temp;
- }
- }
希尔排序的时间复杂度是随着增量的变化而变化,时间复杂度在O(nlogn) ~ O(n²)之间,空间复杂度为O(1),是不稳定算法。希尔排序的重点是:先递减分组,后直接插入
时间复杂度在O(n^1.3) ~ O(n²):这个是随增量的变化而变化,百度百科显示为1.5
空间复杂度O(1):只需要保存临时变量
不稳定算法:由于增量将其分成不同的序列,可能导致相同的元素相对位置发生改变,例如:{4,3,5,7,3},如果增量为2,则3的相对位置会发生改变。
希尔排序的类比:类似于我们有一叠正常的扑克牌,现在我们要将其从小到大按照红桃、黑桃、梅花、方块进行排序,我们首先按照红黑梅方划分为四组,则增量可以理解为4,每组进行直接排序,后面增量为1,只有1组,我们只需要进行一次直接排序就行。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。