插入排序算法及其在C++/Java中的实现
在本文中，我们将学习插入排序的概念和实现。
顾名思义，插入排序基于将新值插入已排序的一组值的基本原理。
让我们快速进入排序技术背后的基本概念。
插入排序背后的概念
为了理解这个概念，让我们考虑一个空数组。
每次迭代都会插入一个新值，并且必须将其放置在数组中，以便对整个数组进行排序。
首先，数组包含单个元素，这意味着它已经被排序。
包含单个元素的数组– 9
随后，将一个新元素插入到数组中。
在将其放置到第一个空白处之前，我们将根据已经存在的元素对其进行检查。
我们重复此比较过程，直到遇到更大的元素。
在添加多个元素时，我们将分为以下几个阶段。
在上面的数组中插入15：
在数组中插入15
在上面的数组中添加11：
在数组中插入11
最后，当我们插入5时，我们注意到由于没有更小的元素，因此必须将其放置在数组的开头。
将5插入数组
这种插入和排序的组合方法产生了已建立的插入排序算法。
在现实生活中，我们遇到的是填充数组，而不是插入随机数。
因此，插入排序算法尝试将上述概念应用于已填充的数组。
事不宜迟，让我们继续进行完整的插入排序算法。
插入排序算法
这种基于比较的排序算法非常基础。
通过示例更容易遍历该算法。
一个例子数组
步骤1：将每个元素与前面的元素进行比较
首先，比较需要从第二个元素开始，因为第一个元素本身已经被排序。
我们将每个元素与之前的元素进行比较，直到被检查的元素大于之前的元素。
比较第二个和第一个元素
对于每个系列的比较，该过程或者在到达第一个元素时停止，或者遇到一个较小的元素。
在上述情况下，我们在比较时达到了第一个索引。
步骤2：将每个比较的元素移到右侧
在这一步中，我们将把每个被比较的元素移到数组的右侧。
转移的动机是为要检查的元件腾出空间。
在上面的示例中，仅移位了25。
向右移动25
转移将创建一个空白点。
该空白点已被当前元素占用。
步骤3：将元素放置在空白处
如标题所示，我们将用于比较的元素放在空索引处。
将15放置在空白处
以上三个步骤的组合将数组排序到第二个索引。
同样，对数组中的所有元素重复这些步骤。
经过几次算法迭代，让我们快速看一下数组：
在第二次迭代之后：
第二次迭代后的数组
但是，由于数组已经排序，因此对数组没有影响。
第三次迭代后：
第三次迭代后的数组
步骤4：打印排序后的数组
最后，我们打印排序后的数组。
排序数组
这总结了插入排序的整个算法。
C++中插入排序的实现
#include<bits/stdc++.h>
using namespace std;
//Function that performs Insertion Sort
void insertion_sort(int arr[], int n){
//Loop to implement steps for each element (except first)
for(int i=1; i<n; i++){
//Element under inspection
int value = arr[i];
//Preceding element index
int j = i-1;
//Step 1: Compare each element with preceding elements
while(j >= 0 and arr[j] > value){
//Step 2: Shift each compared element on the right
arr[j+1] = arr[j];
//Move along the preceding elements
j--;
}
//Step 3: Place the element at the empty spot
arr[j+1] = value;
}
cout<<"The Sorted array:"<<endl;
//Step 4: Print the sorted array
for(int i=0; i<n; i++)
cout<<arr[i]<<" ";
cout<<endl;
}
//Main Function
int main(){
//The array to be sorted
int arr[] = {15, 25, 30, 17, 9, 5, 20, 10, 11, 6};
//The size of the array
int n = sizeof(arr)/sizeof(arr[0]);
//Print the original array
cout<<"The Original array:"<<endl;
for(int i=0; i<n; i++)
cout<<arr[i]<<" ";
cout<<endl;
//Function call to implement Insertion Sort
insertion_sort(arr, n);
return 1;
}
输出：
The Original array: 15 25 30 17 9 5 20 10 11 6 The Sorted array: 5 6 9 10 11 15 17 20 25 30
Java插入排序的实现
import java.io.*;
public class InsertionSort
{
//Function that performs Insertion Sort
void insertion_sort(int arr[], int n){
//Loop to implement steps for each element (except first)
for(int i=1; i<n; i++){
//Element under inspection
int value = arr[i];
//Preceding element index
int j = i-1;
//Step 1: Compare each element with preceding elements
while(j >= 0 && arr[j] > value){
//Step 2: Shift each compared element on the right
arr[j+1] = arr[j];
//Move along the preceding elements
j--;
}
//Step 3: Place the element at the empty spot
arr[j+1] = value;
}
System.out.println("The sorted array:");
//Step 4: Print the sorted array
for(int i=0; i<n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String args[])
{
//The array to be sorted
int arr[] = {15, 25, 30, 17, 9, 5, 20, 10, 11, 6};
//The size of the array
int n = arr.length;
//Print the original array
System.out.println("The original array:");
for(int i=0; i<n; i++)
System.out.print(arr[i]+" ");
System.out.println();
//Creating object for InsertionSort Class
InsertionSort is = new InsertionSort();
//Function call to implement Insertion Sort
is.insertion_sort(arr, n);
}
}
输出：
The original array: 15 25 30 17 9 5 20 10 11 6 The sorted array: 5 6 9 10 11 15 17 20 25 30
插入排序涉及的复杂性
插入排序的运行涉及两个复杂性–时间和空间复杂性
时间复杂度
通常，时间复杂度取决于数组中值的大小和排列。
因此，诸如"最佳情况"和"最坏情况"复杂度之类的标准术语是算法时间复杂度的量度。
最坏情况：O(n ^ 2)–数组降序排列的情况。
同时，该算法尝试按升序排序。
最佳情况：O(n)-数组已按排序顺序时的情况。
总体而言，插入排序的时间复杂度为O(n ^ 2)。
空间复杂度
简单来说，空间复杂度是指算法运行期间使用的多余空间或者内存量。
由于我们仅使用诸如value，i和j之类的另外变量，因此空间复杂度为O(1)。
