type
status
date
slug
summary
tags
category
icon
password
整理定义
中文名称:插入排序
英文名称:insertion sort
出处 | 定义 |
一种简单的排序算法。算法将待排序的数据分成两个区域:有序区和无序区,每次将一个无序区的数据按其大小插入到有序区中的适当位置,直到所有无序区中的数据都插入完成为止 | |
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
【插入排序是一种简单的排序算法,通过比较一次构建最终的排序数组(或列表)。 它在大型列表上的效率比更高级的算法(例如快速排序、堆排序或合并排序)低得多。】 | |
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 |
复述展开
插入排序 (Insertion Sort)
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2Fdea38628-64dc-40fd-8d17-2efa87e3d554%2Fd6d0b359-962f-4af2-b0e4-abcd4de25827%2F%25E6%258F%2592%25E5%2585%25A5%25E6%258E%2592%25E5%25BA%258F_%25E5%258E%258B%25E7%25BC%25A9.gif?table=block&id=f6fe6114-19fb-41f4-a101-06e53eb013dc&t=f6fe6114-19fb-41f4-a101-06e53eb013dc&width=420&cache=v2)
算法步骤
1.从第一个元素开始,该元素可以认为已经被排序;
2.取出下一个元素,在已经排序的元素序列中从后向前扫描;
3.如果该元素(已排序)大于新元素,将该元素移到下一位置;
4.重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置;
5.将新元素插入到该位置后;
6.重复步骤 2~5。
算法分析
稳定性:稳定
时间复杂度 :最佳:O(n) ,最差:O(n^2), 平均:O(n^2)
空间复杂度 :O(1)
排序方式 :In-place
代码分析
理解体会
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序在实现上,通常采用 in-place 排序(即只需用到 O(1) 的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。
插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
快速跳转链接
【概念解析】启动
【概念解析】Day 1 - 10
【概念解析】Day 11 - 20
【概念解析】Day 21 - 30
【概念解析】Day 31 - 40
【概念解析】Day 41 - 50
【概念解析】Day 51 - 60
【概念解析】Day 61 - 70
【概念解析】Day 71 - 80
【概念解析】Day 81 - 90
- 作者:eachenkuang
- 链接:https://kuangyichen.com/article/industry-day18
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。