文章目录

一：定义二：原理三：动态图演示，排序过程解释四：C# 代码实现五：多种编程语言实现插入排序（参考）1：Java 2：JavaScript 3：Python 4：PHP 5：GO

一：定义

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法 《百度百科》

二：原理

在排序前，先把“待排序列”拆分成“有序序列”与“无序序列”。将“待排序列”中的第一个元素，看做一个“有序序列”中的第一个元素，把“待排序列”中的第二个元素一直到最后一个元素，当成是“无序序列”。从头到尾依次扫描“未排序序列”，将扫描到的每个元素插入“有序序列”的适当位置。(如果待插入的元素与“有序序列”中的某个元素相等，则将待插入元素插入到相等元素的后面。)

三：动态图演示，排序过程解释

1、动态图演示： 2、排序过程解释：

一开始左端数字已经排序，数字 5 不动。然后取出剩余未操作的左端数字 3 ，将其与已经操作的左侧数字相比较，如果左边的数字较大，则交换两个数字，由于 5 大于 3，所以交换两个数字。重复此操作，直到出现一个较小的数字到达左端。数字 3 已经完成排序。接下来，和之前一样取出剩余未操作的左端数字 4 ，与其相邻的左边数字进行比较，由于 5 大于4，所以交换两个数字。继续操作，由于 3 小于 4，即出现了更小的数字，所以 4 停止移动，数字 4 已经完成排序。重复相同的操作，直到所有的数字完成排序。

四：C# 代码实现

namespace AlgorithmTest { class Program { static void Main(string[] args) { // 定义一个长度为12的数组 int[] array = new[]{ 3, 88, 15, 9, 2, 14, 12, 13, 56, 68, 33, 61 }; InsertionSort(array); Console.ReadKey(); } // 插入排序 static void InsertionSort(int[] array) { // 注意：这里的i是从1开始的 for (int i = 1; i < array.Length; ++i) { int value = array[i]; int j = 0; // 插入的位置 for (j = i - 1; j >= 0; j--) { // 自左向右依次递增 if (array[j] > value) { array[j + 1] = array[j]; // 移动数据 } else { break; } } array[j + 1] = value; // 插入数据 } // 打印输出结果 foreach (var item in array) { Console.Write(item+" "); } } } }

控制台输出结果如下所示 从代码里我们可以看出，如果找到了合适的位置，就不会再进行比较了，就好比牌堆里抽出的一张牌，本身就比我手里的牌都小，那么我只需要直接放在末尾就行了，不用一个一个去移动数据腾出位置插入到中间。

所以说，最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)，然而时间复杂度这个指标看的是最坏的情况，而不是最好的情况，所以插入排序的时间复杂度是 O(n2)。

五：多种编程语言实现插入排序（参考）

1：Java

public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int tmp = arr[i]; // 从已经排序的序列最右边的开始比较，找到比其小的数 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数，插入 if (j != i) { arr[j] = tmp; } } return arr; } }

2：JavaScript

function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current) { arr[preIndex+1] = arr[preIndex]; preIndex--; } arr[preIndex+1] = current; } return arr; }

3：Python

def insertionSort(arr): for i in range(len(arr)): preIndex = i-1 current = arr[i] while preIndex >= 0 and arr[preIndex] > current: arr[preIndex+1] = arr[preIndex] preIndex-=1 arr[preIndex+1] = current return arr

4：PHP

function insertionSort($arr) { $len = count($arr); for ($i = 1; $i < $len; $i++) { $preIndex = $i - 1; $current = $arr[$i]; while($preIndex >= 0 && $arr[$preIndex] > $current) { $arr[$preIndex+1] = $arr[$preIndex]; $preIndex--; } $arr[$preIndex+1] = $current; } return $arr; }

5：GO

func insertionSort(arr []int) []int { for i := range arr { preIndex := i - 1 current := arr[i] for preIndex >= 0 && arr[preIndex] > current { arr[preIndex+1] = arr[preIndex] preIndex -= 1 } arr[preIndex+1] = current } return arr }

声明： 一：博文中用到的动态效果图，录取自 vx 公众号《五分钟学算法》以及《程序员小灰》，对算法感兴趣的可以关注下。 二：文章思路开源项目地址，整理人 hustcc

---

结束语

如果这篇博客有幸帮到了您，欢迎点击下方链接，和更多志同道合的伙伴一起交流，一起进步。