排序系列 之 希尔排序
创始人
2024-11-15 19:06:09
0次
  • !!!排序仅针对于数组哦
  • 本次排序是按照升序来的哦

介绍

  • 英文名为ShellSort,又称“缩小增量排序”
  • 是直接插入排序算法的一种更高效的改进版本
  • 希尔排序是把记录按下标的指定步长分组,然后按照每组使用直接插入排序,这样能保证一定程度上小的数值在前边
  • 此排序需要有插入排序的基础,不清除的可以移步了解一下排序系列 之 插入排序

解释起来有点拗口,直接按照步骤上图

在这里插入图片描述

本身数组就短,不需要移动很多次来排序,所以就避免了插入排序如果前边数值大,需要移动多次的情况了

代码

 public class ShellSort {     public static void main(String[] args) {         int[] arr = {1260,134,209,408,34,68907,29,1034,51,855,2,33,566,7,12};         sort(arr);         System.out.println(Arrays.toString(arr));     }      public static void sort(int[] arr){         // 循环步长,逐步减少         for(int gap=arr.length/2;gap>0;gap/=2){             // 按照分组来进行插入排序             for(int i=gap;i  // 每一组的第一个元素我们默认排好序了                 // 对组内元素进行插入排序,但是比较的步长是折半减少的                 for(int j=i-gap;j>=0;j-=gap){  // 这里j=i-gap是为了避免数组越界问题                     if(arr[j+gap]                         int temp = arr[j];                         arr[j] = arr[j+gap];                         arr[j+gap] = temp;                     }else {                         break;                     }                 }             }         }     } }   运行结果; [2, 7, 12, 29, 33, 34, 51, 134, 209, 408, 566, 855, 1034, 1260, 68907] 
 def sort(arr):     step = len(arr) // 2;  # 步长初始值为数组长度的一半     while step > 0:  # 步长每次都为原来的1/2,最小为1,所以保证大于0即可          for i in range(step, len(arr)):  # 从下表为step开始到数组结束,开始对每组进行插入排序             j = i - step             while j >= 0 and arr[j] > arr[j + step]:  # 保证下标最小为0,并且满足交换条件                 arr[j], arr[j + step] = arr[j + step], arr[j];                 j -= step   # 当前比值完成,j减小,往前移动          step //= 2;     print(arr)   if __name__ == '__main__':     arr = [1260, 134, 209, 408, 34, 68907, 29, 1034, 51, 855, 2, 33, 566, 7, 12]     sort(arr)  运行结果; [2, 7, 12, 29, 33, 34, 51, 134, 209, 408, 566, 855, 1034, 1260, 68907] 

复杂度

  • 时间复杂度在平均情况下为O(n log n),但在最坏情况下为O(n^2)
  • 空间复杂度未明确给出,由于其本质上是插入排序的一种变体,可以推测其空间复杂度也为O(1)
  • 它是稳定排序,意味着相等元素的相对顺序在排序后保持不变。
  • 适用于快速排序的预处理

相关内容

热门资讯

一分钟了解辅助!新518互游辅... 一分钟了解辅助!新518互游辅助多功能AI软件,新518互游真是真的是有辅助软件1、新518互游辅助...
终于清楚开挂!卡米大厅开挂多功... 终于清楚开挂!卡米大厅开挂多功能AI方法,卡米大厅其实存在有开挂方法1、下载好卡米大厅正确养号方法之...
六分钟了解作弊器!玄灵大厅作弊... 六分钟了解作弊器!玄灵大厅作弊器多功能AI软件,玄灵大厅真是有作弊器软件1、很好的工具软件,可以解锁...
一起来讨论外挂!椰子大厅外挂多... 一起来讨论外挂!椰子大厅外挂多功能AI攻略,椰子大厅原来是真的有外挂攻略1、椰子大厅辅助软件下载优化...
玩家必看教程辅助!鲨鱼众娱辅助... 玩家必看教程辅助!鲨鱼众娱辅助多功能AI攻略,鲨鱼众娱一直真的是有辅助攻略1、许多玩家不知道鲨鱼众娱...
盘点一款开挂!皇豪大厅开挂多功... 盘点一款开挂!皇豪大厅开挂多功能AI攻略,皇豪大厅确实是真的有开挂攻略1、进入到皇豪大厅是否有挂之后...
教学盘点辅助器!老夫子大厅辅助... 教学盘点辅助器!老夫子大厅辅助器多功能AI攻略,老夫子大厅竟然真的是有辅助器攻略1、该软件可以轻松地...
热点推荐透视挂!嗨玩娱乐麻将透... 热点推荐透视挂!嗨玩娱乐麻将透视挂多功能AI软件,嗨玩娱乐麻将本来真的是有透视挂软件1、下载好嗨玩娱...
一分钟揭秘作弊器!黑莓大厅作弊... 一分钟揭秘作弊器!黑莓大厅作弊器多功能AI教程,黑莓大厅本来是真的有作弊器教程1、首先打开黑莓大厅辅...
玩家必看科普开挂!七天娱乐开挂... 玩家必看科普开挂!七天娱乐开挂多功能AIapp,七天娱乐竟然存在有开挂app1、七天娱乐公共底牌简单...