Skip to content

Commit 48b0745

Browse files
linwtlinwt
committed
十大排序算法
1 parent 87b4d20 commit 48b0745

File tree

12 files changed

+141
-92
lines changed

12 files changed

+141
-92
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,3 +6,4 @@
66
- [2017校招真题编程题汇总](https://www.nowcoder.com/ta/2017test)
77
- [2019校招真题编程题汇总](https://www.nowcoder.com/ta/2019test)
88
- [数据库SQL实战](https://www.nowcoder.com/ta/sql?query=&asc=true&order=&page=1)
9+
- [十大经典排序算法动画与解析](https://mp.weixin.qq.com/s/vn3KiV-ez79FmbZ36SX9lg)

‎十大排序算法/README.md

Lines changed: 0 additions & 1 deletion
This file was deleted.

‎十大排序算法_Java/Bubble.java

Lines changed: 11 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,16 @@
11
package sort;
22

3-
// 冒泡排序
3+
/*
4+
冒泡排序：
5+
1、第一个for循环表示外循环次数，将所有元素都排序需要的循环次数
6+
第二个for循环表示内循环次数，将一个元素排序需要的循环次数。一轮循环中从左到右将一个大数交换到后面
7+
2、flag标记一次排序过程是否发生元素位置交换，若没有交换说明已经排序好了，直接结束
8+
*/
49
public class Bubble {
510
public int[] bubbleSort(int[] nums) {
611
int n = nums.length;
7-
// 外循环次数
812
for (int i = 0; i < n - 1; i++) {
9-
// 标记一次排序过程是否发生元素位置交换
1013
boolean flag = true;
11-
// 内循环次数
1214
for (int j = 0; j < n - i - 1; j++) {
1315
if (nums[j] > nums[j + 1]) {
1416
int temp = nums[j];
@@ -17,7 +19,9 @@ public int[] bubbleSort(int[] nums) {
1719
flag = false;
1820
}
1921
}
20-
if (flag) break;
22+
if (flag) {
23+
break;
24+
}
2125
}
2226
return nums;
2327
}
@@ -26,7 +30,8 @@ public static void main(String[] args) {
2630
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
2731
Bubble bubble = new Bubble();
2832
nums = bubble.bubbleSort(nums);
29-
for (int num : nums)
33+
for (int num : nums) {
3034
System.out.println(num);
35+
}
3136
}
3237
}

‎十大排序算法_Java/Bucket.java

Lines changed: 15 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -2,36 +2,37 @@
22

33
import java.util.Arrays;
44

5-
// 桶排序
5+
/*
6+
桶排序：
7+
1、获取数组最大值、最小值，以数值范围定义桶数组stats大小，数组默认值为0
8+
2、以数值个数定义结果数组res大小，数组默认值为0
9+
3、遍历元素，映射到桶中，统计每个数的出现次数
10+
4、遍历每个桶，按序获取数字放到结果数组
11+
*/
612
public class Bucket {
713
public int[] bucketSort(int[] nums) {
8-
// 获取数组最大值、最小值
914
int max = Arrays.stream(nums).max().getAsInt();
1015
int min = Arrays.stream(nums).min().getAsInt();
11-
12-
// 以数值范围定义数组大小
1316
int[] stats = new int[max - min + 1];
14-
Arrays.fill(stats, 0);
15-
// 以数值个数定义的数组大小
1617
int[] res = new int[nums.length];
17-
Arrays.fill(res, 0);
18-
19-
// 统计每个数的出现次数
20-
for(int num : nums)
18+
for(int num : nums) {
2119
stats[num - min]++;
22-
// 遍历每个桶，按序获取数字放到结果数组
20+
}
2321
int k = 0;
24-
for (int i = 0; i < stats.length; i++)
25-
for (int j = 0; j < stats[i]; j++)
22+
for (int i = 0; i < stats.length; i++) {
23+
for (int j = 0; j < stats[i]; j++) {
2624
res[k++] = min + i;
25+
}
26+
}
2727
return res;
2828
}
2929

3030
public static void main(String[] args) {
3131
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
3232
Bucket bucket = new Bucket();
3333
nums = bucket.bucketSort(nums);
34-
for (int num : nums)
34+
for (int num : nums) {
3535
System.out.println(num);
36+
}
3637
}
3738
}

‎十大排序算法_Java/Count.java

Lines changed: 14 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,23 +2,26 @@
22

33
import java.util.Arrays;
44

5-
// 计数排序
5+
/*
6+
计数排序：
7+
1、获取数组最大值、最小值，以数值范围定义桶数组stats大小，数组默认值为0
8+
2、以数值个数定义结果数组res大小，数组默认值为0
9+
3、遍历元素，映射到桶中，统计每个数的出现次数
10+
4、遍历桶，滚动累加，此时桶值表示包括当前元素 前面总共有多少个元素，即表示元素在结果数组中的索引位置
11+
5、遍历元素，映射到桶中获取元素的最终索引，将元素存入结果数组。桶中该元素的索引位置减1，表示下一个同样的元素存放的位置
12+
*/
613
public class Count {
714
public int[] countSort(int[] nums) {
815
int max = Arrays.stream(nums).max().getAsInt();
916
int min = Arrays.stream(nums).min().getAsInt();
10-
1117
int[] stats = new int[max - min + 1];
12-
Arrays.fill(stats, 0);
1318
int[] res = new int[nums.length];
14-
Arrays.fill(res, 0);
15-
16-
for (int num : nums)
19+
for (int num : nums) {
1720
stats[num - min]++;
18-
// 记录每个数字存放的索引位置
19-
for (int i = 1; i < nums.length; i++)
21+
}
22+
for (int i = 1; i < stats.length; i++) {
2023
stats[i] += stats[i - 1];
21-
// 获取每个数字的最终索引并存入结果数组
24+
}
2225
for (int num : nums) {
2326
res[stats[num - min] - 1] = num;
2427
stats[num - min]--;
@@ -31,7 +34,8 @@ public static void main(String[] args) {
3134
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
3235
Count count = new Count();
3336
nums = count.countSort(nums);
34-
for (int num : nums)
37+
for (int num : nums) {
3538
System.out.println(num);
39+
}
3640
}
3741
}

‎十大排序算法_Java/Heap.java

Lines changed: 17 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
11
package sort;
22

33
/*
4-
1、堆：堆本质上就是一棵完全二叉树，它的每一个节点都必须大于或者小于其子节点
5-
2、最大堆：每个节点都大于或者等于子树所有节点的堆称为最大堆
6-
最小堆：每个节点都小于或者等于子树所有节点的堆称为最小堆
4+
1、堆：堆本质上就是一棵完全二叉树，它的每一个节点都必须大于等于或者小于等于其子节点
5+
2、最大堆：每个节点都大于等于子树所有节点的堆称为最大堆
6+
最小堆：每个节点都小于等于子树所有节点的堆称为最小堆
77
3、数组存储堆，节点的索引关系如下
88
索引角度：起始索引为0，某个节点在数组中的索引为i，则其（直接看索引，好记）
99
1）父节点索引：(i-1)/2
@@ -51,11 +51,13 @@ private void maxHeapify(int[] nums, int root) {
5151
// 索引从0开始
5252
int left = root * 2 + 1, right = root * 2 + 2;
5353
// 如果有左孩子，且左孩子大于父节点，则将最大指针指向左孩子
54-
if (left < n && nums[left] > nums[maxIndex])
54+
if (left < n && nums[left] > nums[maxIndex]) {
5555
maxIndex = left;
56+
}
5657
// 如果有右孩子，且右孩子大于父节点和左孩子，则将最大指针指向右孩子
57-
if (right < n && nums[right] > nums[maxIndex])
58+
if (right < n && nums[right] > nums[maxIndex]) {
5859
maxIndex = right;
60+
}
5961
// 如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置
6062
if (maxIndex != root) {
6163
swap(nums, maxIndex, root);
@@ -73,8 +75,9 @@ public static void main(String[] args) {
7375
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
7476
Heap heap = new Heap();
7577
nums = heap.heapSort(nums);
76-
for (int num : nums)
78+
for (int num : nums) {
7779
System.out.println(num);
80+
}
7881
}
7982
}
8083

@@ -99,10 +102,12 @@ public int[] heapSort(int[] nums) {
99102
private void maxHeapify(int[] nums, int root) {
100103
int maxIndex = root;
101104
int left = root * 2 + 1, right = root * 2 + 2;
102-
if (left < n && nums[left] > nums[maxIndex])
105+
if (left < n && nums[left] > nums[maxIndex]) {
103106
maxIndex = left;
104-
if (right < n && nums[right] > nums[maxIndex])
107+
}
108+
if (right < n && nums[right] > nums[maxIndex]) {
105109
maxIndex = right;
110+
}
106111
if (maxIndex != root) {
107112
swap(nums, maxIndex, root);
108113
maxHeapify(nums, maxIndex);
@@ -143,10 +148,12 @@ public int[] heapSort(int[] nums) {
143148
private void minHeapify(int[] nums, int root) {
144149
int minIndex = root;
145150
int left = root * 2 + 1, right = root * 2 + 2;
146-
if (left < n && nums[left] < nums[minIndex])
151+
if (left < n && nums[left] < nums[minIndex]) {
147152
minIndex = left;
148-
if (right < n && nums[right] < nums[minIndex])
153+
}
154+
if (right < n && nums[right] < nums[minIndex]) {
149155
minIndex = right;
156+
}
150157
if (minIndex != root) {
151158
swap(nums, minIndex, root);
152159
minHeapify(nums, minIndex);

‎十大排序算法_Java/Insert.java

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
11
package sort;
22

3-
// 插入排序
3+
/*
4+
插入排序：
5+
1、第一个for循环从左到右遍历要排序的元素，第二个for循环从右到左将要排序的元素进行交换排序
6+
2、i从1开始，j从i开始，条件j>0保证j-1不会越界
7+
2、元素比较结果不用交换时，左边元素已经排序，可结束本轮排序
8+
*/
49
public class Insert {
510
public int[] insertSort(int[] nums) {
611
for (int i = 1; i < nums.length; i++) {
@@ -10,7 +15,6 @@ public int[] insertSort(int[] nums) {
1015
nums[j] = nums[j - 1];
1116
nums[j - 1] = temp;
1217
} else {
13-
// 左边元素已经排序，本次比较若没有交换则可结束本轮排序
1418
break;
1519
}
1620
}
@@ -22,7 +26,8 @@ public static void main(String[] args) {
2226
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
2327
Insert insert = new Insert();
2428
nums = insert.insertSort(nums);
25-
for (int num : nums)
29+
for (int num : nums) {
2630
System.out.println(num);
31+
}
2732
}
2833
}

‎十大排序算法_Java/Merge.java

Lines changed: 21 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,31 +2,41 @@
22

33
import java.util.Arrays;
44

5-
// 归并排序
5+
/*
6+
归并排序：递归
7+
1、方法功能：入参是一个数组，返回排序后的数组
8+
2、终止条件：数组长度小于2时，返回该数组
9+
3、一个元素处理过程和返回结果：直接返回该数组
10+
4、递归调用：左半部分和右半部分数组同样需要排序，因此调用同样的方法
11+
5、递归顺序：当前数组排序 需要依赖 左半部分和右半部分数组，因此要先递归排序左半部分和右半部分数组
12+
6、使用递归调用结果和返回结果：将两个有序数组合并，返回最终的排序数组
13+
*/
614
public class Merge {
715
public int[] mergeSort(int[] nums) {
816
int n = nums.length;
9-
if (n < 2)
17+
if (n < 2) {
1018
return nums;
19+
}
1120
int mid = n / 2;
1221
// 递归拆分数组
1322
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
1423
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, n));
1524
return combine(left, right);
1625
}
1726

18-
// 将两个数组排序合并为一个数组
27+
// 将两个有序数组合并为一个排序数组
1928
private int[] combine(int[] left, int[] right) {
2029
int[] res = new int[left.length + right.length];
2130
for (int i = 0, l = 0, r = 0; i < res.length; i++) {
22-
if (l >= left.length)
23-
res[i] = right[r++];
24-
else if (r >= right.length)
25-
res[i] = left[l++];
26-
else if (left[l] > right[r])
31+
if (l >= left.length) {
2732
res[i] = right[r++];
28-
else
33+
} else if (r >= right.length) {
2934
res[i] = left[l++];
35+
} else if (left[l] < right[r]) {
36+
res[i] = left[r++];
37+
} else {
38+
res[i] = right[l++];
39+
}
3040
}
3141
return res;
3242
}
@@ -35,7 +45,8 @@ public static void main(String[] args) {
3545
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
3646
Merge merge = new Merge();
3747
nums = merge.mergeSort(nums);
38-
for (int num : nums)
48+
for (int num : nums) {
3949
System.out.println(num);
50+
}
4051
}
4152
}

‎十大排序算法_Java/Quick.java

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,8 @@ public static void main(String[] args) {
7575
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
7676
Quick quick = new Quick();
7777
nums = quick.quickSort(nums);
78-
for (int num : nums)
78+
for (int num : nums) {
7979
System.out.println(num);
80+
}
8081
}
8182
}

‎十大排序算法_Java/Radix.java

Lines changed: 23 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -3,29 +3,31 @@
33
import java.util.ArrayList;
44
import java.util.Arrays;
55

6-
// 基数排序
6+
/*
7+
基数排序：
8+
1、创建0-9共10个桶
9+
2、获取最大数字的长度作为排序次数
10+
3、遍历数字，每个数字从低位到高位，获取数字的基数，由基数获取对应的桶，并将数字放入对应的桶中
11+
4、遍历10个桶，有序地将每个桶的数字放回原数组，然后清空桶，准备下一轮排序
12+
5、在低位有序的前提下，对高位排序，最终得到整体排序数组
13+
*/
714
public class Radix {
815
public int[] radixSort(int[] nums) {
9-
// 创建0-9共10个桶
10-
ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
11-
for (int i = 0; i < 10; i++)
12-
bucket.add(new ArrayList<>());
13-
// 获取最大数字的长度作为排序次数
16+
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
17+
for (int i = 0; i < 10; i++) {
18+
buckets.add(new ArrayList<>());
19+
}
1420
int times = String.valueOf(Arrays.stream(nums).max().getAsInt()).length();
1521
for (int i = 0; i < times; i++) {
16-
// 从低位到高位，获取数字的基数，并将数字放入对应的桶中
17-
for (int num : nums)
18-
bucket.get(num / (int) Math.pow(10, i) % 10).add(num);
19-
// 有序地将每个桶的数字放回原数组
20-
int k = 0;
21-
// 遍历10个桶
22-
for (int m = 0; m < 10; m++) {
23-
ArrayList list = bucket.get(m);
24-
// 遍历桶中所有数字
25-
for (int n = 0; n < list.size(); n++)
26-
nums[k++] = (int) list.get(n);
27-
// 清空桶
28-
list.clear();
22+
for (int num : nums) {
23+
buckets.get(num / (int) Math.pow(10, i) % 10).add(num);
24+
}
25+
int index = 0;
26+
for (ArrayList<Integer> bucket : buckets) {
27+
for (Integer num : bucket) {
28+
nums[index++] = num;
29+
}
30+
bucket.clear();
2931
}
3032
}
3133
return nums;
@@ -35,7 +37,8 @@ public static void main(String[] args) {
3537
int[] nums = {10, 244, 6, 212, 38, 528, 7777, 555, 9};
3638
Radix radix = new Radix();
3739
nums = radix.radixSort(nums);
38-
for (int num : nums)
40+
for (int num : nums) {
3941
System.out.println(num);
42+
}
4043
}
4144
}

0 commit comments

Comments
 (0)