Java希尔排序
Binaire-沐辰 人气:0希尔排序
希尔排序时插入排序的一种,也称缩小增量排序,是直接插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
算法思想
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的数越来越多当增量减至1时,整个序列恰好被分成一组,算法完成。
我们以增序排序为例,希尔排序基本步骤:选择初始增量gap=length/2
,缩小增量继续以gap=gap/2
的方式进行,直到增量gap=1
为止,增量的每次变化都会将原始序列划分为若干组,分别对每一组进行插入排序,每一次通过增量划分组进行插入排序宏观上小的数移到了前面,大的数移到了后面,最后增量gap=1进行插入排序后就是最终的有序序列。下面以图解的方式详细介绍希尔排序算法的整个流程。
图解
代码实现(Java)
public class ShellSort { public static void main(String[] args){ int[] array = {86,11,54,34,53,12,45,81,19,65}; int gap = array.length; while (true) { gap /= 2; //增量每次减半 for (int i = 0; i < gap; i++) { for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序 int k = j - gap; while (k >= 0 && array[k] > array[k+gap]) { int temp = array[k]; array[k] = array[k+gap]; array[k + gap] = temp; k -= gap; } } } if (gap == 1) break; } System.out.println("排序结果:"); for(int i=0;i<array.length;i++){ System.out.print(array[i]+" "); } } } //排序前:{86,11,54,34,53,12,45,81,19,65} //排序后:{11,12,19,34,45,53,54,65,81,86}
加载全部内容