Démonstration animée du tri par insertion directe

插入排序 是一种简单的排序算法，其工作原理类似于对手中的扑克牌进行排序。该数组实际上分为已排序部分和未排序部分。未排序部分的值被拾取并放置在已排序部分的正确位置。

插入排序算法

要按升序对大小为 N 的数组进行排序，请迭代数组并将当前元素（键）与其前一个元素进行比较，如果键元素小于其前一个元素，则将其与之前的元素进行比较。将较大的元素向上移动一位，为交换的元素腾出空间。

插入排序算法的工作原理

考虑一个例子： arr[]: {12, 11, 13, 5, 6}

12    11    13    5    6

第一关：

最初，在插入排序中比较数组的前两个元素。

12    11    13    5    6

这里，12 大于 11，因此它们不是按升序排列的，并且 12 也没有处于正确的位置。因此，交换 11 和 12。

因此，目前 11 存储在已排序的子数组中。

11    12    13    5    6

第二遍：

现在，转到接下来的两个元素并比较它们

11    12    13    5    6

这里，13大于12，因此两个元素看起来都是升序的，因此不会发生交换。 12 也与 11 一起存储在已排序的子数组中

第三遍：

现在，已排序的子数组中存在两个元素： 11 和 12

继续看接下来的两个元素，即 13 和 5

11    12    13    5    6

5 和 13 都没有出现在正确的位置，所以交换它们

11    12    5    13    6

交换后，元素12和5未排序，因此再次交换

11    5    12    13    6

这里，11 和 5 再次没有排序，因此再次交换

5    11    12    13    6

这里，5 处于正确的位置

第四遍：

现在，排序后的子数组中存在的元素是 5、11 和 12

移至接下来的两个元素 13 和 6

5    11    12    13    6

显然，它们没有排序，因此在两者之间执行交换

5    11    12    6    13

现在，6 小于 12，因此，再次交换

5    11    6    12    13

在这里，交换也使得 11 和 6 未排序，因此，再次交换

5    6    11    12    13

最后，数组完全排序。

插图：

12	11	13	5	6

11	12	13	5	6

11	12	13	5	6

11	12	13	5	6

11	12	5	13	6

11	5	12	13	6

5	11	12	13	6

5	11	12	13	6

5	11	12	6	13

5	11	6	12	13

5	6	11	12	13

插入排序算法的实现

下面是迭代方法的实现：

C++

              
                
                    // C++ program for insertion sort
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort an array using
// insertion sort
void insertionSort(int arr[], int n)
{
    int
                          i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
 
        // Move elements of arr[0..i-1],
        // that are greater than key, 
        // to one position ahead of their
        // current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
 
// A utility function to print an array
// of size n
void printArray(int arr[], int n)
{
    int
                          i;
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
// Driver code
int main()
{
    int
                          arr[] = { 12, 11, 13, 5, 6 };
    int
                          N = sizeof(arr) / sizeof(arr[0]);
 
    insertionSort(arr, N);
    printArray(arr, N);
 
    return 0;
}
// This is code is contributed by rathbhupendra

                  

              
            

C

              
                
                    // C program for insertion sort
#include <math.h>
                        
#include <stdio.h>
                        
 
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
    int
                          i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
 
        /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
 
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
    int
                          i;
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
/* Driver program to test insertion sort */
int main()
{
    int
                          arr[] = { 12, 11, 13, 5, 6 };
    int
                          n = sizeof(arr) / sizeof(arr[0]);
 
    insertionSort(arr, n);
    printArray(arr, n);
 
    return 0;
}

                  

              
            

Java

              
                
                    // Java program for implementation of Insertion Sort
public class InsertionSort {
    /*Function to sort array using insertion sort*/
    void
                          sort(int arr[])
    {
        int n = arr.length;
        for (int
                          i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
 
            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
                        
        }
    }
 
    /* A utility function to print array of size n*/
    static
                          void printArray(int arr[])
    {
        int n = arr.length;
        for (int
                          i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
 
        System.out.println();
    }
 
    // Driver method
    public
                          static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6 };
 
        InsertionSort ob = new InsertionSort();
        ob.sort(arr);
 
        printArray(arr);
    }
};
 
 
/* This code is contributed by Rajat Mishra. */

                  

              
            

Python

              
                    # Python program for implementation of Insertion Sort
 
# Function to do insertion sort
def insertionSort(arr):
 
    # Traverse through 1 to len(arr)
    for
                          i in range(1, len(arr)):
                        
        key = arr[i]
                        
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=
                          0 and key < arr[j] :
                arr[j + 1] = arr[j]
                        
                j -= 1
        arr[j + 1] = key
 
# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
    print
                          ("% d" %
                          arr[i])
 
# This code is contributed by Mohit Kumra

C＃

              
                
                    // C# program for implementation of Insertion Sort
using System;
 
class InsertionSort {
 
    // Function to sort array
    // using insertion sort
    void
                          sort(int[] arr)
    {
        int n = arr.Length;
        for (int
                          i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;
 
            // Move elements of arr[0..i-1],
            // that are greater than key,
            // to one position ahead of
            // their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
 
    // A utility function to print
    // array of size n
    static
                          void printArray(int[] arr)
    {
        int n = arr.Length;
        for (int
                          i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
 
        Console.Write("\n");
    }
 
    // Driver Code
    public
                          static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6 };
        InsertionSort ob = new InsertionSort();
        ob.sort(arr);
        printArray(arr);
    }
}
 
// This code is contributed by ChitraNayal.

                  

              
            

PHP

              
                
                    <?php 
// PHP program for insertion sort
 
// Function to sort an array
                        
// using insertion sort
                        
function insertionSort(&$arr, $n)
{
    for
                          ($i = 1; $i < $n; $i++)
    {
        $key = $arr[$i];
        $j = $i-1;
     
        // Move elements of arr[0..i-1],
        // that are    greater than key, to 
        // one position ahead of their 
        // current position
        while ($j
                          >= 0 && $arr[$j] > $key)
                        
        {
            $arr[$j
                          + 1] = $arr[$j];
            $j = $j
                          - 1;
        }
         
        $arr[$j
                          + 1] = $key;
    }
}
 
// A utility function to
                        
// print an array of size n
function printArray(&$arr, $n)
{
    for
                          ($i = 0; $i < $n; $i++)
        echo $arr[$i]." ";
    echo
                          "\n";
}
 
// Driver Code
$arr = array(12, 11, 13, 5, 6);
$n = sizeof($arr);
insertionSort($arr, $n);
printArray($arr, $n);
 
// This code is contributed by ChitraNayal.
?>

                  

              
            

JavaScript

              
                
                    <script>
// Javascript program for insertion sort  
   
                        
// Function to sort an array using insertion sort
function insertionSort(arr, n)  
{  
    let i, key, j;  
    for
                          (i = 1; i < n; i++) 
    {  
                        
        key = arr[i];  
        j = i - 1;  
   
                        
        /* Move elements of arr[0..i-1], that are  
        greater than key, to one position ahead  
        of their current position */
        while (j >= 0 && arr[j] > key) 
        {  
            arr[j + 1] = arr[j];  
            j = j - 1;  
        }  
        arr[j + 1] = key;  
    }  
                        
}  
   
                        
// A utility function to print an array of size n  
function printArray(arr, n)  
{  
    let i;  
    for
                          (i = 0; i < n; i++)  
        document.write(arr[i] + " ");  
    document.write("<br>"); 
}  
   
                        
// Driver code 
    let arr = [12, 11, 13, 5, 6 ];  
    let n = arr.length;  
   
                        
    insertionSort(arr, n);  
    printArray(arr, n);  
     
// This code is contributed by Mayank Tyagi
   
                        
</script>

                  

              
            

输出

5 6 11 12 13

时间复杂度： O(N^2)
辅助空间： O(1)

插入排序的复杂度分析：

插入排序的时间复杂度

插入排序 最坏情况的 时间复杂度是 O(N^2)
插入排序的 平均情况 时间复杂度为 O(N^2)
最好情况 的时间复杂度是 O(N) 。

插入排序的空间复杂度

插入排序的辅助空间复杂度为 O(1)

插入排序的特点

该算法是最简单的算法之一，实现也简单
基本上，插入排序对于小数据值是有效的
插入排序本质上是自适应的，即它适用于已经部分排序的数据集。

有关插入排序的常见问题

Q1. 插入排序算法的边界情况是什么？

如果元素按逆序排序，插入排序将花费最大时间进行排序。当元素已经排序时，它需要最少的时间（n 的顺序）。

Q2。插入排序算法的算法范式是什么？

插入排序算法遵循增量方法。

Q3。插入排序是就地排序算法吗？

是的，插入排序是一种就地排序算法。

Q4。插入排序是一种稳定的算法吗？

是的，插入排序是一种稳定的排序算法。

Q5. 什么时候使用插入排序算法？

当元素数量较少时，使用插入排序。当输入数组几乎已排序并且完整的大数组中只有少数元素被放错位置时，它也很有用。