侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 292 篇文章
  • 累计创建 132 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

java排序算法之希尔排序

孔子说JAVA
2019-10-26 / 0 评论 / 0 点赞 / 85 阅读 / 1,976 字 / 正在检测是否收录...

1、排序算法概述

常用的内部排序方法有:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)、插入排序(直接插入排序、希尔排序)、归并排序、基数排序(一关键字、多关键字)。

  • 所需辅助空间最多:归并排序
  • 所需辅助空间最少:堆排序
  • 平均速度最快:快速排序
  • 不稳定:快速排序,希尔排序,堆排序。

选择排序算法的依据:任何排序算法在数据量小的时候基本体现不出来差距。选择依据有:

  • 1.数据的规模 :当数据规模较小时,选择直接插入排序或冒泡排序。
  • 2.数据的类型 :如全部是正整数,那么考虑使用桶排序为最优。
  • 3.数据已有的顺序 :快排是一种不稳定的排序(当然可以改进),对于大部分排好的数据,快排会浪费大量不必要的步骤。

数据量极小,而且已经基本排好序,冒泡是最佳选择。我们说快排好,是指大量随机数据下,快排效果最理想。而不是所有情况。

2、希尔排序时空复杂度

最差时间复杂度O(n^2),平均时间复杂度O(nlogn),空间复杂度O(1),是一种不稳定的排序算法。最优时间复杂度根据步长序列的不同而不同。

3、希尔排序原理

希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,是将整个无序列分割成若干小的子序列分别进行插入排序,希尔排序并不稳定。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

  • 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序(这样可以让一个元素可以一次性地朝最终位置前进一大步);随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,到了这步,需排序的数据几乎是已排好的了(此时插入排序较快),算法终止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 1.插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率。
  • 2.插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。

4、希尔排序思路

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中,最后对这个组进行直接插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。

5、希尔排序举例说明

要排序数组:int[] arr={13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10};

1.以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样(竖着的元素是步长组成):

13 14 94 33 82 
25 59 94 65 23
45 27 73 25 39
10

2.然后我们对每列进行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

3.将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了,然后再以3为步长进行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

4.排序之后变为:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

5.最后以1步长进行排序(此时就是简单的插入排序了)

image-1649572137276

6、希尔排序代码

public class ShellSort {
	public static void main(String[] args) {
		int[] ins = { 2, 3, 5, 1, 23, 6, 78, 34, 23, 4};
		System.out.println("排序之前:"+Arrays.toString(ins));
		int[] ins2 = sort(ins);
		System.out.println("排序之后:"+Arrays.toString(ins2));
	}

	public static int[] sort(int[] ins) {
		int n = ins.length;
		int gap = n / 2;   //增量长度
		int i, j, temp;
		while (gap > 0) {
			for (i = gap; i < n; i++) {
                temp = ins[i];
                j = i - gap;
                while (j >= 0 && ins[j] > temp) { // ins[j] > temp将会使数组从小到到排序。
                	ins[j + gap] = ins[j];
                    j = j - gap;
                }
                ins[j + gap] = temp;
            }
			gap = gap / 2;
		}
		return ins;
	}
}

// 排序之前:[2, 3, 5, 1, 23, 6, 78, 34, 23, 4]
// 排序之后:[1, 2, 3, 4, 5, 6, 23, 23, 34, 78]
0

评论区