设计与分析-插入排序

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

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

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

插入排序算法

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

步骤 1 - 如果它是第一个元素，则它已经排序。返回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; //insert in right place
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; // initialize the array
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("\n");
   insertionSort(arr, n);
   printf("Array after Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("\n");
}

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 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; //insert in right place
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; // initialize the array
   cout << "Array before Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   insertionSort(arr, n);
   cout << "Array after Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Array before Sorting: 67 44 82 17 20
Array after Sorting: 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}; //initialize an array
      System.out.print("Array before Sorting: ");
      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; //insert in right place
      }
      System.out.print("\nArray After Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

Array before Sorting: 67 44 82 17 20
Array After Sorting: 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("Array before Sorting: ")
print(arr)
insertion_sort(arr, n);
print("Array after Sorting: ")
print(arr)

Array before Sorting: 
[67, 44, 82, 17, 20]
Array after Sorting: 
[17, 20, 44, 67, 82]