排序算法之希尔排序

希尔排序介绍

希尔排序,也称递减增量排序算法(缩小增量排序),是插入排序的一种更高效的改进版本,但希尔排序是非稳定排序算法

希尔排序基本思想

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件被分成一组,算法便终止

希尔排序算法讲解(需要有直接插入排序算法作为基础知识)

(说明:分组个数等于下标增量等于步长,说的都是同一个意思,分组=下标增量=步长)

以数组 {82 ,31 ,29 ,71, 72, 42, 64, 5, 110} 为例

该数组长度为9,初始增量初始默认设置为数组长度的一半,取整,为4

就可以把以上数组分为以下四个子数组,然后对每个子数组分别进行直接插入排序

子数组1

子数组2

 

子数组3

子数组4

对每个子数组进行直接插入排序后得到以下数组:

重新设置增量 = 之前增量的1/2   即是4/2=2

在增量为2的前提下,分成以下两个子数组,分别对各个子数组进行直接插入排序

子数组1

子数组2

 对每个子数组进行直接插入排序后得到以下数组:

重新设置增量 = 之前增量的1/2   即是2/2=1

增量为1的时候,就是对整个数组分成一组,进行直接插入排序 

得到最终排序结果:

 代码实现

1package com.zzb.sort; 2 3import java.util.Arrays; 4 5/** 6 * @Auther: Administrator 7 * @Date: 2020/3/8 14:36 8 * @Description: 希尔排序(直接插入排序的升级版) 9 */ 10public class ShellSort { 11 public static void main(String[] args) { 12 int[] array = {82, 31, 29, 71, 72, 42, 64, 5, 110}; 13 14 shellSort(array); 15 System.out.println(Arrays.toString(array)); 16 /*[5, 29, 31, 42, 64, 71, 72, 82, 110]*/ 17 } 18 19 /** 20 * 希尔排序算法 21 * @param array 待排序数组 22 * 23 * 说明:分组个数即为步长,或者即为下表增量 24 */ 25 private static void shellSort(int[] array) { 26 //待插入元素 27 int insertValue; 28 // 初始默认值为各个分组每次循环比较开始时,待插入元素左边的已排序元素的索引位置 29 int insertIndex; 30 // 对待排序数组进行分组 31 // 初始分组个数为数组长度的一半 32 // gap /= 2 分组逐步减半,向1靠近 33 for(int gap = array.length / 2; gap > 0; gap /= 2) { 34 // 对各个分组中的若干元素进行直接插入排序 35 // 共有gap个分组 36 for(int i = 0; i < gap; i++) { 37 // 取出各个分组中的元素进行直接插入排序 38 // j = gap + i 默认每一个分组中的第一个元素为已排序,需要找出下一个元素与已排序元素进行比较排序 39 // j < array.length 能够获取到每一个分组中的全部元素 40 // j += gap 元素下标差等于步长gap的元素都在同一个分组中 41 for(int j = gap + i; j < array.length; j += gap) { 42 // 如果待插入元素比已排序元素小,则需要比较找出插入位置 43 if(array[j] < array[j - gap]) { 44 //待插入元素 45 insertValue = array[j]; 46 // 初始默认值为各个分组每次循环比较开始时,待插入元素左边的已排序元素的索引位置 47 insertIndex = j - gap; 48 // insertIndex >= 0 保证在给待插入元素insertVal找插入位置,数组下标不越界 49 // insertVal < arr[insertIndex] 待插入元素还没有找到要插入的位置 50 while(insertIndex >= 0 && insertValue < array[insertIndex]) { 51 // 如果待插入元素小于已排序元素,则将已排序元素向后移动一个位置 52 array[insertIndex + gap] = array[insertIndex]; 53 // 继续与已排序元素进行比较 54 insertIndex -= gap; 55 } 56 // 退出while循环,待插入元素已找到插入位置,为insertIndex + gap 57 array[insertIndex + gap] = insertValue; 58 } 59 } 60 } 61 } 62 } 63} 64 65

 

下一篇:桶排序

代码交流 2021