插入排序有哪些

插入排序有簡單插入排序和希爾排序這兩種，簡單插入排序的時間複雜度是【O(N2) 穩定排序】，希爾排序的時間複雜度是【和增量序列的選取有關，非穩定排序】。

插入排序

#簡單插入排序

將待排序的一組序列分為已排好序和未排序的兩個部分，初始狀態時，已排序序列僅包含第一個元素，未排序序列中的元素為除了第一個以外N-1個元素；此後將未排序序列中的元素逐一插入到已排序的序列中。如此往復，經過N-1次插入後，未排序序列中元素個數為0，則排序完成

#時間複雜度：O(N2) 穩定排序

希爾排序

將待排序的一組元素依一定間隔分成若干個序列，分別進行插入排序。開始時設定的"間隔"較大，在每輪排序中將間隔逐步減小，直到"間隔"為1，也就是最後一步是進行簡單插入排序

#時間複雜度：和增量序列的選取有關非穩定排序

以上是插入排序有哪些的詳細內容。更多資訊請關注PHP中文網其他相關文章！