算法实现/排序/插入排序
对整数数组进行排序。
type Integer_Array is array (Natural range <>) of Integer;
procedure Insertion_Sort (A : in out Integer_Array) is
Value : Integer;
J : Natural;
begin
for I in A'First + 1 .. A'Last loop
Value := A(I);
J := I - 1;
while J >= A'First and then A(J) > Value loop
A(J + 1) := A(J);
J := J - 1;
end loop;
A(J + 1) := Value;
end loop;
end Insertion_Sort;
Func insertionSort( ByRef $array )
For $i = 1 to Ubound( $array ) - 1
$j = $i - 1
$temp = $array[$i]
While ( $j >= 0 ) And ( $array[$j] > $temp )
$array[$j+1] = $array[$j]
$j -= 1
WEnd
$array[$j+1] = $temp
Next
EndFunc
在C中
#include <iostream>
using namespace std;
void insertSort(int a[], int length)
{
int i, j, value;
for(i = 0 ; i < length ; i++)
{
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; j--)
a[j + 1] = a[j];
a[j+1] = value;
}
}
在C++中
#include <iostream>
using namespace std;
template<class Iterator>
void insertion_sort( Iterator a, Iterator end )
{
std::iter_swap( a, std::min_element( a, end ) );
for ( Iterator b = a; ++b < end; a = b )
for( Iterator c = b; *c < *a; --c, --a )
std::iter_swap( a, c );
}
在C++中，半插入排序
void halfInsertSort(int array[], int length)
{
int begin;
int end;
int middle;
int value;
for (int i = 1; i < length; ++i)
{
value = array[i];
begin = 0;
end = i - 1;
while (begin <= end)
{
middle = (begin + end) / 2;
if (value < array[middle])
{
end = middle - 1;
}
else
{
begin = middle + 1;
}
}
for (int j = i - 1; j >= begin; --j)
{
array[j + 1] = array[j];
}
array[begin] = value;
}
}
static void InsertSort(IComparable[] array)
{
int i, j;
for (i = 1; i < array.Length; i++)
{
IComparable value = array[i];
j = i - 1;
while ((j >= 0) && (array[j].CompareTo(value) > 0))
{
array[j + 1] = array[j];
j--;
}
array[j + 1] = value;
}
}
此示例对任何实现IComparable的类型T的列表进行排序。它演示了C# 2.0泛型，特别是“where”子句。
static void InsertSort<T>(IList<T> list) where T : IComparable<T>
{
int i, j;
for (i = 1; i < list.Count; i++)
{
T value = list[i];
j = i - 1;
while ((j >= 0) && (list[j].CompareTo(value) > 0))
{
list[j + 1] = list[j];
j--;
}
list[j + 1] = value;
}
}
let rec insertion_sort l =
match l with
| [] -> []
| (h::n) -> insert h (insertion_sort n)
and insert t l =
match l with
| [] -> [t]
| (h::n) -> if t > h then h::(insert t n)
else t::h::n ;;
Common Lisp
[编辑 | 编辑源代码](defun insert (target list)
(if (null list)
(cons target nil)
(if (<= target (first list))
(cons target list)
(cons (first list) (insert target (rest list))))))
(defun insertSort (myList)
(if (null myList)
nil
(insert (first myList) (insertSort (rest myList)))))
Fortran 90/95
[编辑 | 编辑源代码]此插入排序实现紧跟GPL FORTRAN 90/95 GPL库AFNL中的实现。
! ***********************************
! *
Subroutine Insrt(X, Ipt)
! *
! ***********************************
! * Sort Array X(:) in ascendent order.
! * If present Ipt, a pointer with the
! * changes is returned in Ipt.
! ***********************************
Real (kind=4), Intent (inout) :: X(:)
Integer, Intent (out), Optional :: Ipt(:)
Real (kind=4) :: Rtmp
Integer :: I, J
If (Present(Ipt)) Then
Forall (I=1:Size(X)) Ipt(I) = I
Do I = 2, Size(X)
Rtmp = X(I)
Do J = I-1, 1, -1
If (Rtmp < X(J)) Then
X(J+1) = X(J)
CALL Swap(Ipt, J, J+1)
Else
Exit
End If
End Do
X(J+1) = Rtmp
End Do
Else
Do I = 2, Size(X)
Rtmp = X(I)
Do J = I-1, 1, -1
If (Rtmp < X(J)) Then
X(J+1) = X(J)
Else
Exit
End If
End Do
X(J+1) = Rtmp
End Do
End If
Return
End Subroutine Insrt
! ***********************************
! *
Subroutine Swap(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:).
! ***********************************
Integer, Intent (inout) :: X(:)
Integer, Intent (in) :: I, J
Integer :: Itmp
Itmp = X(I)
X(I) = X(J)
X(J) = Itmp
Return
End Subroutine Swap
let insertionSort l =
let rec insert x sortedList =
match sortedList with
| smallest :: sortedTail when smallest < x -> smallest :: insert x sortedTail
| _ -> x :: sortedList
List.foldBack insert l []
func InsertionSort(data []int) {
for i, v := range data {
j := i
for ;j > 0 && v < data[j - 1]; j-- {
data[j] = data[j - 1]
}
data[j] = v
}
}
public static void insertionsort(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
int copyNumber = numbers[i];
int j = i;
while (j > 0 && copyNumber < numbers[j-1]) {
numbers[j] = numbers[j-1];
j--;
}
numbers[j] = copyNumber;
}
}
另一种通用实现。
public static < E extends Comparable<? super E> > void insertSort( E[] comparable )
{
for ( int i = 1; i < comparable.length; i++ )
{
E value = comparable[i];
int j = i - 1;
while ( j >= 0 && comparable[j].compareTo( value ) > 0 )
{
comparable[j + 1] = comparable[j--];
}
comparable[j + 1] = value;
}
}
JavaScript
[编辑 | 编辑源代码]// Assumes all elements are non-null and non-undefined
function insertionSort(sortMe) {
for (var i = 0, j; i < sortMe.length; ++i) {
var tmp = sortMe[i];
for (var j = i - 1; j >= 0 && sortMe[j] > tmp; --j)
sortMe[j + 1] = sortMe[j];
sortMe[j + 1] = tmp;
}
}
import Data.List (insert)
insertsort :: Ord a => [a] -> [a]
insertsort = foldr insert []
let rec insert e = function
h::t when e <= h -> h :: insert e t
| l -> e :: l
let rec insertion_sort = function
[] -> []
| h::t -> insert h (insertion_sort t)
insert函数与上面的相同。
let rec insert e = function
h::t when e <= h -> h :: insert e t
| l ->
let insertion_sort xs = List.fold_right insert xs []
Procedure InsertionSort(var ArrayOfOrd: AnyOrdType);
var
Top, InsertionPos: integer;
Cache :string;
Begin
for Top := 1 to length(ArrayOfOrd) - 1 do
begin
Cache := ArrayOfOrd[Top];
InsertionPos := Top;
while (ArrayOfOrd[InsertionPos - 1] > Cache) and (InsertionPos > 0) do
begin
ArrayOfOrd[InsertionPos] := ArrayOfOrd[InsertionPos - 1];
dec(InsertionPos);
end;
ArrayOfOrd[InsertionPos] := Cache;
end;
End;
链表版本
procedure insertionSort(var L:PNode);
var h, x, xs, y, z:PNode;
begin
h := NIL;
x := L;
while x <> NIL do
begin
xs := x^.next;
y := h;
z :=NIL;
while (y <> NIL)and(x^.key > y^.key)do
begin
z := y;
y := y^.next;
end;
x^.next := y;
if z <> NIL then
z^.next := x
else
h := x;
x := xs;
end;
L := h;
end;
sub insert_sort {
for(my $i = 1; $i <= $#_; $i++) {
my ($j, $val) = ($i - 1, $_[$i]);
$_[$j-- + 1] = $_[$j] while ($j >= 0 && $_[$j] > $val);
$_[$j+1] = $val;
}
}
function insertion_sort(sequence s)
object temp
integer j
for i=2 to length(s) do
temp = s[i]
j = i-1
while j>=1 and s[j]>temp do
s[j+1] = s[j]
j -= 1
end while
s[j+1] = temp
end for
return s
end function
for ($j=1; $j < count($array); $j++) {
$temp = $array[$j];
$i = $j;
while (($i >= 1) && ($array[$i-1] > $temp)) {
$array[$i] = $array[$i-1];
$i--;
}
$array[$i] = $temp;
}
def insertsort(array):
for removed_index in range(1, len(array)):
removed_value = array[removed_index]
insert_index = removed_index
while insert_index > 0 and array[insert_index - 1] > removed_value:
array[insert_index] = array[insert_index - 1]
insert_index -= 1
array[insert_index] = removed_value
Standard ML
[编辑 | 编辑源代码]fun insertsort [] = []
| insertsort (x::xs) =
let fun insert (x:real, []) = [x]
| insert (x:real, y::ys) =
if x<=y then x::y::ys
else y::insert(x, ys)
in insert(x, insertsort xs)
end;
insert函数与上面的相同。
fun insert (x:real, []) = [x]
| insert (x, y::ys) =
if x <= y then x::y::ys
else y::insert(x, ys)
val insertion_sort = foldr insert []
它对原始数组进行排序。
def insert_sort!(list)
for i in 1..(list.length - 1)
value = list[i]
j = i - 1
while j >= 0 and list[j] > value
list[j + 1] = list[j]
j -= 1
end
list[j + 1] = value
end
end
在 Swift 中
func insertionSort<T: Comparable> (list: inout [T]) {
for i in 1..<list.count {
var j = i - 1
let x = list[i]
while 0 <= j && x < list[j] {
swap(&list[j+1], &list[j])
j -= 1
}
list[j+1] = x
}
}
C 原型是
void isort(int *a, int n)
汇编程序例程是
isort:
%define a [ebp + 8]
%define n [ebp + 12]
enter 0, 0
pusha
mov ecx, 1
for:
mov ebx, ecx
imul ebx, 4
add ebx, a
mov ebx, [ebx]
mov edx, ecx
dec edx
while:
cmp edx, 0
jl while_quit
mov eax, edx
imul eax, 4
add eax, a
cmp ebx, [eax]
jge while_quit
mov esi, [eax]
mov dword [eax + 4], esi
dec edx
jmp while
while_quit:
mov [eax], ebx
inc ecx
cmp ecx, n
jl for
popa
leave
ret
Public Sub InsertionSort(ByRef ArrayAngka() As Long)
Dim i, j As Integer
Dim t As Long
For i = 0 To (n - 1)
For j = i + 1 To 1 Step -1
If ArrayAngka(j) < ArrayAngka(j - 1) Then
Call tukar(ArrayAngka(j), ArrayAngka(j - 1))
End If
Next j
Next i
End Sub
Private Sub tukar(data1 As Long, data2 As Long)
Dim temp As Long
temp = data1
data1 = data2
data2 = temp
End Sub
这里有一些更快的代码。
Public Sub Insertionsort(nums() As Long)
Dim i&, j&, k&, length&
length = UBound(nums)
For i = 1 To length
j = nums(i)
k = i
Do While (k > 0) And (nums(k - 1) > j)
nums(k) = nums(k - 1)
k = k - 1
Loop
nums(k) = j
Next i
End Sub