希尔排序
介绍
- 介绍
- 算法实现
- 实现方法1(我编写的我认为容易理解的希尔排序实现算法)
- 实现效果
- 实现方法2(网络上最常见的希尔排序算法)
- 扩展
- 后续
希尔排序又称缩小增量排序,基本思想为:先将待排序列分割成若干子表,把相隔某个增量的记录组成一个子表,对各个子表分别进行直接插入排序,当整个表已基本有序的时候,再对整个表进行一次直接插入排序。
希尔排序的过程如下:先取一个小于n的步长d1,把表中的全部记录分成d1组,所有距离为d1的倍数的记录放在同一组,在各组内进行直接插入排序;然后取第二个步长d2= 1; dk--) for(int i=dk+1;i 0 && A[0] < A[j]; j -= dk) A[j + dk] = A[j]; A[j + dk] = A[0]; } 扩展
数据结构或者说算法,只要理念是一样的,实现方法因人而异,我们不需要纠结到底哪一个效率最高,因为只要是按照此算法理解实现的程序,大致的算法时间复杂度都大同小异,关键是我们是否能学会此算法,而判断我们学会算法的标准就是自己能写出符合此算法思路的实现程序,如果能和网络上其他人写的不一样,反而是一种好事。所以读者可以仔细理解一下上面的两个程序,来理解一下希尔排序的理念和优点。
后续欢迎关注公众号:物联网知识