插入排序算法

插入排序是一种非常简单的按升序或降序对数字进行排序的方法。此方法遵循增量方法。它可以与玩游戏时对纸牌进行排序的技术进行比较。

这是一种基于就地比较的排序算法。其中，会维护一个始终处于排序状态的子列表。例如，数组的下半部分保持排序状态。要"插入"到这个已排序子列表中的元素，必须找到其合适的位置，然后将其插入到那里。因此得名插入排序。

按顺序搜索数组，并将未排序的项目移动并插入到已排序的子列表中（在同一个数组中）。该算法不适用于大型数据集，因为其平均和最坏情况复杂度均为 Ο(n²)，其中 n 为项目数。

插入排序算法

现在我们对这种排序技术的工作原理有了更全面的了解，因此我们可以推导出实现插入排序的简单步骤。

步骤 1 − 如果它是第一个元素，则表示它已经排序。return 1;

步骤 2 − 选择下一个元素

步骤 3 − 与已排序子列表中的所有元素进行比较

步骤 4 −将已排序子列表中所有大于待排序值的元素移位

步骤 5 − 插入值

步骤 6 − 重复此操作，直到列表排序完成

伪代码

Algorithm: Insertion-Sort(A)
for j = 2 to A.length
   key = A[j]
   i = j – 1
   while i > 0 and A[i] > key
      A[i + 1] = A[i]
      i = i -1
   A[i + 1] = key

分析

该算法的运行时间很大程度上取决于给定的输入。

如果给定的数字已排序，则该算法的运行时间为O(n)。如果给定的数字是逆序的，算法的运行时间为 O(n²)。

示例

我们以一个未排序的数组为例。

插入排序比较前两个元素。

它发现 14 和 33 都已经是升序的了。目前，14 在排序子列表中。

插入排序向前移动，比较 33 和 27。

发现 33 的位置不正确。它将 33 与 27 交换。同时，它还检查了排序子列表中的所有元素。这里我们看到排序后的子列表只有一个元素 14，而 27 大于 14。因此，交换后排序后的子列表仍然保持排序状态。

现在排序后的子列表中有 14 和 27。接下来，它将 33 与 10 进行比较。这两个值并非按排序顺序排列。

因此它们被交换了。

然而，交换后 27 和 10 就不再排序了。

因此，我们也交换它们。

我们再次找到未排序的 14 和 10。

我们再次交换它们。

第三次迭代结束时，我们得到了一个包含 4 个项目的排序子列表。

此过程持续进行，直到所有未排序的值都被一个已排序的子列表覆盖。现在我们将了解插入排序的一些编程方面。

实现

由于插入排序是一种就地排序算法，因此该算法的实现方式是：将关键元素（迭代地选择为数组中的每个元素）与其后续元素进行比较以检查其位置。如果关键元素小于其后续元素，则不进行交换。否则，将交换两个比较的元素，并选择下一个元素作为关键元素。

插入排序可以用四种编程语言实现：C、C++、Java 和 Python −

#include <stdio.h>
void insertionSort(int array[], int size){
   int key, j;
   for(int i = 1; i<size; i++) {
      key = array[i];//take value
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key; //插入到正确的位置
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; //初始化数组
   printf("排序前的数组：");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("
");
   insertionSort(arr, n);
   printf("排序后的数组：");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("
");
}

排序前的数组：67 44 82 17 20 
排序后的数组：17 20 44 67 82 

#include<iostream>
using namespace std;
void insertionSort(int *array, int size){
   int key, j;
   for(int i = 1; i<size; i++) {
      key = array[i];//take value
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key; //插入到正确的位置
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; //初始化数组
   cout << "排序前的数组：";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   insertionSort(arr, n);
   cout << "排序后的数组：";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

排序前的数组：67 44 82 17 20
排序后的数组：17 20 44 67 82

import java.io.*;
public class InsertionSort {
   public static void main(String args[]) {
      int n = 5;
      int[] arr = {67, 44, 82, 17, 20}; //初始化数组
      System.out.print("排序前的数组：");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
      for(int i = 1; i<n; i++) {
         int key = arr[i];//take value
         int j = i;
         while(j > 0 && arr[j-1]>key) {
            arr[j] = arr[j-1];
            j--;
         }
         arr[j] = key; //插入到正确的位置
      }
      System.out.print("排序后的数组：");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

排序前的数组：67 44 82 17 20
排序后的数组：17 20 44 67 82

def insertion_sort(array, size):
   for i in range(1, size):
      key = array[i]
      j = i
      while (j > 0) and (array[j-1] > key):
         array[j] = array[j-1]
         j = j-1
      array[j] = key
      
arr = [67, 44, 82, 17, 20]
n = len(arr)
print("排序前的数组：")
print(arr)
insertion_sort(arr, n);
print("排序后的数组：")
print(arr)

排序前的数组：
[67, 44, 82, 17, 20]
排序后的数组：
[17, 20, 44, 67, 82]