srcmini本文概述
插入排序是一种简单的排序算法, 通常在日常生活中订购一副纸牌时使用。在此算法中, 我们将每个元素插入到已排序数组中的适当位置。这比其他排序算法（例如快速排序, 合并排序等）效率低。
技术
考虑一个数组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]。
复杂
| 复杂 | 最好的情况 | 平均情况 | 最差的情况 |
|---|---|---|---|
| Time | Ω(n) | θ(n2) | o(n2) |
| Space | o(1) |
算法
- 步骤1：对于K = 1到N-1, 重复步骤2到5
- 步骤2：SET TEMP = ARR [K]
- 步骤3：SET J = K-1
- 步骤4：在TEMP <= ARR [J]设置ARR [J +1] = ARR [J]设置J = J-1 [内部循环结束]时重复
- 第5步：设置ARR [J +1] = TEMP [LOOP LOOP]
- 步骤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("\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++)
{
printf("\n%d\n", a[i]);
}
}输出：
Printing Sorted Elements . . .
7
9
10
12
23
23
34
44
78
101C ++程序
#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
101Java程序
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
101C＃程序
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("\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++)
{
Console.WriteLine(a[i]);
}
}
}输出：
printing sorted elements . . .
7
9
10
12
23
23
34
44
78
101Python程序
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迅捷程序
import Foundation
import Glibc
var a = [10, 9, 7, 101, 23, 44, 12, 78, 34, 23];
print("\nprinting 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
101JavaScript程序
<html>
<head>
<title>
Insertion Sort
</title>
</head>
<body>
<script>
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];
j = j-1;
}
a[j+1] = temp;
}
for(i=0;i<10;i++)
{
document.writeln(a[i]);
document.writeln(txt);
}
</script>
</body>
</html>输出：
printing sorted elements ...
7
9
10
12
23
23
34
44
78
101PHP程序
<html>
<head>
<title>Insertion Sort</title>
</head>
<body>
<?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";
}
?>
</body>
</html>输出：
printing sorted elements ...
7
9
10
12
23
23
34
44
78
101
评论前必须登录！
注册