forked from mood321/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSelectSort.java
More file actions
193 lines (170 loc) · 5.48 KB
/
Copy pathSelectSort.java
File metadata and controls
193 lines (170 loc) · 5.48 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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
package Conllection;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int a[] = {5, 2, 8, 4, 1, 9, 16};
System.out.println("冒泡排序法:" + Arrays.toString(bubble(a)));
int b[] = {5, 2, 8, 4, 1, 9, 16};
System.out.println("选择排序法" + Arrays.toString(select(b)));
int c[] = {5, 2, 8, 4, 1, 9, 16};
System.out.println("插入排序法" + Arrays.toString(insert(c)));
int d[] = {5, 2, 8, 4, 1, 9, 16};
mergeSort(d);
System.out.println("归并排序法" + Arrays.toString(d));
System.out.println("二分 位置:" + find(bubble(a), 8));
}
/**
* 归并排序法 主函数
*
* @param arr
*/
public static void mergeSort(int[] arr) {
// 归并排序 是一个递归二分拆分O(log2(N)) 拿到两个有序数组 合并成一个有序 O(N) 时间是O(N*Log2(N)) 空间O(n)
// 稳定
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
/**
* 归并排序法 分治 并合并拆开的结果集
*
* @param arr
* @param l
* @param r
*/
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) { // base case
return;
}
int mid = l + (r - l) / 2;// 中间拆分
mergeSort(arr,l,mid); // 左边 排序
mergeSort(arr, mid+1, r); // 右边
merge(arr,l,mid,r);// 合并排序逻辑
}
/**
* 归并排序法 对数组 起始位置l 结束r 中间点m 两段进行合并排序
*
* @param arr
* @param l
* @param m
* @param r
*/
public static void merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1]; //辅助数组
int i = 0;
int p1 = l;
int p2 = m + 1;
// 四段逻辑
// 1 双指针排序
while (p1<= m && p2<= r){
// 谁小 放到辅助数组
help[i++]=arr[p1]<arr[p2] ?arr[p1++]:arr[p2++];
}
// 2 如果左边没跑完
while (p1<=m){
help[i++]=arr[p1++];
}
// 3 右边没跑完
while (p2<= r){
help[i++]=arr[p2++] ;
}
// 4 回写
for (int i1 = 0; i1 < help.length; i1++) {
arr[l++]=help[i1];
}
}
/**
* 二分查找
*
* @param a
* @param i
* @return
*/
private static int find(int[] arr, int i) {
int L = 0, R = arr.length; // 最左最右
while (L <= R) { // 边界问题
int mid = L + (R - L) / 2; // 中位数
if (i < arr[mid]) {
R = mid - 1; // 来到左边
} else if (i > arr[mid]) {
L = mid + 1; // 来到右边
} else {
return mid;
}
}
return arr.length;
}
/**
* 插入算法
* 从 1 开始向前 检查 如果检查位置下标（work）大于0 而且比work-1 小 work-1的值给work work向前继续检查
* <p>
* 在计算时间复杂度时 有几种情况
* 原数组已经拍好序 为(最好情况) O(n)
* 原数组顺序为倒叙 为(最坏情况) O(n^2)
*
* @param arr
* @return
*/
private static int[] insert(int[] arr) {
if (arr == null || arr.length < 2) {
return arr;
}
// 思路： 找到从 1 开始找work 应该在的位置 比work小的 放在前面
//待排元素小于有序序列的最后一个元素时，向前插入
// 插入 值判断 小于 稳定
for (int i = 1; i < arr.length; i++) {
int work = i;
while (work > 0 && arr[work] < arr[work - 1]) {
swarp(arr, work, work - 1);
work--;
}
}
return arr;
}
/**
* 选择排序法
* 核心算法: 找出起始位置（i）到最后位置 最小的数 和起初位置交换
*
* @param b
* @return
*/
private static int[] select(int[] b) {
if (b == null || b.length < 2) {
return b;
}
// 选择 排序 每次选择一个最小 放在当前位置 两次for O(N^2)
// 因为 要找到 最小值 这个最小值不一定是第一个最小值 所以不稳定
for (int i = 0; i < b.length - 1; i++) { // 最后一次 循环 自己一定是最小 可不用计算
int min = i;
for (int j = i + 1; j < b.length; j++) { //
min = b[j] < b[min] ? j : min;
}
if (b[i] != b[min]) // 最小不是 本身 交换
swarp(b, i, min);
}
return b;
}
/**
* 冒泡排序法
*/
private static int[] bubble(int[] a) {
if (a.length == 0) {
return null;
}
// 思路 ， i 与i+1 比较 大的放后面 两次for O(n^2) 稳定
for (int i = 0; i < a.length - 1; i++) { // 最后一个值不参与 循环
for (int i1 = 0; i1 < a.length - 1; i1++) { // 与i 循环次数一致
if (a[i1] > a[i1 + 1]) {
swarp(a, i1, i1 + 1);
}
}
}
return a;
}
private static void swarp(int[] a, int j, int i) {
int tem = a[j];
a[j] = a[i];
a[i] = tem;
}
}