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)
算法步骤
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
.png?table=block&id=0af3d43f-8aae-4c4a-b6c8-7266fccd6991&width=800&t=0aa172ae-180c-4cc6-b47f-3ccb84e7c8d8&cache=v2)
【概念解析】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 许可协议，转载请注明出处。