By

文章目录
  1. 1. 插入排序

插入排序

思想：一堆数据，前面部分有序，后面无序；遍历无序的这部分数据，并在前面有序数据中寻找合适的位置插入，并将插入点后的数据后移，使插入后的前面数据仍然有序；
应用场景：适用于少量数据排序，是原址排序

原址排序：如果排序数组中仅有常数个元素需要在排序过程中存储在数组之外，则称排序算法是原址的。除了插入排序 ，还有堆排序和快排。

  • 直接插入排序
  • 折半插入排序

情景 时间复杂度
理想 O(n)
最坏 O(n^2)

稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//java code
public void insertSort(int[] array){
	   int len = array.length;
	   
	   for(int j = 1 ;j<len;j++){
		   int key = array[j];
		   int i = j-1;
		   //比较一个，移动一个
		   while( i >=0 && key<array[i]){
			   // key<array[i] && i >=0  数组会越界抛异常
			   array[i+1] = array[i--];
		   }
		   //插入（当一个for或while循环按通常的方式[即由于循环头中的测试]退出时，执行测试的次数比执行循环体的次数多1，故插入点为array[i+1]）
		   array[i+1] = key;
	   }
	   
}
//比较次数减少，移动次数不变
public static void binaryInsertSort(int[] array){
	   int len = array.length;
	   
	   for(int j = 1 ; j<len; j++){
		   int key = array[j];
		   int i = j-1;
		   //location 是 key 刚好 >= value的地方
		   int location = binarySearch(array,0,i,key);
		   //通过二分查找找到插入点，将插入点后数据整体移动；
		   for(;i>=location;i--){
			   array[i+1] = array[i];
		   }
		   
		   array[i+1] = key;
	   }
	   
}
public static int binarySearch(int[] array,int start,int end,int obj){
    int left = start;
    int right = end;
    int mid = 0;
    while(left <= right){
   	    mid = (left + right )/2;
   	   
        if(obj >= array[mid]){
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }
    return left;//注意返回left，寻找的<=obj的位置；
}
文章目录
  1. 1. 插入排序