forked from yangyiRunning/DataStructureAlgorithmsJava
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInsertSort.java
More file actions
67 lines (63 loc) · 2.07 KB
/
InsertSort.java
File metadata and controls
67 lines (63 loc) · 2.07 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
package ds;
/**
* 插入排序
* <p>
* 含义：
* 1. 整个数组数据分为两部分，已排序部分和未排序部分，其中已排序部分在前，未排序部分在后。
* 2. 从未排序部分的第一个元素开始，倒序与已排序部分元素相比。
* 3. 如果和当前比较的元素相比小的话，则说明找到了自己的位置，插入比较元素的后面一位。
* <p>
* 核心：
* 最好时间复杂度 O(n)
* 最坏时间复杂度 O(n^2)
* 平均时间复杂度 O(n^2)
* 空间复杂度 O(1)
* 稳定排序
*
* @author yangyi 2018年12月04日22:58:30
*/
public class InsertSort {
/**
* 从小到大排序
*/
public void insertSort(int[] ints) {
if (ints.length == 1) {
return;
}
//未排序部分-正序遍历
for (int i = 1; i < ints.length; i++) {
//将每一个元素都作为一个将要比较的值value
int value = ints[i];
int j = i - 1;
//已排序部分-倒序遍历
for (; j >= 0; j--) {
//让value这个值挨个去和已排序部分中的元素去比较，如果比有序部分中的某个元素小，说明找到了自己应有的问题
if (value < ints[j]) {
ints[j + 1] = ints[j];
} else {
break;
}
}
//有序部分的元素挪位置，value插进去
ints[j + 1] = value;
}
}
public static void main(String[] args) {
//准备30个0~100的随机数
int[] nums = new int[30000];
for (int i = 0; i < 30000; i++) {
nums[i] = (int) (Math.random() * 30000);
}
System.out.println("排序前：");
for (int num : nums) {
System.out.println(num);
}
InsertSort insertSort = new InsertSort();
insertSort.insertSort(nums);
System.out.println();
System.out.println("排序后：");
for (int num : nums) {
System.out.println(num);
}
}
}