插入排序

维基百科,自由的百科全书
跳转至: 导航搜索
插入排序
Insertion sort animation.gif
使用插入排序为一列数字进行排序的过程
分类 排序算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度
空间复杂度 总共 ,需要辅助空间
使用插入排序为一列数字进行排序的过程

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

記載[编辑]

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

算法描述[编辑]

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

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

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

範例程式碼[编辑]

C语言[编辑]

 1 void insertion_sort(int arr[], int len)
 2 {
 3     int i,j,temp;
 4 
 5     for (i = 1 ; i < len ; i++ )
 6     {
 7         temp = arr[i];
 8 
 9         for (j = i; j > 0 && arr[j-1] > temp ; j--)
10         {
11             arr[j] = arr[j-1];
12         }
13 
14         arr[j] = temp;
15     }
16 }

C++[编辑]

 1 template <typename BidirectionalIterator>
 2   void insertion_sort(BidirectionalIterator __first, BidirectionalIterator __last) {
 3     if (__first == __last) return;
 4 
 5     BidirectionalIterator __it = __first;
 6     while (++__it != __last) {
 7         typename iterator_traits<BidirectionalIterator>::value_type __val = *__it;
 8         BidirectionalIterator __middle = __it, __right = __it;
 9         while (__val < *--__middle) {
10             *__right-- = *__middle;
11             if (__middle == __first) break;
12         }
13         *__right = __val;
14     }
15 }

C#[编辑]

public static void InsertSort(int[] array)
{
    for(int i = 1;i < array.length;i++)
    {
        int temp = array[i];
        for(int j = i - 1;j >= 0;j--)
        {
            if(array[j] > temp)
            {
                array[j + 1] = array[j];
                array[j] = temp;
            }
            else
                break;
        }
    }
}

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_sort(lst):
    n=len(lst)
    if n==1: return lst
    for i in range(1,n):
        for j in range(i,0,-1):
            if lst[j]<lst[j-1]: lst[j],lst[j-1]=lst[j-1],lst[j]
    return lst

Python的另一个版本[编辑]

def insertion_sort(lst):
    if len(lst) == 1:
        return lst

    for i in range(1, len(lst)):
        temp = lst[i]
        j = i - 1
        while j >= 0 and temp < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = temp
    return lst

Java[编辑]

public static void insertion_sort( int[] arr ){
    for( int i=0; i<arr.length-1; i++ ) {	
        for( int j=i+1; j>0; j-- ) {
            if( arr[j-1] <= arr[j] )
                break;
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
}

Java的另一个版本[编辑]

 1     //将arr[i] 插入到arr[0]...arr[i - 1]中
 2 	public static void insertion_sort(int[] arr) {
 3 		for (int i = 1; i < arr.length; i++ ) {
 4 			int temp = arr[i];
 5 			int j = i - 1;  
 6     //如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
 7 			for (; j >= 0 && arr[j] > temp; j-- ) {
 8 				arr[j + 1] = arr[j];
 9 			}
10 			arr[j + 1] = temp;
11 		}
12 	}

JavaScript[编辑]

 1 Array.prototype.insertion_sort = function() 
 2 {
 3   var i,j;
 4   for(i = 1;i < this.length; i++){
 5     for(j = 0;j<i;j++){
 6       if(this[j]>this[i]){
 7         this.splice(j,0,this[i]);
 8         this.splice(i+1,1);
 9       }
10     }
11   }
12   return this;
13 };

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

PHP[编辑]

function insertion_sort(&$arr) 
{
 //php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
	for ($i = 1; $i < count($arr); $i++) 
    {
	     $temp = $arr[$i];
	     for ($j = $i - 1; $j >= 0 && $arr[$j] > $temp; $j--)
	     $arr[$j + 1] = $arr[$j];
	     $arr[$j + 1] = $temp;
	}
}

Rust[编辑]

fn insert_sort<T>(list: &mut Vec<T>)
    where T: PartialOrd + Copy{

    let mut i = 0;
    while i < list.len()-1 {

        let mut j = i + 1;
        while j > 0 {
            if list[j] > list[j-1] {break;}

            let temp = list[j-1];
            list[j-1] = list[j];
            list[j] = temp;

            j -= 1;
        }

        i += 1;
    }
}

用法示例: let mut a: Vec<i32> = vec![5,8,3,9,1,0]; insert_sort(&mut a);

Go[编辑]

package main

import (
	"fmt"
)

func InsertSort(array []int) {
	n := len(array)
	if n < 2 {
		return
	}
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0; j-- {
			if array[j] > array[j+1] {
				array[j], array[j+1] = array[j+1],array[j]
			}else{
				break
			}
		}
	}
}

func main() {
	array := []int{
		55, 94, 87, 1, 4, 32, 11, 77, 39, 42, 64, 53, 70, 12, 9,
	}
	fmt.Println(array)
	InsertSort(array)
	fmt.Println(array)

}

算法复杂度[编辑]

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

参考文献[编辑]