伪代码
function insertionSort(array A)for i from 1 to length[A]-1 dovalue := A[i] j := i-1while j >= 0 and A[j] > value doA[j+1] := A[j]j := j-1doneA[j+1] = valuedone
ActionScript
function insertionSort(array:Array)
{for(var i:int = 1; i < array.length;i++){var value = array[i];var j:int = i-1;while(j >= 0 && array[j] > value){array[j+1] = array[j];j--;}array[j+1] = value;}return array;
}
BASIC
DECLARE SUB InsertionSort (theList() AS INTEGER)DIM n(10) AS INTEGER, L AS INTEGER, o AS STRING
FOR L = 0 TO 10n(L) = INT(RND * 32768)
NEXT
InsertionSort n()
FOR L = 1 TO 10PRINT n(L); ";";
NEXTSUB InsertionSort (theList() AS INTEGER)DIM insertionElementIndex AS INTEGERFOR insertionElementIndex = 1 TO UBOUND(theList)DIM insertionElement AS INTEGERinsertionElement = theList(insertionElementIndex)DIM j AS INTEGERj = insertionElementIndex - 1DO WHILE (j >= 0)'necessary for BASICs without short-circuit evaluationIF (insertionElement < theList(j)) THENtheList(j + 1) = theList(j)j = j - 1ELSEEXIT DOEND IFLOOPtheList(j + 1) = insertionElementNEXT
END SUB
C
#include <stdio.h>void insertion_sort(int *a, int n) {
for(size_t i = 1; i < n; ++i) {
int tmp = a[i];size_t j = i;while(j > 0 && tmp < a[j - 1]) {
a[j] = a[j - 1];--j;}a[j] = tmp;}
}
C++
#include <algorithm>
#include <iostream>
#include <iterator>template <typename RandomAccessIterator, typename Predicate>
void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end,Predicate p) {
for (auto i = begin; i != end; ++i) {
std::rotate(std::upper_bound(begin, i, *i, p), i, i + 1);}
}template <typename RandomAccessIterator>
void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end) {
insertion_sort(begin, end,std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}
C#
namespace Sort {
using System;static class InsertionSort<T> where T : IComparable {
public static void Sort(T[] entries) {
Sort(entries, 0, entries.Length - 1);}public static void Sort(T[] entries, Int32 first, Int32 last) {
for (var i = first + 1; i <= last; i++) {
var entry = entries[i];var j = i;while (j > first && entries[j - 1].CompareTo(entry) > 0)entries[j] = entries[--j];entries[j] = entry;}}}
}
Go
package mainimport "fmt"func insertionSort(a []int) {
for i := 1; i < len(a); i++ {
value := a[i]j := i - 1for j >= 0 && a[j] > value {
a[j+1] = a[j]j = j - 1}a[j+1] = value}
}func main() {
list := []int{
31, 41, 59, 26, 53, 58, 97, 93, 23, 84}fmt.Println("unsorted:", list)insertionSort(list)fmt.Println("sorted! ", list)
}
通用版本
package mainimport ("fmt""sort"
)func insertionSort(a sort.Interface) {
for i := 1; i < a.Len(); i++ {
for j := i; j > 0 && a.Less(j, j-1); j-- {
a.Swap(j-1, j)}}
}func main() {
list := []int{
31, 41, 59, 26, 53, 58, 97, 93, 23, 84}fmt.Println("unsorted:", list)insertionSort(sort.IntSlice(list))fmt.Println("sorted! ", list)
}
Groovy
def insertionSort = { list ->def size = list.size()(1..<size).each { i ->def value = list[i]def j = i - 1for (; j >= 0 && list[j] > value; j--) {print "."; list[j+1] = list[j]}print "."; list[j+1] = value}list
}
Java
public static void insertSort(int[] A){
for(int i = 1; i < A.length; i++){
int value = A[i];int j = i - 1;while(j >= 0 && A[j] > value){
A[j + 1] = A[j];j = j - 1;}A[j + 1] = value;}
}
JavaScript
function insertionSort (a) {
for (var i = 0; i < a.length; i++) {
var k = a[i];for (var j = i; j > 0 && k < a[j - 1]; j--)a[j] = a[j - 1];a[j] = k;}return a;
}var a = [4, 65, 2, -31, 0, 99, 83, 782, 1];
insertionSort(a);
document.write(a.join(" "));
Julia
# v0.6function insertionsort!(A::Array{T}) where T <: Numberfor i in 1:length(A)-1value = A[i+1]j = iwhile j > 0 && A[j] > valueA[j+1] = A[j]j -= 1endA[j+1] = valueendreturn A
endx = randn(5)
@show x insertionsort!(x)
Kotlin
fun insertionSort(array: IntArray) {
for (index in 1 until array.size) {
val value = array[index]var subIndex = index - 1while (subIndex >= 0 && array[subIndex] > value) {
array[subIndex + 1] = array[subIndex]subIndex--}array[subIndex + 1] = value}
}fun main(args: Array<String>) {
val numbers = intArrayOf(5, 2, 3, 17, 12, 1, 8, 3, 4, 9, 7)fun printArray(message: String, array: IntArray) = with(array) {
print("$message [")forEachIndexed {
index, number ->print(if (index == lastIndex) number else "$number, ")}println("]")}printArray("Unsorted:", numbers)insertionSort(numbers)printArray("Sorted:", numbers)
}
MATLAB / Octave
function list = insertionSort(list)for i = (2:numel(list))value = list(i);j = i - 1;while (j >= 1) && (list(j) > value)list(j+1) = list(j);j = j-1;endlist(j+1) = value;end %for
end %insertionSort
Perl
sub insertion_sort {
my (@list) = @_;foreach my $i (1 .. $#list) {
my $j = $i;my $k = $list[$i];while ( $j > 0 && $k < $list[$j - 1]) {
$list[$j] = $list[$j - 1];$j--;}$list[$j] = $k;}return @list;
}my @a = insertion_sort(4, 65, 2, -31, 0, 99, 83, 782, 1);
print "@a\n";
Perl 6
sub insertion_sort ( @a is copy ) {
for 1 .. @a.end -> $i {
my $value = @a[$i];my $j;loop ( $j = $i-1; $j >= 0 and @a[$j] > $value; $j-- ) {
@a[$j+1] = @a[$j];}@a[$j+1] = $value;}return @a;
}my @data = 22, 7, 2, -5, 8, 4;
say 'input = ' ~ @data;
say 'output = ' ~ @data.&insertion_sort;
PHP
function insertionSort(&$arr){
for($i=0;$i<count($arr);$i++){
$val = $arr[$i];$j = $i-1;while($j>=0 && $arr[$j] > $val){
$arr[$j+1] = $arr[$j];$j--;}$arr[$j+1] = $val;}
}$arr = array(4,2,1,6,9,3,8,7);
insertionSort($arr);
echo implode(',',$arr);
PowerShell
function insertionSort($arr){
for($i=0;$i -lt $arr.length;$i++){
$val = $arr[$i]$j = $i-1while($j -ge 0 -and $arr[$j] -gt $val){
$arr[$j+1] = $arr[$j]$j--}$arr[$j+1] = $val}
}$arr = @(4,2,1,6,9,3,8,7)
insertionSort($arr)
$arr -join ","
Python
def insertion_sort(l):for i in xrange(1, len(l)):j = i-1 key = l[i]while (l[j] > key) and (j >= 0):l[j+1] = l[j]j -= 1l[j+1] = key
R
insertionsort <- function(x)
{for(i in 2:(length(x))){value <- x[i]j <- i - 1while(j >= 1 && x[j] > value){x[j+1] <- x[j]j <- j-1}x[j+1] <- value}x
}
Ruby
class Arraydef insertionsort!1.upto(length - 1) do |i|value = self[i]j = i - 1while j >= 0 and self[j] > valueself[j+1] = self[j]j -= 1endself[j+1] = valueendselfend
end
ary = [7,6,5,9,8,4,3,1,2,0]
p ary.insertionsort!
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Rust
fn insertion_sort<T: std::cmp::Ord>(arr: &mut [T]) {for i in 1..arr.len() {let mut j = i;while j > 0 && arr[j] < arr[j-1] {arr.swap(j, j-1);j = j-1;}}
}
Swift
func insertionSort<T:Comparable>(inout list:[T]) {
for i in 1..<list.count {
var j = iwhile j > 0 && list[j - 1] > list[j] {
swap(&list[j], &list[j - 1])j--}}
}
更多代码，持续更新！
整理自网络。