插入類排序法

所謂插入排序,是指將無序序列中的各元素依次插入到已經有序的線性表中。

基本介紹

  • 中文名:插入類排序法
  • 概念:一種排序方法
  • 分類:簡單插入排序法、希爾排序法
  • 套用學科:高等數學
主要分為兩種:
① 簡單插入排序法;
基本思想:所謂插入排序,是指將無序序列中的各元素依次插入到已經有序的線性表中。
一般來說,假設線性中前j-1元素已經有序,現在要將線性表中第j個元素插入到前面的有序子表中,插入過程如下:
將第j個元素放到一個變數T中,然後從有序子表的最後一個元素(即線性表中第j-1個元素)開始,往前逐個與T進行比較,將大於T的元素均依次向後移動一個位置,直到發現一個元素不大於T為止,此時就將T(即原線性表中的第j個元素)插入到剛移出的空位置上,有序子表的長度就變為j了。效率與冒泡法相同
在最壞情況下,簡單插入排序需要n(n-1)/2次比較。
② 希爾排序法;
基本思想:將整個無序序列分割成若干小的子序列分別進行插入排序。
子序列的分割方法如下:
將相隔某個增量H的元素構成一個子序列。在排序過程中,逐次減小這個增量,最後當H減到1時,進行一次插入排序,排序就完成。增量序列一般取h=n/2k(k=1,2,…【log2n】,其中n為待排序序列的長度。
其效率與增量序列有關。 在最壞情況下,需要的比較次數為O(N^1.5)。

相關詞條

熱門詞條

聯絡我們