使用 C++ STL 的插入排序

在本教程中，我们将讨论一个使用 C++ STL 来理解插入排序的程序。

其中，我们使用 std::upper_bound 找出错误位置的元素，然后旋转数组中未排序的部分，使其变成排序状态。

示例

 在线演示

#include <bits/stdc++.h>
//function to perform insertion sort
void insertionSort(std::vector<int> &vec){
   for (auto it = vec.begin(); it != vec.end(); it++){
      auto const insertion_point =
      std::upper_bound(vec.begin(), it, *it);
      std::rotate(insertion_point, it, it+1);
   }
}
//printing the array
void print(std::vector<int> vec){
   for( int x : vec)
   std::cout << x << " ";
   std::cout << '\n';
}
int main(){
   std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};
   insertionSort(arr);
   print(arr);
   return 0;
}

输出

1 2 3 4 5 5 6 7

阿尤什·古普塔

更新于：2020-04-01

617 次浏览

开启您的 职业生涯

完成课程获取认证

开始