环球即时看！插入排序

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

环球即时看！插入排序

2023-03-29 12:52:11 来源：博客园

(资料图片仅供参考)

欢迎关注fish的公众号：fish码农成长之旅

插入排序的算法实现没有冒泡排序跟选择排序来的那么的直观易懂，但是其算法思想是最容易理解的。通过构建有序序列，对于未排序的序列在已排序的序列中找到相应位置并插入。

算法步骤

把数组分为有序序列(初始化为1，第一个就是有序的)跟无序序列(剩下的n - 1个数)。选择最前端的无序序列的数，从右到左遍历有序序列，找到相应位置插入，有序序列加一，无序序列减一。

实例演示

总共7个数的排序，按照从小到大排序，原始数据为：3 38 5 1 9 4 10

由图看出：第一次遍历，3为有序，38为无序序列最前端的数，相比较之后有序序列变为3 38；第二次遍历，5为无序序列最前端的数，首先跟38比较，应该在38之前，再跟3比较，应该在3之后，有序序列变为3 5 38；第三次遍历，1为无序序列最前端的数，首先跟38比较，应该在38之前，再跟5比较，应该在5之前，再跟3比较，应该在3之前，有序序列变为1 3 5 38。

剩下的同理。

代码实现

template void insertion_sort(std::vector &arrs) {  int n = arrs.size();  // 数组的大小  if (n <= 1) {         // 一个数的情况不需要排序    return;  }  for (int idx_i = 1; idx_i < n; ++idx_i) {  // 无序数组 从第一个到最后一个    T key = arrs[idx_i];                     // 无序数组的最前端元素    int idx_j = idx_i - 1;    for (        idx_j = idx_i - 1; idx_j >= 0 && arrs[idx_j] > key;        idx_j--) {  // 遍历有序数组，把不合适的全部往后移动一位，直到找到合适的位置      arrs[idx_j + 1] = arrs[idx_j];    }    // 在合适的位置上放上 无序数组最前端的元素    arrs[idx_j + 1] = key;  }}

关键词：