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

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

相关文章

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技