三种插入排序详解和代码实现(直接插入排序、折半插入排序和希尔排序)

2024-08-25 11:20

本文主要是介绍三种插入排序详解和代码实现(直接插入排序、折半插入排序和希尔排序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 基本思想
  • 直接插入排序
    • 排序方法
    • 代码实现
    • 复杂度分析
  • 折半插入排序
    • 排序方法
    • 代码实现
    • 复杂度分析
  • 希尔排序
    • 排序方法
    • 代码实现
    • 复杂度分析
      • 最佳情况
      • 平均情况
      • 最坏情况
      • 增量序列的影响

基本思想

插入排序的基本思想是:每一趟将一个待排序的元素按照其关键字的大小插入到已经排好序的一组数据的适当位置,直到所有的待排序元素全部插入为止。
就像我们在打扑克时,每抓取一张牌,都将其插入到合适的位置,直到所有的牌摸完,我们就得到了一个有序的序列。

本文介绍三种插入排序的方法:直接插入排序折半插入排序希尔排序

直接插入排序

排序方法

  1. 将待排序的元素存放在数组中,数据元素的数量为 n n n
    1

  2. 每次选择一个元素将其放到前面的有序数组中,使得其仍然保持有序。共循环 n − 1 n-1 n1 次,第 k k k 次循环之后有序数组的长度为 k + 1 k+1 k+1
    2

代码实现

public class Test {public static void insertSort(int[] a) {for (int i = 1; i < a.length; i ++) {int key = a[i];int j = i - 1;// 数组元素后移直到key找到合适的位置while (j >= 0 && a[j] > key) {a[j + 1] = a[j];j --;}a[j + 1] = key;}}public static void main(String[] args) {int[] data = {5, 7, 4, 2, 0, 3, 1, 6};insertSort(data);for (int i : data) {System.out.print(i + " ");}}
}

复杂度分析

  1. 外层循环从 i = 1 i=1 i=1 开始,共执行了 n − 1 n-1 n1 次循环,内层循环中最坏情况下每次需要移动的次数为 O ( n ) O(n) O(n),因此时间复杂度为 O ( n 2 ) O(n^2) O(n2)
  2. 排序过程中只需要 O ( 1 ) O(1) O(1) 数量级的变量来记录状态,因此空间复杂度为 O ( 1 ) O(1) O(1)
  3. 直接插排由于在移动元素时可以是从后向前遍历移动,因此算法属于稳定排序。

折半插入排序

排序方法

  • 直接插入排序的基础上进行优化,在进行查找待插入元素位置操作的时候,我们可以利用二分法来实现(即折半查找)。

代码实现

public static void binaryInsertSort(int[] array) {for (int i = 1; i < array.length; i++) {int key = array[i];int left = 0;int right = i - 1;// 二分查找while (left <= right) {int mid = left + (right - left) / 2;if (key < array[mid]) {right = mid - 1;} else {left = mid + 1;}}int j = i - 1;while (j >= left) {array[j + 1] = array[j];j--;}array[left] = key;}
}

复杂度分析

  1. 折半插入排序的对象移动次数和直接插入排序相同,依赖于对象的初始排列方式。由于折半插入排序只是减少了元素之间的比较次数,并没有改变元素的移动次数。因此折半插入排序的时间复杂度仍为 O ( n 2 ) O(n^2) O(n2)
  2. 其空间复杂度也和直接插入排序相同,为 O ( 1 ) O(1) O(1)
  3. 折半插入排序也属于稳定排序,但是由于用到了二分查找,所以只能应用于顺序结构,不能用于链式结构。

希尔排序

排序方法

希尔排序实质上是采用分组插入的方法,将整个待排序的数组分为若干组,从而减少直接插入排序的数据量,对每个分组分别进行直接插入排序,然后增加每个分组的数据量重新进行排序。直至所有分组合并为一组。

  1. 确定一个增量 d 1 d_1 d1 ,并把间隔为 d 1 d_1 d1 的数据分入同一组中,在各组进行直接插入排序。
  2. 第二趟取增量 d 2 d_2 d2 ,重复上述分组和排序。
  3. 以此类推,直到所取的增量 d i = 1 d_i=1 di=1 d t < d t − 1 < . . . < d 2 < d 1 d_t<d_{t-1}<...<d_2<d_1 dt<dt1<...<d2<d1),所有数据在同一组中直接插入排序为止。

  1. 如图所示,第一趟取增量 d 1 = 4 d_1=4 d1=4,所有间隔为 4 4 4 的元素分为同一组,并进行直接排序。
    1

  2. 第二趟取增量 d 2 = 2 d_2=2 d2=2,所有间隔为 2 2 2 的元素分为同一组,并进行直接排序。
    2

  3. 第三趟取增量 d 3 = 1 d_3=1 d3=1,所有元素分为同一组,并进行直接排序,排序完成。
    3

代码实现

public static void shellSort(int[] array) {int n = array.length;// 每次间隔折半for (int gap = n / 2; gap > 0; gap /= 2) {// 同组元素直接插入排序for (int i = gap; i < n; i++) {int key = array[i];int j = i;while (j >= gap && array[j - gap] > key) {array[j] = array[j - gap];j -= gap;}array[j] = key;}}
}

复杂度分析

希尔排序的空间复杂度与上述两种排序相同,均为 O ( 1 ) O(1) O(1)
记录跳跃式的移动导致了希尔排序算法是不稳定的。

希尔排序的时间复杂度取决于所使用的增量序列(gap sequence)。以下是对希尔排序时间复杂度的详细分析

最佳情况

  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)(在某些特定的增量序列下,如Hibbard增量序列)
  • 描述:当增量序列优化得当时,希尔排序的性能接近于 O ( n l o g n ) O(nlogn) O(nlogn)。这意味着希尔排序在最优情况下的性能与归并排序相近。

平均情况

  • 时间复杂度 O ( n 3 2 ) − O ( n 5 4 ) O(n^\frac{3}{2})-O(n^\frac{5}{4}) O(n23)O(n45)
  • 描述:对于大多数常用的增量序列(如Shell增量序列、Knuth增量序列等),希尔排序的平均时间复杂度通常介于 O ( n 3 2 ) O(n^\frac{3}{2}) O(n23) O ( n 5 4 ) O(n^\frac{5}{4}) O(n45) 之间。

最坏情况

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2)(例如,使用简单的增量序列,如 n 2 , n 4 , . . . , 1 \frac{n}{2},\frac{n}{4},...,1 2n4n...1
  • 描述:在使用不优化的增量序列时,希尔排序的时间复杂度可能会退化到 O ( n 2 ) O(n^2) O(n2),类似于简单插入排序的时间复杂度。

增量序列的影响

  1. Shell增量序列:初始增量为 n 2 \frac{n}{2} 2n,然后逐步减小到 1 1 1。时间复杂度为 O ( n 2 ) O(n^2) O(n2)
  2. Hibbard增量序列:增量为 1 , 3 , 7 , 15 , . . . , 2 k − 1 1, 3, 7, 15, ..., 2^k-1 1,3,7,15,...,2k1。时间复杂度为 O ( n 3 2 ) O(n^\frac{3}{2}) O(n23)
  3. Knuth增量序列:增量为 1 , 4 , 13 , 40 , 121 , . . . , 3 k − 1 2 1, 4, 13, 40, 121, ..., \frac{3^{k-1}}{2} 1,4,13,40,121,...,23k1。时间复杂度为 O ( n 5 4 ) O(n^\frac{5}{4}) O(n45)
  4. Sedgewick增量序列:例如, 1 , 5 , 19 , 41 , 109 , . . . 1, 5, 19, 41, 109, ... 1,5,19,41,109,... 时间复杂度为 O ( n 4 3 ) O(n^\frac{4}{3}) O(n34)

这篇关于三种插入排序详解和代码实现(直接插入排序、折半插入排序和希尔排序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1105416

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一