熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

排序之直接插入排序

2013-11-15 15:46:07  來源: 數據結構 

  插入排序(Insertion Sort)的基本思想是每次將一個待排序的記錄按其關鍵字大小插入到前面已經排好序的子文件中的適當位置直到全部記錄插入完成為止

 直接插入排序

  直接插入排序(Straight Insertion Sort)將一個記錄插入到排好序的有序表中從而得到一個新的記錄數增的有序表
直接插入排序算法

 
  哨兵(監視哨)有兩個作用一是作為臨變量存放R[i](當前要進行比較的關鍵字)的副本二是在查找循環中用來監視下標變量j是否越界
 
  當文件的初始狀態不同時直接插入排序所耗費的時間是有很大差異的最好情況是文件初態為正序此時算法的時間復雜度為O(n)最壞情況是文件初態為反序相應的時間復雜度為O(n)算法的平均時間復雜度是O(n)算法的輔助空間復雜度是O()是一個就地排序
直接插入排序是穩定的排序方法


From:http://tw.wingwit.com/Article/program/sjjg/201311/23919.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.