排序算法复习

排序算法的一些复习笔记。

顺便分享一个视频,群魔乱舞到秩序与整洁的变化挺爽的(小心精神污染):15 Sorting Algorithms in 6 Minutes - YouTube

冒泡排序

维基百科:

重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对n个项目需要O(n^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
43
44
45
46
47
48
49
50
51
52
53
54
55
package bubble;

import java.util.Random;

/**
* @author Boli Tao
*/
public class BubbleSort {
/**
* 交换 arr 数组中索引为 index1 和 index2 的值
*
* @param arr array
* @param index1 index1
* @param index2 index2
*/
public static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}

/**
* bubble sort
*
* @param arr the array to be sorted
*/
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}

public static void main(String[] args) {
Random random = new Random();
int[] array = new int[100000];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(Integer.MAX_VALUE);
}
bubbleSort(array);
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] < array[i]) {
throw new IllegalArgumentException("冒泡排序写错了");
}
}
System.out.println("Test complete.");
}
}

选择排序

冒泡排序比较的是相邻元素,而选择排序是比较整体,并且选择排序交换的是最小值和未经排序“头部”元素。其时间复杂度为 O(n^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
43
44
45
package selection;

/**
* @author Boli Tao
*/
public class SelectionSort {
/**
* 交换 arr 数组中索引为 index1 和 index2 的值
*
* @param arr array
* @param index1 index1
* @param index2 index2
*/
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}

public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr, i, min_idx);
}
}

public static void main(String[] args) {
int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
selectionSort(arr);
System.out.print("Sorted array:\n[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i != arr.length - 1) {
System.out.print(" ,");
}
}
System.out.print("]");
}
}

插入排序

插入排序通过找到合适位置进行插入达到排序目的。时间复杂度为 O(n^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
package insertion;

/**
* @author Boli Tao
*/
public class InsertionSort {
static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// 插入
arr[j + 1] = key;
}
}

public static void main(String[] args) {
int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
insertionSort(arr);
StringBuilder builder = new StringBuilder();
builder.append("Sorted array:\n[");
for (int i = 0; i < arr.length; i++) {
builder.append(arr[i]);
if (i != arr.length - 1) {
builder.append(" ,");
}
}
builder.append("]");
System.out.println(builder.toString());
}
}

归并排序

空间复杂度 O(n),时间复杂度 O(nlogn)。

演示:

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
package merge;

/**
* @author 陶波利
*/
public class MergeSort {
private static void merge(int[] arr, int l, int m, int r) {
int leftArraySize = m - l + 1;
// r - (m + 1) + 1
int rightArraySize = r - m;

// temp array
int[] leftTempArray = new int[leftArraySize];
int[] rightTempArray = new int[rightArraySize];

// 把 arr 中的数据拷入两个 temp 数组
for (int i = 0; i < leftArraySize; i++) {
leftTempArray[i] = arr[l + i];
}
for (int i = 0; i < rightArraySize; i++) {
rightTempArray[i] = arr[m + 1 + i];
}

// 两个 temp 数组的索引
int i = 0, j = 0;
// arr 数组的索引
int k = l;

// 将 temp 数组的数据按顺序填入 arr
while (i < leftArraySize && j < rightArraySize) {
if (leftTempArray[i] <= rightTempArray[j]) {
arr[k] = leftTempArray[i];
i++;
} else {
arr[k] = rightTempArray[j];
j++;
}
k++;
}

while (i < leftArraySize) {
arr[k] = leftTempArray[i];
i++;
k++;
}

while (j < rightArraySize) {
arr[k] = rightTempArray[j];
j++;
k++;
}
}

public static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}

public static void main(String[] args) {
int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
mergeSort(arr, 0, arr.length - 1);
StringBuilder builder = new StringBuilder();
builder.append("Sorted array:\n[");
for (int i = 0; i < arr.length; i++) {
builder.append(arr[i]);
if (i != arr.length - 1) {
builder.append(" ,");
}
}
builder.append("]");
System.out.println(builder.toString());
}
}

快速排序

快速排序相比冒泡排序,不是比较相邻元素,而是比较和交换大数和小数,做到把小数浮到上面、大数沉到下面。

快速排序不稳定,平均时间复杂度为 O(nlogn)。

演示:

代码:

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
package quick;

import java.util.Random;

/**
* @author 陶波利
*/
public class QuickSort {
/**
* 交换 arr 数组中索引为 index1 和 index2 的值
*
* @param arr array
* @param index1 index1
* @param index2 index2
*/
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}

private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int pivotIndex = left;
while (left < right) {
// 从右侧开始寻找比基准数小的元素的索引
while (left < right && arr[right] >= pivot) {
right--;
}
//从左侧开始寻找比基准数大的元素的索引
while (left < right && arr[left] <= pivot) {
left++;
}
// 把大数移到右边,小数移到左边
swap(arr, left, right);
}
// 把 pivot 移到中间
swap(arr, pivotIndex, left);
return left;
}

private static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pi = partition(arr, left, right);
quickSort(arr, left, pi - 1);
quickSort(arr, pi + 1, right);
}

public static void sort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}

public static void main(String[] args) {
Random random = new Random();
int[] array = new int[1000000];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(Integer.MAX_VALUE);
}
sort(array);
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] < array[i]) {
throw new IllegalArgumentException("快排写错了");
}
}
}
}

堆排序

平均时间复杂度为 O(nlogn)。

自己实现一个最大堆,所有的问题都迎刃而解。

代码:

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
package heap;

import array.Array;

import java.util.Random;

/**
* @author 陶波利
*/
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;

public MaxHeap(int capacity) {
data = new Array<>(capacity);
}

public MaxHeap() {
data = new Array<>();
}

/**
* 构造函数:将传入数组组成为最大堆
*
* @param arr 待化为最大堆的数组
*/
public MaxHeap(E[] arr) {
data = new Array<>(arr);
for (int i = parent(arr.length - 1); i >= 0; i--) {
siftDown(i);
}
}

public int size() {
return data.getSize();
}

public boolean isEmpty() {
return data.isEmpty();
}

/**
* @param index index
* @return index 的父节点的索引
*/
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("index 0 doesn't have parent.");
}
return (index - 1) / 2;
}

private int leftChild(int index) {
return index * 2 + 1;
}

private int rightChild(int index) {
return index * 2 + 2;
}

/**
* 向堆中添加元素
*
* @param e 待添加的元素值
*/
public void add(E e) {
data.addLast(e);
siftUp(data.getSize() - 1);
}

/**
* 为满足最大堆性质而设计的元素上浮方法
*
* @param k 需要被上浮的元素索引
*/
private void siftUp(int k) {
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
data.swap(k, parent(k));
k = parent(k);
}
}

/**
* 取出堆中最大元素
*
* @return
*/
public E extractMax() {
E ret = getMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}

public E getMax() {
if (data.getSize() == 0) {
throw new IllegalArgumentException("Size is 0, no element in heap.");
}
return data.get(0);
}

/**
* 为满足最大堆性质而设计的元素下沉方法
* TODO: 需要进一步理解
*
* @param k 需要被下沉的元素索引
*/
private void siftDown(int k) {
while (leftChild(k) < data.getSize()) {
int j = leftChild(k);
if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j = rightChild(k);
}
// ↑此时 j 表示孩子节点中更大元素的索引
if (data.get(k).compareTo(data.get(j)) > 0) {
break;
}
data.swap(k, j);
k = j;
}
}

public E replace(E e) {
E ret = getMax();
data.set(0, e);
siftDown(0);
return ret;
}

/**
* 测试类
*
* @param args args
*/
public static void main(String[] args) {
int n = 1000000;
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.extractMax();
}
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[i]) {
throw new IllegalArgumentException("Error: 最大堆实现出现问题!");
}
}
System.out.println("Completed!");
}
}

自定义的 Array 类如下:

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
package array;

/**
* 自定义的 Array 类
*
* @author 陶波利
*/
public class Array<E> {
private E[] data;
private int size;

public Array() {
this(10);
}

public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}

public Array(E[] arr) {
data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
size = arr.length;
}

public int getSize() {
return size;
}

public int getCapacity() {
return data.length;
}

public boolean isEmpty() {
return size == 0;
}

public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get() failed, index is illegal.");
}
return data[index];
}

public void set(int index, E value) {
data[index] = value;
}

public boolean isContaianed(E value) {
for (E m : data) {
if (value.equals(m)) {
return true;
}
}
return false;
}

public int find(E value) {
for (int i = 0; i < data.length; i++) {
if (value.equals(data[i])) {
return i;
}
}
return -1;
}

public void add(int index, E value) {
// if (size >= data.length) {
// throw new IllegalArgumentException("add() method failed, array is full.");
// }
if (index < 0 || index > size) {
throw new IllegalArgumentException("add() failed. Requirement: 0 <=index <= size.");
}
if (size == data.length) {
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = value;
size++;
}

private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}

public void addFirst(E value) {
add(0, value);
}

public void addLast(E value) {
add(size, value);
}

public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove() failed, index is illegal.");
}
E removedValue = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
// loitering objects != memory leak
data[size] = null;
if (size == data.length / 4 && data.length / 2 != 0) {
// TODO: / 4?
resize(data.length / 2);
}
return removedValue;
}

public E removeFirst() {
return remove(0);
}

public E removeLast() {
return remove(size - 1);
}

public void removeElement(E value) {
int index = find(value);
if (-1 != index) {
remove(index);
}
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
builder.append("[");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}

public E getLast() {
return get(size - 1);
}

public E getFirst() {
return get(0);
}

/**
* 交换索引为 i j 的元素
*
* @param i index i
* @param j index j
*/
public void swap(int i, int j) {
if (i < 0 || i >= size || j < 0 || j >= size) {
throw new IllegalArgumentException("Index is illegal");
}
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}

希尔排序

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
package shell;

import java.util.Random;

/**
* @author 陶波利
*/
public class ShellSort {
private static void shellInsert(int[] arr, int d) {
for (int i = d; i < arr.length; i++) {
int j = i - d;
//记录要插入的数据
int temp = arr[i];
//从后向前,找到比其小的数的位置
while (j >= 0 && arr[j] > temp) {
//向后挪动
arr[j + d] = arr[j];
j -= d;
}
//存在比其小的数
if (j != i - d) {
arr[j + d] = temp;
}
}
}

public static void shellSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int d = arr.length / 2;
while (d >= 1) {
shellInsert(arr, d);
d /= 2;
}
}

public static void main(String[] args) {
Random random = new Random();
int[] array = new int[1000000];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(Integer.MAX_VALUE);
}
shellSort(array);
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] < array[i]) {
throw new IllegalArgumentException("希尔排序写错了");
}
}
System.out.println("Test complete.");
}
}

参考:
Sorting Algorithms - GeeksforGeeks
francistao/LearningNotes: Enjoy Learning.
VisuAlgo - visualising data structures and algorithms through animation
排序算法 - 维基百科,自由的百科全书

Author: Boli Tao
Link: https://www.bolitao.xyz/archives/8d5e9fff.html
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.