插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 � ( 1 ) {\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

目录 1 记载 2 概述 3 算法 4 示例代码 4.1 Julia (编程语言) 5 算法复杂度 6 参考文献 7 延伸阅读记载最早拥有排序概念的机器出现在1901至1904年间由赫尔曼·何乐礼发明出使用基数排序法的分类机，此机器系统包括打孔，制表等功能，1908年分类机第一次应用于人口普查，并且在两年内完成了所有的普查数据和归档。赫尔曼·何乐礼在1896年创立的分类机公司的前身，为电脑制表记录公司（CTR）。他在电脑制表记录公司曾担任顾问工程师，直到1921年退休，而电脑制表记录公司在1924年正式改名为IBM。

概述 Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。

举例：

输入： {5 2 4 6 1 3}。

首先拿起第一张牌, 手上有 {5}。

拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。

拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。

以此类推。

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

从第一个元素开始，该元素可以认为已经被排序取出下一个元素，在已经排序的元素序列中从后向前扫描如果该元素（已排序）大于新元素，将该元素移到下一位置重复步骤3，直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5 示例代码此范例程序以C语言实现。[1]

void insertion_sort(int arr[], int len){ int i,j,key; for (i=1;i!=len;++i){ key = arr[i]; j=i-1; while((j>=0) && (arr[j]>key)) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; } } 此范例程序以Objective C实现。[1]

(NSMutableArray *)insertionSort:(NSArray *)array { NSMutableArray *sortArray = [array mutableCopy]; NSNumber *key = @(0); int j = 0; for (int i = 1; i < sortArray.count; i++) { key = array[i]; j = i - 1; while ((j >= 0) && [sortArray[j] integerValue] > [key integerValue]) { sortArray[j + 1] = sortArray[j]; j --; } sortArray[j + 1] = key; } return sortArray; } Julia (编程语言)

Julia Sample : InsertSort

function InsertSort(A) for i=2:length(A) key = A[i] j=i-1 while (j>=1)&&(A[j]>key) A[j+1]=A[j] j-=1 end A[j+1]=key end return A end

Main Code

A = [16,586,1,31,354,43,3] println(A) # Original Array println(InsertSort(A)) # Insert Sort Array 算法复杂度如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需 � − 1 {\displaystyle n-1}次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有 1 2 � ( � − 1 ) {\displaystyle {\frac {1}{2}}n(n-1)}次。插入排序的赋值操作是比较操作的次数减去 � − 1 {\displaystyle n-1}次，（因为 � − 1 {\displaystyle n-1}次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。平均来说插入排序算法复杂度为 � ( � 2 ) O(n^{2})。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: