# 算法实现/排序/插入排序

### 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;
};
```

### 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;
}
}
```

### Go

```package main

import (
"fmt"
)

func InsertSort(array []int) {
for i := 1; i < n; i++ {
for j := i - 1; j >= 0 && array[j] > array[j+1]; j-- {
array[j], array[j+1] = array[j+1],array[j]
}
}
}

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))
```