直接插入排序

直接插入排序

写法1:查找插入位置 后移腾出位置 插入

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
/**
* 直接插入排序,每次取下一个元素后。
* 插入前面已经有序的序列中,并保证插入后依然有序。
* 先查找待插入的位置,然后把该位置之后的其他元素后移一位。
* 然后在放入插入的元素
*
* @param data 待排序的数组
*/
public static void directSortInsertByFind(int[] data) {
if (data == null)
return;
// 第0个元素已经有序,从第1个开始向前方已经有序的序列中插入
for (int i = 1; i < data.length; i++) {
// 缓存待插入的元素
int toInsert = data[i], insertIndex;
// 从前向后遍历,查找插入点
for (insertIndex = 0; insertIndex <= i - 1; insertIndex++) {
// 当遍历的元素大于待插入的元素时
if (data[insertIndex] > toInsert)
break;
}
// 后移插入点之后的元素
for (int k = i; k > insertIndex; k--)
data[k] = data[k - 1];
// 待插入的元素,放入插入点之中
data[insertIndex] = toInsert;
}
}

写法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
/**
* 直接插入排序
* 每次取下一个元素,插入到前方已经有序的序列之中。
* 该元素插入有序序列的末尾,然后使用冒泡法调整插入元素的位置。
*
* @param data 待排序的数字
*/
public static void directSortInsertByMaoPao(int[] data) {
// 输入合法性判断
if (data == null)
return;
// 数组的第0个元素,必定有序,
// 所以从第1个元素开始,向前方已排序序列中插入元素
for (int i = 1; i < data.length; i++) {
// 从当前元素开始 遍历 到数组开头
for (int j = i; j > 0; j--) {
// 把该元素冒泡到前面去
// 如果遍历的元素比它前面的元素小的话
if (data[j] < data[j - 1]) {
// 把该元素换到前面去
int t = data[j];
data[j] = data[j - 1];
data[j - 1] = t;
} else {
break;
}
}
}
}

改进写法:二分查找来找插入位置

使用二分查找来查找待插入元素的位置

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
54
55
/**
* 直接插入排序,每次取出一个元素,插入到前方已排序的序列中。
* 使用折半查找来查找插入点。
*
* @param data 待排序的数组
*/
public static void directSortInsertByHalfSearch(int[] data) {
if (data == null)
return;
for (int i = 1; i < data.length; i++) {
int key = data[i];
// 使用折半查找,找出插入点
int j = FindInsertIndexByHalfSearch(data, i - 1, key);
// 把插入点之后的都后移一位
for (int k = i; k > j; k--)
data[k] = data[k - 1];
// 把当前遍历的元素放到插入点之中
data[j] = key;
}
}

/**
* 在数组的0~n的区间内进行折半查找,二分查找
*
* @param data 需要查找的数组
* @param n 需要在数组的那个位置之前查找,[0,n]
* @param key 要查找的
* @return
*/
private static int FindInsertIndexByHalfSearch(int[] data, int n, int key) {
// if(data==null) return -1;
int left = 0, right = n;
// 在已经排好序的序列中查找插入点
while (left <= right) {
// 计算中间点的位置
int mid = (left + right) / 2;
// 如果中间点的位置与要查找的相等
if (data[mid] == key) {
// 返回位置
return mid;
}
// 如果中间点的值比待查找的大
if (data[mid] > key)
// 下次到中间点的前方查找,把尾指针指向中间点的前一个位置
right = mid - 1;
// 如果中间点的值比待查找的小
else
// 下次到中间点的后方去查找,把左指针指向中间点的后一个位置
left = mid + 1;
}
// 当已经排好序的序列中查找不到插入点时,说明这个数比最大的数大,
// 则直接插入在已排序序列的末尾即可
right++;
return right;
}