插入排序

维基百科，自由的百科全书
跳转至： 导航、 搜索
插入排序
Insertion sort animation.gif

使用插入排序为一列数字进行排序的过程
分類 排序算法
數據結構 数组
最差時間復雜度 O(n^2)
最優時間復雜度 O(n)
平均時間復雜度 O(n^2)
最差空間復雜度 总共O(n) ，需要辅助空间O(1)
最佳算法 No
使用插入排序为一列数字进行排序的过程

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

目录

記載 [编辑]

最早擁有排序概念的機器出現在1901至1904年間由Hollerith發明出使用基數排序法的分類機，此機器系統包括打孔，制表等功能，1908年分類機第一次應用於人口普查，並且在兩年內完成了所有的普查數據和歸檔。 Hollerith在1896年創立的分類機公司的前身，為電腦製表記錄公司（CTR）。他在電腦製表記錄公司（CTR）曾擔任顧問工程師，直到1921年退休，而電腦製表記錄公司（CTR）在1924年正式改名為IBM。

算法描述 [编辑]

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

範例程式碼 [编辑]

範例程式碼為C語言，輸入參數中，需要排序的陣列為array[]，起始索引值為first，终止索引值為last。範例原始碼的函數採用in-place排序，使用完成後，array[]中從first到last處於升冪排序。

 void insertion_sort(char array[], int first, int last)
 {
        int i,j;
        int temp;
        for (i = first+1; i<=last;i++)
        {
                temp = array[i];
                j=i-1;
 
                //與已排序的數逐一比較，大於temp時，該數向後移
                while((j>=first) && (array[j] > temp))  //当first=0，j循环到-1时，由于[[短路求值]]，不会运算array[-1]
                {
                        array[j+1] = array[j];
                        j--;
                }
                array[j+1] = temp;      //被排序数放到正确的位置
 
        }
 }

[C#] 這是C#程式碼的 插入排序法。

        public static void InsertSort(double[] data) {
            var count = data.Length;
            for (int i = 1 ; i < count ; i++) {
                var t = data[i];
                var j = i;
                while (j > 0 && data[j - 1] > t) {
                    data[j] = data[j-1];
                     --j;
                }
                data[j] = t;
            }
        }

這是c++语言版本的插入排序法。為了支援list使用了std::advance()。

#include <iterator>
 
template<typename biIter>
void insertion_sort(biIter begin, biIter end)
  {
    typedef typename std::iterator_traits<biIter>::value_type value_type;
    biIter bond = begin;
    std::advance(bond, 1);
    for(; bond!=end; std::advance(bond, 1)) {
      value_type key = *bond;
      biIter ins = bond;
      biIter pre = ins;
      std::advance(pre, -1);
      while(ins!=begin && *pre>key) {
        *ins = *pre;
        std::advance(ins, -1);
        std::advance(pre, -1);
      }
      *ins = key;
    }
  }

以下是PASCAL語言，程式使用 linked list 做插入排序，目的：将讀入的英文名字按字母排列

TYPE
link=^node;
node=record
      data:string;
      next:link;
     end;
VAR
 
p,q,head,n:link;
t,m:integer;
f1,f2:text;
i:string;
BEGIN
 
assign(f1,'lianbiao-name-in.txt');
reset(f1);
assign(f2,'lianbiao-name-out.txt');
rewrite(f2);
head:=nil;
read(f1,t);
readln(f1);
read(f1,i);
new(p);
p^.data:=i;
p^.next:=nil;
head:=p;
readln(f1);
read(f1,i);
FOR m:=2 TO t DO
 BEGIN
  p:=head;
  new(n);
  n^.data:=i;
  while (i>p^.data) and (p^.next<>nil) do
   begin
    q:=p;
    p:=p^.next;
   end;
  if i<head^.data then begin
                        n^.next:=head;
                        head:=n;
                       end
                  else if (i>p^.data) and (p^.next=nil) then begin
                                                              p^.next:=n;
                                                              n^.next:=nil;
                                                             end
                                                        else begin
                                                              q^.next:=n;
                                                              n^.next:=p;
                                                             end;
  readln(f1);
  read(f1,i);
 end;
p:=head;
while p<>nil do
 begin
  write(f2,p^.data,' ');
  p:=p^.next;
 end;
CLOSE(f1);
CLOSE(f2);
END.

以下是Python代码：

def insert(L):
        L = [0]+L[:]
        for i in range(2,len(L)):
                L[0] =  L[i]-1
                for j in range(i-1,0,-1):
                        if L[i] <= L[j] and L[i] > L[j-1]:
                                L[j:i+1] = L[i:i+1] + L[j:i]
 
        L.pop(0)
        return L
 
# alexander.lee0729@aol.com
def InsertionSort(arr):
        #'insertion sort demo'
 
        arr_len = len(arr)
 
        for i in range(1, arr_len):
                key, j = arr[i], i
 
                while key < arr[j - 1] and j > 0:
                        arr[j], j = arr[j - 1], j - 1
 
                arr[j] = key

Java原始碼：

public class Insertion {  
    public static void insertionSort(Comparable []data){  
        for(int index=1;index<data.length;index++){  
            Comparable key = data[index];  
            int position = index;  
            //shift larger values to the right  
            while(position>0&&data[position-1].compareTo(key)>0){  
                data[position] = data[position-1];  
                position--;  
            }  
            data[position]=key;  
        }     
    }  
    public static void main(String []args){  
        Comparable []c={4,9,23,1,45,27,5,2};  
        insertionSort(c);  
        for(int i=0;i<c.length;i++)  
            System.out.println("插入排序："+c[i]);  
    }  
}

以下是javascript的insertion sort 的表示法：

Array.prototype.insert_sort=function(){
        var key;
        var t;
        for (j=1;j<this.length ;j++ )//從陣列第二個元素開始迴圈。
        {
                key=this[j];
                t=j-1;
                while (t>=0 && this[t]>key)
                {
                        this[t+1]=this[t];
                        this[t]=key;//如果迴圈到的元素比其前一個元素大，則互換其位置。
                        t--;
                }
        }
        return this;
}

用法示例：[3,5,2,11,1,2,"abc","zfd","sad","eng"].insert_sort();

PHP表示法：

<?php
/**
 * 插入排序
 * 插入排序升冪的PHP表示法
 */
class insertsort{
        /**
         * 构造方法
         * @var array 排序后的顺序
         */
        public $order = array();
 
        /**
         * 构造方法
         *
         * @param array $arr 傳入待排序的PHP數字索引陣列
         */
        public function __construct($arr){
                $this->order = $this->insertsort($arr);
        }
 
        /**
         * 插入升冪順序
         *
         * @param array $arr 傳入待排序的PHP數字索引陣列
         * @return  array 排序後的陣列
         */
        private function insertsort($arr){
                foreach($arr as $k=>$v){
                        $i = $k-1;
                        while($i > -1 && $v < $arr[$i]){
                                $next = $arr[$i+1];
                                $arr[$i+1] = $arr[$i];
                                $arr[$i] = $next;
                                $i--;
                        }
                }
                return $arr;
        }
}
$arr = array(1,2,3,4,8,6,7,5);
$obj = new insertsort($arr);
$obj->order;
?>

算法复杂度 [编辑]

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

参考文献 [编辑]
理论
交换排序
选择排序
插入排序
归并排序
分布排序
并发排序
混合排序
其他
来自“http://zh.wikipedia.org/w/index.php?title=插入排序&oldid=26628055”