插入排序算法
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到
记载
最早拥有排序概念的机器出现在1901至1904年间由赫尔曼·何乐礼发明出使用基数排序法的分类机，此机器系统包括打孔，制表等功能，1908年分类机第一次应用于人口普查，并且在两年内完成了所有的普查数据和归档。 赫尔曼·何乐礼在1896年创立的分类机公司的前身，为电脑制表记录公司（CTR）。他在电脑制表记录公司曾担任顾问工程师，直到1921年退休，而电脑制表记录公司在1924年正式改名为 IBM。
概述
Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。
举例：
Input: {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
可以采用二分查找法来减少“比较操作”的数目，而由于“交换操作”的数目不变，算法的时间复杂度依旧为
动图演示
下面的动图演示了使用插入排序对一个数字序列 6, 5, 3, 1, 8, 7, 2, 4 进行排序的过程
示例代码
C 语言
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;
}
C++
void insertion_sort(int arr[],int len){
for(int i=1;i<len;i++){
int key=arr[i];
int j=i-1;
while((j>=0) && (key<arr[j])){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
C#
public static void InsertSort(int[] array)
{
for(int i = 1;i < array.length;i++)
{
int temp = array[i];
for(int j = i - 1;j >= 0;j--)
{
if(array[j] > temp)
{
array[j + 1] = array[j];
array[j] = temp;
}
else
break;
}
}
}
PASCAL
程序使用链表做插入排序，目的：将读入的英文名字按字母排列
TYPE
link=^node;
node=record
data:string;
next:link;
end;
VAR
p,q,head,n:link;
t,m:integer;
f1,f2:text;
i:string;
BEGIN
assign(f1,'lianbiao-name-in.txt');
reset(f1);
assign(f2,'lianbiao-name-out.txt');
rewrite(f2);
head:=nil;
read(f1,t);
readln(f1);
read(f1,i);
new(p);
p^.data:=i;
p^.next:=nil;
head:=p;
readln(f1);
read(f1,i);
FOR m:=2 TO t DO
BEGIN
p:=head;
new(n);
n^.data:=i;
while (i>p^.data) and (p^.next<>nil) do
begin
q:=p;
p:=p^.next;
end;
if i<head^.data then begin
n^.next:=head;
head:=n;
end
else if (i>p^.data) and (p^.next=nil) then begin
p^.next:=n;
n^.next:=nil;
end
else begin
q^.next:=n;
n^.next:=p;
end;
readln(f1);
read(f1,i);
end;
p:=head;
while p<>nil do
begin
write(f2,p^.data,' ');
p:=p^.next;
end;
CLOSE(f1);
CLOSE(f2);
END.
Ruby
def insert_sort(lst)
n = lst.size
return lst if n == 1
(1...n).each do |i|
i.downto(1).each do |j|
if lst[j] < lst[j-1]
lst[j], lst[j-1] = lst[j-1], lst[j]
else
break
end
end
end
lst
end
Ruby 的另一个版本
def insertion_sort(lst)
(1...lst.size).each do |i|
temp = lst[i]
j = i - 1
while j >= 0 and temp < lst[j]
lst[j + 1] = lst[j]
j -= 1
end
lst[j + 1] = temp
end
lst
end
Python
def insert_sort(lst):
n = len(lst)
if n == 1: return lst
for i in range(1,n):
for j in range(i, 0, -1):
if lst[j] < lst[j-1]:
lst[j], lst[j-1] = lst[j-1], lst[j]
else:
break
return lst
Python 的另一个版本
def insertion_sort(lst):
for i in range(1, len(lst)):
temp = lst[i]
j = i - 1
while j >= 0 and temp < lst[j]:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = temp
return lst
Java
public void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}
Java 的另一个版本
//将arr[i] 插入到arr[0]...arr[i - 1]中
public static void insertion_sort(int[] arr) {
for (int i = 1; i < arr.length; i++ ) {
int temp = arr[i];
int j = i - 1;
//如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
for (j >= 0 && arr[j] > temp; j-- ) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
JavaScript
Array.prototype.insertion_sort = function()
{
var i,j;
for(i = 1;i < this.length; i++){
for(j = 0;j<i;j++){
if(this[j]>this[i]){
this.splice(j,0,this[i]);
this.splice(i+1,1);
break;
}
}
}
return this;
};
用法示例：[3,5,2,11,1,2,"abc","zfd","sad","eng"].insertion_sort();
PHP
function insertion_sort(&$arr)
{
//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
for ($i = 1; $i < count($arr); $i++)
{
if ($arr[$i-1] > $arr[$i]) {
$temp = $arr[$i];
for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--)
$arr[$j + 1] = $arr[$j];
$arr[$j + 1] = $temp;
}
}
}
Rust
fn insert_sort<T>(list: &mut Vec<T>)
where T: PartialOrd + Copy{
let mut i = 0;
while i < list.len()-1 {
let mut j = i + 1;
while j > 0 {
if list[j] > list[j-1] {break;}
let temp = list[j-1];
list[j-1] = list[j];
list[j] = temp;
j -= 1;
}
i += 1;
}
}
用法示例： let mut a: Vec<i32> = vec![5,8,3,9,1,0]; insert_sort(&mut a);
Go
package main
import (
"fmt"
)
func InsertSort(array []int) {
n := len(array)
if n < 2 {
return
}
for i := 1; i < n; i++ {
for j := i - 1; j >= 0; j-- {
if array[j] > array[j+1] {
array[j], array[j+1] = array[j+1],array[j]
}else{
break
}
}
}
}
func main() {
array := []int{
55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9,
}
fmt.Println(array)
InsertSort(array)
fmt.Println(array)
}
Swift
//Swift 5.0
func insertionSort(_ arr:[Int]) -> [Int] {
if arr.count<=1 {return arr}
var sortedArr = arr
var tempInt:Int
for i in 0..<arr.count {
tempInt = sortedArr[i]
for j in stride(from: i, to: -1, by: -1){
if tempInt < sortedArr[j]{
sortedArr.remove(at: j + 1)
sortedArr.insert(tempInt, at: j)
}
}
}
return sortedArr
}
let array = [55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9]
print(array)
print(insertionSort(array))
算法复杂度
如果目标是把
