算法笔记（第一部分）-- 排序之白话插入排序

插入排序也是一种比较简单的排序方法，它的基本原理就好似我们打牌过程中摸牌理牌那一环：当你摸到一张牌后将其插入到合适的位置。

插入排序首先定位一个数（一般从第二个开始），将这个数依次与位于它之前的数进行比较，经过一轮比较，找到它在这些数中适当的位置。然后定位下一个数，再找到合适的位置，依次进行直到最后一个数。

例如（5 2 1 4 3)，黑体为进行交换的两数。
第一轮：
（2 5 1 4 3）
第二轮：
（2 1 5 4 3）
       （1 2 5 4 3）
第三轮：
（1 2 4 5 3）
       （1 2 4 5 3）
       （1 2 4 5 3）
第四轮：
（1 2 4 3 5）
       （1 2 3 4 5）
       （1 2 3 4 5）
       （1 2 3 4 5）排序完成

插入排序在数据集较大的时候效率会变的很低，但是它易于实现，处理小型数据集时效率较高，同时也是稳定的，in-place(目前不知道怎么翻译)的，它的时间复杂度是О(n²)，空间复杂度是О(n)。

插入排序的动画：


插入排序的代码（递增）：

public void insertion_sort(int[] data){
        int key = 0;
        int j = 0;
        for(int i=1; i<data.length; i++){
              key = data[i];
              j = i-1;
              while(j>=0 && data[j]>key){
            	    swap(data,j,j+1);
                    j=j-1;
              }
        }
}

评论

2 楼 lenky0401 2008-09-07  

in-place: This means that the algorithms do not allocate additional storage to hold temporary results: they sort the data in place. 

1 楼 lenky0401 2008-09-07  

in-place 原地或就地 意思是不需要额外的输出数据保存空间 输出直接覆盖占用输入