(精华)2020年8月28日 数据结构与算法解析(插入排序-简单插入排序)

举报
愚公搬代码 发表于 2021/10/19 00:40:35 2021/10/19
【摘要】 1、插入排序(Insertion Sort) 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到...

1、插入排序(Insertion Sort)

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

1.1 算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5。

1.2 动图演示

在这里插入图片描述

1.3 代码实现

/// <summary>
/// 简单插入排序
/// </summary>
public class Program {

    public static void Main(string[] args) {
        int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
        StraightInsertionSort(array);
        ShowSord(array);

        Console.ReadKey();
    }

    private static void ShowSord(int[] array) {
        foreach (var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    public static void StraightInsertionSort(int[] array) {
        for (int i = 1; i < array.Length; i++) {
            int sentinel = array[i];
            int j = i - 1;
            while (j >= 0 && sentinel < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = sentinel;
        }
    }

}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

1.4 算法分析

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

文章来源: codeboy.blog.csdn.net,作者:愚公搬代码,版权归原作者所有,如需转载,请联系作者。

原文链接:codeboy.blog.csdn.net/article/details/108203230

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。