Java基础算法-排序-插入排序

插入排序也是最常见的排序之一，他分为以下几种

1 直接插入排序
2 二分插入排序
3 希尔插入排序
4 链表插入排序

实现原理

跟抓牌一样，自己先定义一个有序区域，把抓到的牌放到已经排好序的牌堆里面，直到所有牌都抓完，有序区域就变成了整个
牌。
也就是说假设前面(n-1) [n>=2]个数已经是排
好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数
也是排好顺序的。如此反复循环，直到全部排好顺序

时间复杂度

一般来说，最好情况下的插入排序时间复杂度为O(n),平均以及最坏的时间复杂度为O(n^2),而且插入排序是最稳定的排序
算法，在数据量小的情况下，插入排序的效率挺高的- -。

下面让我用java代码实现下直接插入排序。

代码实现直接排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Insertion {  
    public static void insertionSort(int []num){  
    	int temp = 0;
       	
        for(int i=1;i<num.length;i++){
       		int j=i-1;
      		temp=a[i];
		while(j >= 0&&temp < a[j]){
       			a[j+1] = a[j];                //将大于temp的值整体后移一个单位
       			j--;
       		}
       		a[j+1] = temp;
    	}
    }  
    public static void main(String []args){  
        int[] num={4,9,23,1,45,27,5,2};  
        insertionSort(num);  
        for(int i=0;i<num.length;i++)  
            System.out.println("插入排序后："+num[i]);  
    }  
}
Algorithms