插入排序有哪些
时间：2020-08-14 19:30:13
作者：重庆seo小潘
来源：
插入排序有简单插入排序和希尔排序这两种，简单插入排序的时间复杂度是【O(N2) 稳定排序】，希尔排序的时间复杂度是【和增量序列的选取有关，非稳定排序】。 插入排序 简单插入排序 将待排序的一组序列分为已排好序和未排序的两个部分，初始状态时，已排序序
插入排序有简单插入排序和希尔排序这两种，简单插入排序的时间复杂度是【O(N2) 稳定排序】，希尔排序的时间复杂度是【和增量序列的选取有关，非稳定排序】。
插入排序
简单插入排序
将待排序的一组序列分为已排好序和未排序的两个部分，初始状态时，已排序序列仅包含第一个元素，未排序序列中的元素为除了第一个以外N-1个元素；此后将未排序序列中的元素逐一插入到已排序的序列中。如此往复，经过N-1次插入后，未排序序列中元素个数为0，则排序完成
时间复杂度：O(N2) 稳定排序
希尔排序
将待排序的一组元素按一定间隔分为若干个序列，分别进行插入排序。开始时设置的"间隔"较大，在每轮排序中将间隔逐步减小，直到"间隔"为1，也就是最后一步是进行简单插入排序
时间复杂度：和增量序列的选取有关 非稳定排序
