插入排序是一种简单的排序算法。 在此算法中，将每个元素插入到排序数组中的适当位置。 这比其他排序算法(如快速排序，合并排序等)效率低。
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
