重生之我在Java学斩神。
汇总
关于稳定性和占用内存的说明：
- 稳定性：如果
A = B，排序前A在B前面，排序后A也在B前面，则为稳定；如果出现了排序后A在B后面的情况，则为不稳定。
- 占用内存：
in代表占用常数内存，不消耗额外内存；out代表消耗常数内存。
开始
笔记中使用了自定义的类，分别是SortEnum枚举类和SortUtil工具类。
SortEnum枚举类如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public enum SortEnum {
BUBBLE("冒泡排序"),
SELECTION("选择排序"),
INSERTION("插入排序"),
SHELL("希尔排序"),
MERGE("归并排序"),
QUICK("快速排序"),
HEAP("堆排序"),
COUNTING("计数排序"),
BUCKET("桶排序"),
RADIX("基数排序");
private final String name;
SortEnum(String name) {
this.name = name;
}
public String getName() {
return name;
}
}
|
SortUtil工具类如下：
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
|
public class SortUtil {
private static final int[] TEST_ARRAY = {67, 21, 38, 10, 90, 30, 70, 77, 44, 58, 71, 31, 12, 68, 13};
private static void print(SortEnum sort, int[] arr) {
System.out.print(sort.getName());
System.out.print(": [");
for (int i : arr) {
System.out.print(i + ", ");
}
System.out.println("\b\b]");
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void sort(SortEnum sort) {
int[] arr = TEST_ARRAY.clone();
switch (sort) {
case BUBBLE -> BubbleSort.sort(arr);
case SELECTION -> SelectionSort.sort(arr);
case INSERTION -> InsertionSort.sort(arr);
case SHELL -> ShellSort.sort(arr);
case MERGE -> MergeSort.sort(arr);
case QUICK -> QuickSort.sort(arr);
case HEAP -> HeapSort.sort(arr);
default -> {
System.out.println("未知排序算法");
return;
}
}
print(sort, arr);
}
}
|
在使用时直接通过 SortUtil 调用 SortEnum 即可：
1
2
3
| public static void main(String[] args) {
SortUtil.sort(SortEnum.SELECT);
}
|
⭐冒泡排序
从头开始比较相邻元素，如果第一个元素比第二个元素大，就交换它们两个，直到最后一个元素，这样最后一个就是整个数组中最大的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class BubbleSort {
public static void sort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtil.swap(arr, j, j + 1);
}
}
}
}
}
|
⭐选择排序
在序列中找到最小/最大的元素，存放到序列的起始位置，然后再继续找到最小/最大的元素，放到已排序好的序列结尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class SelectionSort {
public static void sort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
int minIndex = i;
for (int j = i + 1; j < len; j++) {
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
if(minIndex!= i) {
SortUtil.swap(arr, i, minIndex);
}
}
}
}
|
⭐插入排序
将第一个元素视为已排序好的序列。选择下一个元素，并在已排序好的序列中从后往前扫描，直到找到比该元素小的元素，将该元素插入到其之后。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class InsertionSort {
public static void sort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j;
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
}
|
🔋希尔排序
设置一个增量gap（一般是数组长度/2），将整个序列分为gap个子序列，分别对子序列进行插入排序。然后将增量设置为gap=gap/2，再对排序了一次的序列分割成gap个子序列，继续进行插入排序。直到gap=1时再进行一次插入排序即可完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class ShellSort {
public static void sort(int[] arr) {
int len = arr.length;
for(int gap = len / 2; gap > 0; gap /= 2){
for (int i = gap; i < len; i++) {
int temp = arr[i];
int j;
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
}
}
|
🔋归并排序
对序列进行递归再合并，即为归并。将长度为n序列持续递归分割为两个长度为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
| public class MergeSort {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
System.arraycopy(temp, 0, arr, left, temp.length);
}
}
|
⭐快速排序
选择一个基准pivot。将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面。该操作结束之后，该基准就处于数列的中间位置(分区partition)。然后递归的进行上述操作即可。
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
| public class QuickSort {
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, 0, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
for (int j = i; j <= right && arr[j] < pivot; j++) {
SortUtil.swap(arr, i++, j);
}
SortUtil.swap(arr, left, i - 1);
return i - 1;
}
}
|
🔋堆排序
首先构建一个大根堆或小根堆，然后将堆顶元素和堆的最后一个元素进行交换。交换完成后，需要再次调整堆，使其满足大根堆或小根堆的特性。
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 HeapSort {
private static int len;
public static void sort(int[] arr) {
len = arr.length;
for (int i = len / 2 - 1; i >= 0; i--) {
modifyHeap(arr, i);
}
for (int i = len - 1; i > 0; i--) {
SortUtil.swap(arr, 0, len - 1);
len--;
modifyHeap(arr, 0);
}
}
private static void modifyHeap(int[] arr, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest!= index) {
SortUtil.swap(arr, index, largest);
modifyHeap(arr, largest);
}
}
}
|
计数排序
首先，我们需要找出数组中的最大值 max 或者最小值 min，然后创建一个计数数组 countArray，数组长度为 max - min + 1，元素默认值为0。通过遍历原数组 arr，以 arr[i] - min作为 countArray 的索引，arr[i]在 arr 出现的次数作为对应的值。最后遍历 countArray，只要索引不为0，将对应的 value 加上min输出返回到原数组即可。
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
| public class CountingSort {
public static void sort(int[] arr) {
if (arr.length < 2) return;
int min = arr[0], max = arr[0];
if (value < min) {
min = value;
} else if (value > max) {
max = value;
}
}
int[] countArray = new int[max - min + 1];
for (int i : arr) {
countArray[i - min]++;
}
for (int arrIndex = 0, countIndex = 0; countIndex < countArray.length; countIndex++) {
while (countArray[countIndex]-- > 0) {
arr[arrIndex++] = countIndex + min;
}
}
}
}
|
桶排序
首先需要设置一个 bucketSize，决定每个 bucket 能放置多少数值。然后遍历数组，将值放到对应的 bucket 里面。接着对每个非空的 bucket 进行排序，最后将 bucket 拼接即可完成排序。
bucketSize 的大小至关重要，性能最好时每个桶都能均匀放置所有数值。
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
|
private static final int BUCKET_SIZE = 20;
public static void sort(int[] arr) {
if (arr.length < 2) return;
List<Integer> list = new ArrayList<>();
for (int value : arr) {
list.add(value);
}
list = sort(list, BUCKET_SIZE);
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
}
private static List<Integer> sort(List<Integer> list, int bucketSize) {
if (list.size() < 2 || bucketSize == 0) {
return list;
}
int min = list.get(0), max = list.get(0);
for (Integer integer : list) {
if (integer < min) {
min = integer;
} else if (integer > max) {
max = integer;
}
}
int bucketCount = (max - min) / bucketSize + 1;
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
for (Integer integer : list) {
int index = (integer - min) / bucketSize;
buckets.get(index).add(integer);
}
for (int i = 0; i < bucketCount; i++) {
if (!buckets.get(i).isEmpty()) {
buckets.set(i, sort(buckets.get(i), bucketSize / 2));
}
}
List<Integer> result = new ArrayList<>();
for (List<Integer> bucket : buckets) {
result.addAll(bucket);
}
return result;
}
|
基数排序
基数排序需要先获取数组中的最大值 max，然后计算出max的位数，即为迭代次数 n。然后新建一个二维数组 radix，其一维长度为 10，然后遍历数组，根据数组每一位的值放入 radix。最后将 radix遍历并赋值给原数组，重复 n 次即可。
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
| public static void sort(int[] arr) {
if (arr.length < 2) return;
int max = 0;
for (int value : arr) {
if (value > max) {
max = value;
}
}
int n = 0;
while (max != 0) {
max /= 10;
n++;
}
for (int i = 0; i < n; i++) {
List<List<Integer>> radix = new ArrayList<>();
for (int j = 0; j < 10; j++) {
radix.add(new ArrayList<>());
}
for (int value : arr) {
int digit = (value / (int) Math.pow(10, i)) % 10;
radix.get(digit).add(value);
}
int index = 0;
for (List<Integer> list : radix) {
for (int value : list) {
arr[index++] = value;
}
}
}
}
|
总结
以下是在不同数据量的情况下合适的排序算法：
- 低数据量：插入排序或选择排序。插入排序具有稳定性，选择排序的效率高于插入排序。
- 中数据量：希尔排序。
- 高数据量：快速排序、归并排序或堆排序。快速排序适合元素分布随机，归并排序具有稳定性，堆排序适合元素分布接近排序好的情况。
