-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStraightInsertionSort.java
More file actions
60 lines (52 loc) · 1.29 KB
/
StraightInsertionSort.java
File metadata and controls
60 lines (52 loc) · 1.29 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
package sort;
/*
* 直接插入排序
* 如果有一个有序序列【1,2,5】将4插入时，将插入到2后面
* 直接插入排序：如果有i个元素，就进行i-1次插入，先把第一个元素作为有序集，插入第二个数，再把第三个数插入...
* 时间复杂度：O(n~2)
*
* */
public class StraightInsertionSort extends Sort {
public StraightInsertionSort(int[] array) {
super(array);
}
@Override
public int[] sortAlgorithm(int[] array) {
return insertionSort2();
}
public int[] insertionSort1() {
if(array==null||array.length<2){
return array;
}
// 从第二个数开始往里面插入
for (int i = 1; i < array.length; i++) {
for (int j = 0; j < i; j++) {
// 将array[i]插入前面的j个数中
if (array[i] <= array[j]) {
int temp = array[i];
for (int k = i - 1; k >= j; k--) {
array[k + 1] = array[k];
}
array[j] = temp;
}
}
}
return array;
}
public int[] insertionSort2(){
if(array==null||array.length<2){
return array;
}
for(int i=1;i<array.length;i++){
for(int j=0;j<i;j++){
//如果array[i]比array[j]小的话，就替换两个数的位置
if(array[i]<array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
return array;
}
}