首页 > 编程语言 >深入了解插入排序算法

深入了解插入排序算法

时间:2023-09-12 10:37:51浏览次数:44  
标签:arr int 插入排序 元素 算法 深入 key 排序

排序算法是计算机科学中的基础概念,它们用于对数据集合进行有序排列。插入排序(Insertion Sort)是其中一种简单而有效的排序算法。本文将详细介绍插入排序的工作原理,并提供Python、Go、Java和C语言的示例代码。

插入排序的基本思想

插入排序的基本思想是将数据分成已排序和未排序两部分,初始时已排序部分只包含第一个元素,而未排序部分包含其他元素。然后,它从未排序部分依次选择元素,将其插入到已排序部分的合适位置,直到所有元素都在已排序部分。

让我们通过一个简单的示例来理解插入排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4],我们希望按升序排序它。

  1. 初始状态: 首先,已排序部分只包含第一个元素 5,未排序部分包含其他元素 [2, 9, 3, 4]
  2. 第一次插入: 从未排序部分选择第一个元素 2,将它与已排序部分的 5 比较。因为 2 < 5,所以 2 插入到 5 的前面,得到 [2, 5][9, 3, 4]
  3. 第二次插入: 继续选择未排序部分的第一个元素 9,将它与已排序部分的 52 比较。由于 9 > 5,不需要交换。已排序部分保持不变 [2, 5],未排序部分为 [3, 4]
  4. 继续插入: 依此类推,依次选择未排序部分的元素并插入到已排序部分的正确位置。最终,数组被完全排序成 [2, 3, 4, 5, 9]

插入排序的关键在于将元素逐个插入到已排序部分,并确保已排序部分始终保持升序。

插入排序的时间复杂度

插入排序的时间复杂度取决于输入数据的顺序。在最好的情况下,即数据已经按升序排列,插入排序的时间复杂度为O(n),其中n是数组的长度。这是因为在最好情况下,不需要执行元素交换,只需遍历一次数组。

在最坏的情况下,即数据逆序排列,插入排序的时间复杂度为O(n^2),因为每个元素都需要与已排序部分的所有元素进行比较和移动。

插入排序在小型数据集上通常表现良好,但对于大型数据集,更高效的排序算法可能更合适。

插入排序的应用场景

尽管插入排序不如一些高级排序算法那样高效,但它仍然有一些应用场景:

  1. 小型数据集: 插入排序在处理小型数据集时性能良好,因为其常数因子较低。
  2. 部分有序数据: 如果数据集已经部分有序,插入排序的性能会较好,因为不需要多次交换元素。
  3. 稳定性要求: 插入排序是一种稳定的排序算法,可以保持相同元素的相对位置。
  4. 在线排序: 插入排序可以应用于在线排序场景,即数据不一次性全部可用,而是逐个元素到达。

示例代码

以下是插入排序的示例代码,分别使用Python、Go、Java和C语言编写。

Python 插入排序

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [5, 2, 9, 3, 4]
insertion_sort(arr)
print("排序后的数组:", arr)

Go 插入排序

package main

import "fmt"

func insertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && key < arr[j] {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

func main() {
    arr := []int{5, 2, 9, 3, 4}
    insertionSort(arr)
    fmt.Println("排序后的数组:", arr)
}

Java 插入排序

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && key < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 4};
        insertionSort(arr);
        System.out.print("排序后的数组: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

C 语言 插入排序

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 9, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

这些示例代码演示了插入排序的工作原理,并提供了Python、Go、Java和C语言的不同语言版本的实现。插入排序虽然简单,但在一些特定情况下是一种有效的排序算法,特别适合处理小型数据集或部分有序的数据。

标签:arr,int,插入排序,元素,算法,深入,key,排序
From: https://blog.51cto.com/u_16170163/7443146

相关文章

  • Lnton羚通机器视觉算法平台运用Yolov8检测矿山传送带下大块煤、料口堵塞算法分析
    Lnton羚通的算法算力云平台具有突出的特点,包括高性能、高可靠性、高可扩展性和低成本。用户可以通过该云平台获得高效、强大的算法计算服务,快速、灵活地执行各种复杂的计算模型和算法,涉及机器学习、人工智能、大数据分析和图像识别等广泛领域。此外,云平台还提供丰富的算法库和工具,......
  • 计算机视觉算法中的行人检测(Pedestrian Detection)
    计算机视觉算法中的行人检测(PedestrianDetection)引言随着计算机视觉技术的不断发展,行人检测在人工智能领域中变得越来越重要。行人检测是计算机视觉中的一个关键任务,它可以识别图像或视频中的行人并准确地将其标注出来。本文将介绍行人检测的基本原理以及一些常用的算法。行人检测......
  • 全球校园人工智能算法精英大赛-AIOT应用赛项官方报名通道
    2023全球校园人工智能算法精英大赛AIOT应用赛项大幕拉开!参赛报名官方通道正式开启!关于赛项:“AIOT+行业”科技创新类竞赛,面向全球高校在校学生。AIOT应用赛项是全球校园人工智能算法精英大赛的重要赛项之一,由航天科技控股集团股份有限公司智慧物联事业部主办的面向全球高校各专......
  • C++算法之旅、06 基础篇 | 第四章 动态规划 详解
    常见问题闫式DP分析法状态表示集合满足一定条件的所有方案属性集合(所有方案)的某种属性(Max、Min、Count等)状态计算(集合划分)如何将当前集合划分成多个子集合状态计算相当于集合的划分:把当前集合划分成若干个子集,使得每个子集的状态可以先算出来,从而推导当前......
  • Unity 性能优化之Shader分析处理函数 ShaderUtil.GetAvailableShaderCompilerPlatform
    Unity性能优化之Shader分析处理函数ShaderUtil.GetAvailableShaderCompilerPlatforms用法点击封面跳转到Unity国际版下载页面简介在Unity中,性能优化是游戏开发过程中非常重要的一环。其中,ShaderUtil.GetAvailableShaderCompilerPlatforms函数是一个内部函数,它可以帮助......
  • Unity 性能优化之Shader分析处理函数ShaderUtil.HasProceduralInstancing: 深入解析与
    Unity性能优化之Shader分析处理函数ShaderUtil.HasProceduralInstancing:深入解析与实用案例点击封面跳转到Unity国际版下载页面简介在Unity中,性能优化是游戏开发过程中非常重要的一环。其中,Shader的优化对于游戏的性能提升起着至关重要的作用。本文将深入解析Unity中的Sh......
  • 代码随想录算法训练营第五天
    代码随想录算法训练营第五天|LeetCode242(有效的字母异位词)LeetCode349(两个数组的交集)LeetCode202(快乐数)LeetCode1(两数之和)242:有效的字母异位词LeetCode242(有效的字母异位词)classSolution{publicbooleanisAnagram(Strings,Stringt){......
  • SWUST 算法分析与设计 实验报告1
    Lockerdoors实验报告 一、     实验内容及目的实验内容:有一组数从1~n。从1开始,访问第i个数和它的倍数。以此类推。当i=n结束时,求有多少个数的访问次数为奇数。实验目的:验证不同的算法,在不同的数据规模的情况下,运行时间的变化情况,绘制成曲线图,比较算法的优劣性。体......
  • 《Hello 算法》个人笔记
    https://www.hello-algo.com/算法算法在日常生活中无处不在,并不是遥不可及的高深知识。实际上,我们已经在不知不觉中学会了许多算法,用以解决生活中的大小问题。查阅字典的原理与二分查找算法相一致。二分查找算法体现了分而治之的重要算法思想。整理扑克的过程与插入排序算法......
  • Matlab 遗传算法优化极限学习机(GA-ELM)回归预测
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......