C++程序插入排序

插入排序 是一种简单的排序算法，它类似于在手中排序纸牌的方式。数组被虚拟地划分为已排序部分和未排序部分。从未排序部分选出的值被放置在已排序部分的正确位置上。

插入排序的特点：

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

插入排序算法的工作方式：

考虑一个例子：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, 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

最终，数组完全排序。

插入排序算法说明:

C++程序插入排序

插入排序算法

要按升序排列大小为N的数组：

遍历数组的arr[1]到arr[N]。
比较当前元素（键）与其前任。
如果关键元素小于其前任，则将其与前面的元素进行比较。将更大的元素向上移动一个位置，为交换的元素腾出空间。

下面是代码实现:

// 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```

输出:

5 6 11 12 13

时间复杂度: O(N^2)

空间复杂度: O(1)

插入排序算法的边界用例是什么?

如果元素按照相反的顺序排序，则插入排序需要最长时间来排序。当元素已排序时，它花费的时间最少(顺序为n)。

插入排序算法的算法范式是什么?

插入排序算法采用增量方法。

插入排序是一种原地排序算法吗?

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

插入排序是稳定算法吗?

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

什么时候使用插入排序算法?

当元素数量较少时，插入排序很有用。当输入数组几乎排序时，在完整的大数组中仅有少数元素被错放时，它也很有用。

什么是二进制插入排序?

我们可以使用二分查找来减少普通插入排序中的比较次数。每次迭代时，二分插入排序使用二分查找来找到插入选定项目的正确位置。在普通插入排序中，最坏情况下排序需要O(i)次（在第i次迭代时）比较。我们可以通过使用二分查找将其减少到O(logi)。由于每次插入需要一系列交换，整个算法的最坏情况运行时间仍为O(n^2)。为实现，请参阅此处。