排序_插入排序-Aet

Bingliaolong 2020-09-04 08:06 Aet | 隐藏边栏 | 抢沙发 | 4 0

文章评分 2 次，平均分 5.0 ：

简述

插入排序思想，假设对数组A[p...r]排序:
维持不变式：设当前排序的元素是 A[q]，则保持A[p...q-1]为排好的，A[q]在A[p...q-1]中找到它的位置坐下

template<typename Iterator,typename CompareType=std::less<typename std::iterator_traits<Iterator>::value_type>>

void insert_sort(const Iterator begin,const Iterator end,CompareType compare=CompareType())

{

//typedef typename std::iterator_traits<Iterator>::value_type T;// 迭代器指向对象的值类型

auto size = std::distance(begin,end);

if (size <= 1)

return;

Iterator current = begin;

while(++current != end)

{

auto small_next = current;//指向比*current小的元素中最大的那个元素

//current较小，则向前寻找插入的位置插入

while(small_next != begin && compare(*current,*(small_next-1)))

{

small_next--;

}

auto key = *current;

auto iter = current;

while (iter != small_next)//插入

{

*iter = *(iter-1);//后移

iter--;

}

*(iter) = key;

}

本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！

Bingliaolong 关注：0 粉丝：0 最后编辑于：2021-11-20

Everything will be better.