前言:排序是现在程序员的必备技能,是很多公司的面试必考点,不管是做移动端,后端开发,排序是绕不过的,众生平等。学习其排序的思想往往能解决不同类型的问题,所以静下心来,研究一下不同的排序算法,算是对自己有一个提升。
排序概述:排序就是将一组对象按照某种逻辑顺序重新排列的过程。
十大排序算法:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序,希尔排序,计数排序,基数排序,桶排序。
本文对希尔排序走一个解析:
希尔排序步骤:
1.一种基于插入排序的快速排序算法。简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点得从数组一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要N-1次移动。
2.希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序,同时该算法突破0(n^2)的第一批算法之一。
3.希尔排序是把待排序数组按一定数量的分组,对每组使用直接插入排序算法排序;然后缩小数量继续分组排序,随着数量逐渐减少,每组包含的元素越来越多,当数量减至1时,整个数组恰被分成一组,排序就完成了。这个不断缩小的数量,就构成了一个增量序列。
代码举例:
对一个数组进行排序:(86,11,77,23,32,45,58,63,93,4,37,22)
int[] array = {86,11,77,23,32,45,58,63,93,4,37,22};
排序代码展示:
调用sort方法后打印如下:
对该案例进行分析:(86,11,77,23,32,45,58,63,93,4,37,22)
(1) 当gap = 6,因为该数组长度为12,那么就从58开始 到22这一组, 根据排序代码所知:currentValue = 58(待排序元素)preIndex = 0 currentValue < 第0个位置也就是86。 满足while条件进入:58这个位置变成了86 第0个位置就变成了58.直至for循环结束,完成了第一组排序。
数组变成 ------》 [58, 11, 77, 4, 32, 22, 86, 63, 93, 23, 37, 45]
(2)当gap = 3,因为该数组长度为12. 那么就从4开始 到45这一组依然按照第(1)顺序进行操作。
数组变成 ------》 [4, 11, 22, 23, 32, 45, 58, 37, 77, 86, 63, 93]
(3)当gap = 1,因为该数组长度为12. 那么就从11开始 到93这一组依然按照第(1)顺序进行操作。
数组变成 ------》 [4, 11, 22, 23, 32, 37, 45, 58, 63, 77, 86, 93]
至此排序结束
打印每个步骤的数组:
至此希尔排序就到这里讲解结束了,细看的话其实一点也不复杂。