本文概述
- 技术
- 复杂
- 算法
- C程序
- C ++程序
- Java程序
- C#程序
- Python程序
- 迅捷程序
- JavaScript程序
- PHP程序
技术考虑一个数组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:退出
#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
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("\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
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
迅捷程序
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
101
JavaScript程序
<
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
101
PHP程序
<
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