插入排序是一種簡單的排序演算法。 在此演算法中，將每個元素插入到排序數組中的適當位置。 這比其他排序演算法(如快速排序，合併排序等)效率低。
1. 技術
考慮有一個數組A，其元素將要排序。 最初，A[0]是排序集上的唯一元素。 在第1遍中，A[1]被放置在數組中的適當索引處。
在第2遍中，A[2]被放置在數組中的適當索引處。 同樣，在通過n-1中，A[n-1]被放置在其正確的索引中。
要將元素A[k]插入其正確的索引，需要將它與所有其他元素(即A[k-1]，A[k-2]等)進行比較，直到找到元素A[j]為止 ，A[j] <= A[k]。
從A[k-1]到A[j]的所有元素都需要移位，A[k]將移動到A[j + 1]。
2. 複雜度
| 複雜度 | 最好情況 | 平均情況 | 最差情況 |
|---|---|---|---|
| 時間 | Ω(n) | θ(n^2) | θ(n^2) |
| 空間 | - | - | o(1) |
3. 演算法
第1步 : 重複第2步到第5步：由 K = 1 到 N-1
第2步 : 設置 TEMP = ARR[K]
第3步 : 設置 J = K ? 1
第4步 : 當 TEMP <=ARR[J] 時，迴圈執行
設置 ARR[J + 1] = ARR[J]
設置 J = J ? 1
[結束內迴圈]
第5步 : 設置 ARR[J + 1] = TEMP
[結束迴圈]
第6步: 退出
插入排序演算法使用C語言實現，代碼如下所示 -
#include<stdio.h>
void main ()
{
int i,j, k,temp;
int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
printf("printing sorted elements...\n");
for(k=1; k<10; k++)
{
temp = a[k];
j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
for(i=0;i<10;i++)
{
printf("\n%d\n",a[i]);
}
}
執行上面示例代碼，得到以下結果：
Printing Sorted Elements . . .
7
9
10
12
23
23
34
44
78
101
插入排序演算法使用C++語言實現，代碼如下所示 -
#include<iostream>
using namespace std;
int main ()
{
int i,j, k,temp;
int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
cout<<"\nprinting sorted elements...\n";
for(k=1; k<10; k++)
{
temp = a[k];
j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
for(i=0;i<10;i++)
{
cout <<a[i]<<"\n";
}
}
執行上面示例代碼，得到以下結果：
printing sorted elements...
7
9
10
12
23
23
34
44
78
101
插入排序演算法使用Java語言實現，代碼如下所示 -
public class InsertionSort {
public static void main(String[] args) {
int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
for(int k=1; k<10; k++)
{
int temp = a[k];
int j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
System.out.println("printing sorted elements ...");
for(int i=0;i<10;i++)
{
System.out.println(a[i]);
}
}
}
執行上面示例代碼，得到以下結果：
Printing sorted elements . . .
7
9
10
12
23
23
34
44
78
101
插入排序演算法使用C#語言實現，代碼如下所示 -
using System;
public class Program
{
public static void Main()
{
int i,j, k,temp;
int[] a = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
Console.WriteLine("printing sorted elements...\n");
for(k=1; k<10; k++)
{
temp = a[k];
j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
for(i=0;i<10;i++)
{
Console.WriteLine(a[i]);
}
}
}
執行上面示例代碼，得到以下結果：
printing sorted elements . . .
7
9
10
12
23
23
34
44
78
101
插入排序演算法使用Python語言實現，代碼如下所示 -
a=[10, 9, 7, 101, 23, 44, 12, 78, 34, 23]
for k in range(1,10):
temp = a[k]
j = k-1
while j>=0 and temp <=a[j]:
a[j+1]=a[j]
j = j-1
a[j+1] = temp
print("printing sorted elements...")
for i in a:
print(i)
執行上面示例代碼，得到以下結果：
printing sorted elements . . .
7
9
10
12
23
23
34
44
78
101
插入排序演算法使用Swift語言實現，代碼如下所示 -
import Foundation
import Glibc
var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];
print("printing sorted elements...\n");
for k in 1...9
{
let temp = a[k];
var j = k-1;
while j>=0 && temp <= a[j]
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
for i in a
{
print(i);
}
執行上面示例代碼，得到以下結果：
printing sorted elements...
7
9
10
12
23
23
34
44
78
101
插入排序演算法使用Javascript語言實現，代碼如下所示 -
var txt = "<br>";
var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];
document.writeln("printing sorted elements ... "+txt);
for(k=0;k<10;k++)
{
var temp = a[k]
j=k-1;
while (j>=0 && temp <= a[j])
{
a[j+1] = a[j];
jj = j-1;
}
a[j+1] = temp;
}
for(i=0;i<10;i++)
{
document.writeln(a[i]);
document.writeln(txt);
}
執行上面示例代碼，得到以下結果：
printing sorted elements ...
7
9
10
12
23
23
34
44
78
101
插入排序演算法使用PHP語言實現，代碼如下所示 -
<?php
$a = array(10, 9, 7, 101, 23, 44, 12, 78, 34, 23);
echo("printing sorted elements ... \n");
for($k=0;$k<10;$k++)
{
$temp = $a[$k];
$j=$k-1;
while ($j>=0 && $temp <= $a[$j])
{
$a[$j+1] = $a[$j];
$j = $j-1;
}
$a[$j+1] = $temp;
}
for($i=0;$i<10;$i++)
{
echo $a[$i];
echo "\n";
}
?>
執行上面示例代碼，得到以下結果：
printing sorted elements ...
7
9
10
12
23
23
34
44
78
101