比特麒麟

https://github.com/bitkylin

0%

经典排序算法及其 Java 实现

网上有很多排序算法的总结,不过有很多缺点,比如有些根本就是错的,无法通过测试用例,有些过于冗长。所以我总结了一套短小精悍的 Java 实现,经测试,该套实现可通过牛客网的关于此的所有测试用例。

1. 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
public class BubbleSort implements KySort {
public void kySort(int[] a, int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a, j, j + 1);
}
}
}
}
}

2. 插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
public class InsertSort implements KySort {
public void kySort(int[] a, int size) {
for (int i = 1; i < size; i++) {
int temp = a[i];
int j = i;
while (j > 0 && a[j - 1] > temp) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
}

3. 选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class SelectSort implements KySort {
public void kySort(int[] a, int size) {
for (int i = 0; i < size - 1; i++) {
int min = i;
for (int j = i + 1; j < size; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (i != min) {
swap(a, i, min);
}
}
}
}

4. 堆排序

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
public class HeapSort implements KySort {
public void kySort(int[] a, int n) {
for (int i = n / 2; i >= 0; i--) {
heapAdjust(a, i, n - 1);
}
for (int i = n - 1; i > 0; i--) {
swap(a, 0, i);
heapAdjust(a, 0, i - 1);
}
}

/**
* @param index 父节点索引
* @param n 尾节点索引
*/
private void heapAdjust(int[] a, int index, int n) {
int temp = a[index];
for (int child = index * 2 + 1; child <= n; child = index * 2 + 1) {
if (child < n && a[child] < a[child + 1]) {
child++;
}
if (temp > a[child]) break;
a[index] = a[child];
index = child;
}
a[index] = temp;
}
}

5. 归并排序

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
public class MergeSort implements KySort {
public void kySort(int[] a, int size) {
sort(a, 0, size - 1, new int[a.length]);
}

private void sort(int[] a, int left, int right, int[] temp) {
if (left >= right) return;
int mid = (left + right) / 2;
sort(a, left, mid, temp);
sort(a, mid + 1, right, temp);
merge(a, left, mid, right, temp);
}

private void merge(int[] a, int left, int mid, int right, int[] temp) {
int k = left;
int i = left;
int j = mid + 1;

while (i <= mid && j <= right) {
if (a[i] < a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
}
}
while (i <= mid) {
temp[k++] = a[i++];
}
while (j <= right) {
temp[k++] = a[j++];
}

while (left <= right) {
a[left] = temp[left];
left++;
}
}
}

6. 快速排序

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
public class QuickSort implements KySort {
@Override
public void kySort(int[] a, int size) {
quickSort(a, 0, size - 1);
}

private void quickSort(int[] a, int left, int right) {
if (right - left < 2) {
if (a[left] > a[right])
swap(a, left, right);
return;
}
int p = middleBy3(a, left, right);

quickSort(a, left, p - 1);
quickSort(a, p + 1, right);
}

private int middleBy3(int[] a, int left, int right) {
int p = (left + right) / 2;
int end = right;

if (a[left] > a[p]) swap(a, left, p);
if (a[left] > a[right]) swap(a, left, right);
if (a[p] > a[right]) swap(a, p, right);

int temp = a[p];
swap(a, p, right);

while (true) {
while (a[++left] < temp) ;
while (a[--right] > temp) ;
if (left >= right) break;
else swap(a, left, right);
}
swap(a, left, end);
return left;
}
}

7. 附录

7.1 交换方法

1
2
3
4
5
6
7
public class Util {
public static void swap(int[] a, int i, int j) {
int k = a[i];
a[i] = a[j];
a[j] = k;
}
}

7.2 基于策略模式的主程序实现

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
public class SortMain {
private static KySort sorter;
private int[] a;//定义一个数组

private SortMain(int... values) { //构造函数
a = values;
}

public static void main(String[] args) {
setSorter(new QuickSort());
SortMain arr;
arr = new SortMain(5, 4, 3, 2, 1, 0);
arr.display();
arr.kySort();
arr.display();
System.out.println("--------");
arr = new SortMain(54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28);
arr.display();
arr.kySort();
arr.display();
System.out.println("--------");
arr = new SortMain(32, 103, 24, 88, 95, 70, 97, 15, 102, 6, 79, 46, 51, 37, 93, 108, 9, 58, 53, 58, 79, 36, 58, 91, 78, 58, 61, 81); //初始化数组
arr.display();
arr.kySort();
arr.display();
}

private static void setSorter(KySort sorter) {
SortMain.sorter = sorter;
}

private void display() {
for (int i : a) { //遍历数组中每一个元素
System.out.print(i + " "); //展示
}
System.out.println();
}

private void kySort() {
sorter.kySort(a, a.length);
}
}