​
​

活动地址：CSDN21天学习挑战赛

插入排序

插入排序的基本思路是每次插入一个元素,每一趟完成对一 个待排元素的放置，直到全部插入完成。
简单来说就是把小的数插入到大的数之前,从而把整个数组排好序
拿个简单的例子就是打扑克
只要打过扑克牌的都会对插入排序有一定的了解
排序扑克牌就是把小的牌一个个插入到大的牌前面

代码

	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 不只1个数
		for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}
	public static void swap(int[] arr, int i, int j) {
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

折半插入排序

折半插入排序就是在插入排序的基础上进行折半查找,来快速定位到要插入的位置

low到height代表有序区的范围,min代表无序区里的最小数
第一次遍历,有序区为[0,0],min=1;
将1插入到有序区内

有序区扩大一位
通过二分查找,我们可以确定比2小的数的最右位置
1后面即为2要插入的位置

到6了,
同过二分查找,我们可以快速的确定要插入到5的后面,

之后就按照以上的步骤,把整个数组排好

时间复杂度

如果输入的元素刚好是反向有序的，那么每次都需要进行位置的查找,但是在查找的次数要少一些。 可以知道，由于区间每次缩小一半,
可以得到寻找位置的次数最多为log2 i量级,但是由于移动元素的次数没变,时间复杂度依然是0(n²)。

代码

public class BinaryInsert {

    public static void main(String[] args) {
        // input data
        int[] a = {11,34,20,10,12,35,41,32,43,14};
        // 数组下标从0开始，j初始为1，指向第二个元素
        for (int i = 1;i < a.length;i++){
            if (a[i] < a[i - 1]){
                // 使用temp记录当前元素的值
                int tmp = a[i];
                // 初始化变量
                int left = 0;
                int right = i - 1;
                // while循环作用：使用二分查找确定元素位置，并串出对应的位置
                while(left <= right){
                    // 取中间元素，以下写法防止数据量较大时发生溢出
                    int mid = (right - left) / 2 + left;
                    if(a[mid] > tmp){
                        // 待排元素较小，将搜索区间缩小至左一半
                        right = mid - 1;
                    }else {
                        // 待排元素较大，将搜索区间缩小至右一半
                        left = mid + 1;
                    }
                }
                // 将待排元素放在对应的位置
                for (int j = i - 1;j >= right + 1;j--){
                    a[j + 1] = a[j];
                }
                a[right + 1] = tmp;
            }
        }
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

}

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