forked from forging2012/JavaArithmetic
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInsertSort.java
More file actions
169 lines (112 loc) · 4.42 KB
/
InsertSort.java
File metadata and controls
169 lines (112 loc) · 4.42 KB
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
package sort;
/**
* Created by ozc on 2018/3/15.
*
* @author ozc
* @version 1.0
*/
public class InsertSort {
public static void main(String[] args) {
int[] arrays = {9, 8, 1, 4, 2, 3, 5, 6, 7, 13, 12, 14, 11, 15, 16, 17, 19, 18, 10};
sort2(arrays);
System.out.println(arrays);
}
/**
* 插入排序普通版
* @param arrays
*/
public static void sort(int[] arrays) {
//int[] arrays = {3, 2, 1, 3, 3};
/* //第一趟排序--------------------
int temp;
if (arrays[1] > arrays[0]) {
//如果第二个数比第一个数大，直接跟上
} else {
//如果第二个数比第一个数小，将第一个数后退一个位置(将第二个数插进去)
temp = arrays[1];
arrays[1] = arrays[0];
arrays[0] = temp;
}
System.out.println("公众号Java3y" + arrays);
//第二趟排序--------------------
if (arrays[2] > arrays[1]) {
//如果第三个数比第二个数大，直接跟上
} else {
//如果第三个数比第二个数小，将第二个数往后退一个位置，让第三个数跟第一个数比
temp = arrays[2];
arrays[2] = arrays[1];
//如果第三个数比第一个大，那就插入到第二个数中
if (temp > arrays[0]) {
arrays[1] = temp;
} else {
//如果第三个数比第一个小，将第三个数插入到第一个数前面
int swapTemp = arrays[0];
arrays[0] = temp;
arrays[1] = swapTemp;
}
}
System.out.println("公众号Java3y" + arrays);*/
//临时变量
int temp;
//外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据)
for (int i = 1; i < arrays.length; i++) {
temp = arrays[i];
//如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序]
int j = i - 1;
while (j >= 0 && arrays[j] > temp) {
//往后退一个位置，让当前数据与之前前位进行比较
arrays[j + 1] = arrays[j];
//不断往前，直到退出循环
j--;
}
//退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
arrays[j + 1] = temp;
}
System.out.println("公众号Java3y" + arrays);
}
/**
* 二分插入排序:插入到有序的位置时，使用二分法查找出对应的index，避免多次移动
* @param arrays
*/
public static void sort2(int[] arrays) {
//临时变量
int temp;
//外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据)
for (int i = 1; i < arrays.length; i++) {
//二分查找找出合适的插入位置
int index = BinarySearchIndex(arrays, i - 1, arrays[i]);
//如果不是直接插入，那么就要移动位置了
if (index != i) {
temp = arrays[i];
int j;
// 后移元素，腾出arr[index]位置
for (j = i - 1; j >= index && j >= 0; j--) {
arrays[j + 1] = arrays[j];
}
arrays[j + 1] = temp;
}
}
System.out.println("公众号Java3y" + arrays);
}
private static int BinarySearchIndex(int[] arr, int maxIndex, int data) {
//定义三个指针，分别为待查找区域的两端和中心位置，这个对应的是有序区的大小，不是 整个数组
int left = 0;
int right = maxIndex;
int mid;
//只要左边和右边指针没相撞，那么就可以找
while (left <= right) {
//取中间数
mid = (left + right) / 2;
//比中间数大的或者等于中间数，往右边找
if (data >= arr[mid]) {
//这里包括了等于的情况--->如果等于，角标+1，那么则是直接插入
left = mid + 1;
} else {
//比中间数小的，往左边找
right = mid - 1;
}
}
//角标相撞了才结束循环..
return left;
}
}