算法實現/排序/插入排序

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

程式使用鍊表（linked list）做插入排序，目的：將讀入的英文名字按字母排列

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