插入排序

插入排序是一種簡單的排序演算法。 在此演算法中，將每個元素插入到排序陣列中的適當位置。 這比其他排序演算法(如快速排序，合併排序等)效率低。

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. 複雜度

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