-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathASort.java
More file actions
80 lines (72 loc) · 1.75 KB
/
ASort.java
File metadata and controls
80 lines (72 loc) · 1.75 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
package algorithm.sort;
public class ASort {
public static void main(String[] args) {
}
/*
* Time:
* Best Case: O(n2)
* Average Case: O(n2)
* Worst Case: O(n2)
* Stable: No
*/
public static void selectionSort(int[] a) {
// find the 0, 1, 2, ... n-1 minimal element
for (int i = 0; i < a.length - 1; i++) {
int index = i;
// find minimum element in [i, a.length - 1]
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[i]) {
index = j;
}
}
// swap i and index element
if (i != index) {
int tmp = a[index];
a[i] = tmp;
a[index] = a[i];
}
}
}
/*
* Time:
* Best Case: O(n)
* Average Case: O(n2)
* Worst Case: O(n2)
* Stable: Yes
*/
public static void bubbleSort(int[] a) {
boolean flag = true;
while (flag) {
flag = false;
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i+1]) {
flag = true;
swap(a[i], a[i+1]);
}
}
}
}
/*
* Time:
* Best Case: O(n)
* Average Case: O(n2)
* Worst Case: O(n2)
* Stable: Yes
*/
public static void insertSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i -1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
public static void swap(int a, int b) {
int tmp = a;
a = b;
b = tmp;
}
}