算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

这篇具有很好参考价值的文章主要介绍了算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 插入排序(insertion-sort):

                                          是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入

    算法稳定性:

                        对于两个相同的数,经过排序后,他们依旧保持之前的顺序,二者次序没有发生变化。插入排序是算法稳定的

   时间复杂度

        最优情况

                      在插入排序中,当待排序数组是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较N- 1次,时间复杂度为O(n)

        最坏情况

                          最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为O() 

     动态图

算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十),数据结构与算法,算法,排序算法,数据结构

  递归代码:文章来源地址https://www.toymoban.com/news/detail-697027.html

package com.nami.algorithm.study.day06;

import java.util.Arrays;

/**
 * beyond u self and trust u self.
 *
 * @Author: lbc
 * @Date: 2023-09-05 15:36
 * @email: 594599620@qq.com
 * @Description: keep coding
 */
public class InsertionSort {

    /**
     * 插入排序:
     * 从右向左找
     *
     * @param target
     */
    public static void sort(int[] target) {
        insertion(target, 1);
    }

    /**
     * 递归 缩小结果集
     *
     * @param target
     * @param lowIndex
     */
    private static void insertion(int[] target, int lowIndex) {
        if (lowIndex == target.length) {
            return;
        }

        int t = target[lowIndex];
        // 已排序区域指针
        int i = lowIndex - 1;
        // 没有找到插入位置
        while (i >= 0 && target[i] > t) {
            target[i + 1] = target[i];
            i--;

            // 如果到达数组0时候 依旧没有找到,则退出循环
            // 抽出,合并到while内
//            if(i < 0) {
//                break;
//            }
        }
        //插入位置找到了
        // 优化减少不必要的赋值动作,
        // 需要替换的数组值,正好是大于i, i+1索引的值不需要动,这个赋值动作就不必要了
        if (i + 1 != lowIndex) {
            target[i + 1] = t;
        }
        insertion(target, lowIndex + 1);
    }

    /**
     * 两种写法,这种赋值次数更多
     * 时间复杂度相同
     * 但是 效率没有上面的高,消耗在更多的赋值操作上了
     *
     * @param target
     * @param lowIndex
     */
    private static void insertion0(int[] target, int lowIndex) {
        if (lowIndex == target.length) {
            return;
        }

        // 已排序区域指针
        int i = lowIndex - 1;
        // 没有找到插入位置
        while (i >= 0 && target[i] > target[i + 1]) {
            int temp = target[i];
            target[i] = target[i + 1];
            target[i + 1] = temp;
            i--;

        }
        insertion(target, lowIndex + 1);
    }

    public static void main(String[] args) {
        int[] test = new int[]{1, 54, 234, 675, 32432, 23, 78, 459, 354, 9, 344, 22, 46, 85, 236, 3278, 245, 83, 154, 2, 1, 34, 73, 23};
        int[] test2 = new int[]{2, 4, 7, 3, 2, 1};
//        sort(test, test.length);
        sort(test);
        System.out.println(Arrays.toString(test));
    }


}

到了这里,关于算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法:插入排序&希尔排序

    假设现在你有一个有序的数组,你要把一个数据插入到数组中,保证插入后依然有序,要怎么做? 对于人来说,这个问题就像是在整理扑克牌,瞄一眼就知道应该插入什么位置。但是对于程序来说,就需要一一对比,直到找到一个位置 左边比它大,右边比它小 ,就算找到了

    2024年01月17日
    浏览(55)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中,排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下,排序算法可以分为两类,即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序,适用于数据量较小的情况,而

    2024年02月08日
    浏览(60)
  • 数据结构算法--2 冒泡排序,选择排序,插入排序

    思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。 这时冒泡排序第一轮结束,数列最右侧元素9的位置可认为是一个有序区,有序区目前有一个元素. 第二轮排序

    2024年02月13日
    浏览(62)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(81)
  • 【数据结构与算法】插入排序和希尔排序

      目录 一.插入排序  InsertSort 基本思想 动图演示  特性总结 二.希尔排序  ShellSort 基本思想 图例 特性总结 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。 当插入第i(i=1)个元素

    2023年04月18日
    浏览(86)
  • 【数据结构与算法】:插入排序与希尔排序

    🔥 个人主页 : Quitecoder 🔥 专栏 : 数据结构与算法 欢迎大家来到初阶数据结构的最后一小节:排序 排序是一种将一组对象按照某种特定顺序重新排列的过程。在计算机科学中,排序是数据处理中非常基本且重要的操作,它可以帮助人们更有效地理解和分析数据。排序的顺序

    2024年03月18日
    浏览(38)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(66)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(52)
  • 【数据结构与算法】直接插入排序和希尔排序

    进入了初阶数据结构的一个新的主题——排序。所谓排序,就是一串记录, 按照其中的某几个或某些的大小(一定的规则) , 递增或递减排列起来的操作 。 排序的 稳定性 :在一定的规则下,两个值相等的元素,在排序算法处理前后的相对位置是否发生变化,如果相

    2024年04月13日
    浏览(41)
  • 【数据结构】排序算法(一)—>插入排序、希尔排序、选择排序、堆排序

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.直接插入排序 2.希尔排序 3.直接选择排序 4.堆排序 本篇文章博主将介绍排序算法中的插入排序:直接

    2024年02月08日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包