冒泡排序

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
public class PopSort {

/**
* perform pop sort
* differ from basic pop sort we use a edge to minimize unnecessary compare and swap
* @param array
*/
private static void popSort(int[] array) {
int len = array.length;
for (; len >= 2; ) {
int edge = 0;
for (int j = 0; j < len - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
edge = j + 1;
}
}
len = edge;
}
}

private static void swap(int[] array, int src, int tar) {
int tmp = array[src];
array[src] = array[tar];
array[tar] = tmp;
}

public static void main(String[] args) {
int[] arrayWithEvenLength = new int[] {-1, 2, 3, 8, 10, 5};
popSort(arrayWithEvenLength);
Assert.assertArrayEquals(new int[] {-1, 2, 3, 5, 8, 10}, arrayWithEvenLength);

int[] arrayWithOldLength = new int[] {-1, 2, 3, 8, 10, 5, -1};
popSort(arrayWithOldLength);
Assert.assertArrayEquals(new int[] {-1, -1, 2, 3, 5, 8, 10}, arrayWithOldLength);

int[] arrayWithDescentOrder = new int[] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
popSort(arrayWithDescentOrder);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithDescentOrder);

int[] arrayWithAscentOrder = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
popSort(arrayWithAscentOrder);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithAscentOrder);

int[] arrayWithAllEquals = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
popSort(arrayWithAllEquals);
Assert.assertArrayEquals(new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, arrayWithAllEquals);
}
}

堆排序

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
public class HeapSort {

/**
* perform heap sort
*
* @param array
*/
private static void heapSort(int[] array) {
buildHeap(array, array.length);
swap(array, 0, array.length - 1);

int heapLength = array.length - 1;
while (heapLength > 1) {
buildHeap(array, heapLength);
swap(array, 0, heapLength - 1);
heapLength--;
}
}

/**
* heapfy the array[0:len]
*
* @param array target array
* @param len length of element, array[len] is exclusive
*/
private static void buildHeap(int[] array, int len) {
int beginIndex = (len - 1) >> 1;
for (int i = beginIndex; i >= 0; i--) {
int maxIndex = getMaxIndex(array, i, len);
if (i != maxIndex) {
swap(array, maxIndex, i);
}
}
}

/**
* perform get index for the max value within
* array[i] and array[(i << 1) + 1], array[(i + 1) << 1]
* just the virtual root and children
*
* @param array
* @param i
* @param length
* @return
*/
private static int getMaxIndex(int[] array, int i, int length) {
int maxIndex = i;
int left = (i << 1) + 1;
int right = (i + 1) << 1;
if (left < length && array[maxIndex] < array[left]) {
maxIndex = left;
}
if (right < length && array[maxIndex] < array[right]) {
maxIndex = right;
}
return maxIndex;
}

private static void swap(int[] array, int src, int tar) {
int tmp = array[src];
array[src] = array[tar];
array[tar] = tmp;
}

private static void printArray(int[] array) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < array.length; i++) {
sb.append(array[i]).append(" ");
}
System.out.println(sb.toString());
}

public static void main(String[] args) {
int[] arrayWithEvenLength = new int[] {-1, 2, 3, 8, 10, 5};
heapSort(arrayWithEvenLength);
Assert.assertArrayEquals(new int[] {-1, 2, 3, 5, 8, 10}, arrayWithEvenLength);

int[] arrayWithOldLength = new int[] {-1, 2, 3, 8, 10, 5, -1};
heapSort(arrayWithOldLength);
Assert.assertArrayEquals(new int[] {-1, -1, 2, 3, 5, 8, 10}, arrayWithOldLength);

int[] arrayWithDescentOrder = new int[] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
heapSort(arrayWithDescentOrder);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithDescentOrder);

int[] arrayWithAscentOrder = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
heapSort(arrayWithAscentOrder);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithAscentOrder);

int[] arrayWithAllEquals = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
heapSort(arrayWithAllEquals);
Assert.assertArrayEquals(new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, arrayWithAllEquals);
}
}

快速排序

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
public class QuickSort {

/**
* Perform partition array[start:end], both start and end are inclusive,
* with seed = array[start]
*
* @param array
* @param start
* @param end
* @return partition Index
*/
private static int partition(int[] array, int start, int end) {
int seed = array[start];
int storeIndex = start;
for (int i = start + 1; i <= end; i++) {
if (array[i] < seed) {
storeIndex++;
swap(array, storeIndex, i);
}
}

swap(array, start, storeIndex);
return storeIndex;
}

/***
* both start and end are inclusive
* @param array
* @param start
* @param end
*/
private static void rqsort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int storeIndex = partition(array, start, end);

rqsort(array, start, storeIndex - 1);
rqsort(array, storeIndex + 1, end);
}

/**
* Perform quick sort recursively
*
* @param array
*/
private static void recursionQSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
rqsort(array, 0, array.length - 1);
}

/**
* Internal class for iterative quick sort stack
*/
private static class IterArrayInfo {
int start;
int end;

IterArrayInfo(int start, int end) {
this.start = start;
this.end = end;
}
}

/**
* Perform quick sort iteratively
*
* @param array
*/
private static void iterativeQSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
Stack<IterArrayInfo> iterArrayInfoStack = new Stack<>();

iterArrayInfoStack.push(new IterArrayInfo(0, array.length - 1));

while (!iterArrayInfoStack.empty()) {
IterArrayInfo iterArrayInfo = iterArrayInfoStack.pop();
int storeIndex = partition(array, iterArrayInfo.start, iterArrayInfo.end);
if (storeIndex > iterArrayInfo.start + 1) {
iterArrayInfoStack.push(new IterArrayInfo(iterArrayInfo.start, storeIndex - 1));
}
if (storeIndex + 1 < iterArrayInfo.end) {
iterArrayInfoStack.push(new IterArrayInfo(storeIndex + 1, iterArrayInfo.end));
}
}
}

private static void swap(int[] array, int src, int tar) {
int tmp = array[src];
array[src] = array[tar];
array[tar] = tmp;
}

public static void main(String[] args) {
int[] arrayWithEvenLength = new int[] {-1, 2, 3, 8, 10, 5};
iterativeQSort(arrayWithEvenLength);
Assert.assertArrayEquals(new int[] {-1, 2, 3, 5, 8, 10}, arrayWithEvenLength);

int[] arrayWithOldLength = new int[] {-1, 2, 3, 8, 10, 5, -1};
iterativeQSort(arrayWithOldLength);
Assert.assertArrayEquals(new int[] {-1, -1, 2, 3, 5, 8, 10}, arrayWithOldLength);

int[] arrayWithDescentOrder = new int[] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
iterativeQSort(arrayWithDescentOrder);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithDescentOrder);

int[] arrayWithAscentOrder = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
iterativeQSort(arrayWithAscentOrder);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithAscentOrder);

int[] arrayWithAllEquals = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
iterativeQSort(arrayWithAllEquals);
Assert.assertArrayEquals(new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, arrayWithAllEquals);

int[] arrayWithEvenLength1 = new int[] {-1, 2, 3, 8, 10, 5};
recursionQSort(arrayWithEvenLength1);
Assert.assertArrayEquals(new int[] {-1, 2, 3, 5, 8, 10}, arrayWithEvenLength1);

int[] arrayWithOldLength1 = new int[] {-1, 2, 3, 8, 10, 5, -1};
recursionQSort(arrayWithOldLength1);
Assert.assertArrayEquals(new int[] {-1, -1, 2, 3, 5, 8, 10}, arrayWithOldLength1);

int[] arrayWithDescentOrder1 = new int[] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
recursionQSort(arrayWithDescentOrder1);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithDescentOrder1);

int[] arrayWithAscentOrder1 = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
recursionQSort(arrayWithAscentOrder1);
Assert.assertArrayEquals(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, arrayWithAscentOrder1);

int[] arrayWithAllEquals1 = new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
recursionQSort(arrayWithAllEquals1);
Assert.assertArrayEquals(new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, arrayWithAllEquals1);
}
}