基本算法-插入排序

前言

      本文介绍一种经典排序算法——插入排序，是入门级的排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。

一、插入排序简介

      插入排序法是将数组中的元素逐一与已排序好的数据进行比较，并将其放置在合适位置。例如，从小到大排序，第一个数据默认为已排序状态，第二个数据和第一个数据比较并调整位置，第三个数据与排序好的第二个数据比较，如果大于第二个数据，就原地放置，如果小于第二个数据，则再与第一个数据比，这样三个数据就排序好了，以此类推，直到所有的数据都插入到合适的位置，完成排序。

二、算法特点

      1）最坏情况和平均情况需执行(n-1)+(n-2)+....+3+2+1=n(n-1)/2次，时间复杂度为O(n2)；最好情况只需扫描一次即可，也就是本身已经排序好了，这样只执行了n-1次，时间复杂度为O(n)。和冒泡排序类似。

      2）由于插入排序为相邻两个数据相互比较而后决定是否互换位置，并不会改变原来排序的顺序，因此属于稳定排序法。

      3）只需要一个额外空间，空间复杂度很低。

      4）此排序法适用于大部分数据已经排过序的情况，也适用于往已排序数据库中添加新数据后再进行排序的情况。

      5）由于插入排序法会造成数据的大量迁移，因此建议在链表上使用。

三、代码实现

      代码实现逻辑：

1. 从第二个数开始插入，因此i的起始点是1；j是倒序比较的下标，从i-1开始直到0。
2. 如果一开始result[j]<result[i]，则不用进行下面的while循环，说明已经排序完毕了。
3. 若result[j]>result[i]，则进入while循环，这个循环干的事就是把比当前数大的值都往后排，所以有result[j+1]=result[j]和j--的操作；到了某个位置，当前数大于前一个数了，此时循环终止，将之前存的temp赋值在当前位置上，就相当于将其插入了。

// 插入排序
vector<int> InsertSort(vector<int> data)
{
  // 拷贝
  vector<int> result = data;
  // 排序过程：
  int size = static_cast<int>(data.size());
  for (int i = 1; i < size; ++i)
  {
    int temp = result[i];
    int j = i - 1;
    while (j >= 0 && result[j] > temp)
    {
      result[j + 1] = result[j];
      j--;
    }
    result[j + 1] = temp;
  }
  return result;
}

四、C++示例

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;
// 展示当前顺序
void Show(vector<int> data)
{
  size_t size = data.size();
  for (size_t i = 0; i < size; ++i)
    cout << setw(4) << data[i];
  cout << endl;
}
// 插入排序
vector<int> InsertSort(vector<int> data)
{
  // 拷贝
  vector<int> result = data;
  cout << "插入排序：\n原始数据：\n";
  Show(result);
  // 排序过程：
  int size = static_cast<int>(data.size());
  for (int i = 1; i < size; ++i)
  {
    int temp = result[i];
    int j = i - 1;
    while (j >= 0 && result[j] > temp)
    {
      result[j + 1] = result[j];
      j--;
    }
    result[j + 1] = temp;
    cout << "第" << i << "次排序结果：\n";
    Show(result);
  }
  cout << "排序后结果：\n";
  Show(result);
  return result;
}
// 主函数
int main()
{
  vector<int> data = { 9,11,567,0,-2,4,2 };
  // 插入排序
  vector<int> result3 = InsertSort(data);
  system("pause");
  return 0;
}

  效果图：

      综上所述，插入排序法是个比较基础的排序法，优点是往已排序的数据集合中插入新数据时，很方便省时，缺点就是对全乱的数据进行排序时挺慢的~

      如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！