Skip to content

Commit 66a28af

Browse files
linwtlinwt
authored
Add files via upload
1 parent 674c93d commit 66a28af

File tree

10 files changed

+368
-0
lines changed

10 files changed

+368
-0
lines changed

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

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package sort;
2+
3+
// 冒泡排序
4+
public class Bubble {
5+
public int[] bubbleSort(int[] nums) {
6+
int n = nums.length;
7+
// 外循环次数
8+
for (int i = 0; i < n - 1; i++) {
9+
// 标记一次排序过程是否发生元素位置交换
10+
boolean flag = true;
11+
// 内循环次数
12+
for (int j = 0; j < n - i - 1; j++) {
13+
if (nums[j] > nums[j + 1]) {
14+
int temp = nums[j];
15+
nums[j] = nums[j + 1];
16+
nums[j + 1] = temp;
17+
flag = false;
18+
}
19+
}
20+
if (flag) break;
21+
}
22+
return nums;
23+
}
24+
25+
public static void main(String[] args) {
26+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
27+
Bubble bubble = new Bubble();
28+
nums = bubble.bubbleSort(nums);
29+
for (int num : nums)
30+
System.out.println(num);
31+
}
32+
}

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

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package sort;
2+
3+
import java.util.Arrays;
4+
5+
// 桶排序
6+
public class Bucket {
7+
public int[] bucketSort(int[] nums) {
8+
// 获取数组最大值、最小值
9+
int max = Arrays.stream(nums).max().getAsInt();
10+
int min = Arrays.stream(nums).min().getAsInt();
11+
12+
// 以数值范围定义数组大小
13+
int[] stats = new int[max - min + 1];
14+
Arrays.fill(stats, 0);
15+
// 以数值个数定义的数组大小
16+
int[] res = new int[nums.length];
17+
Arrays.fill(res, 0);
18+
19+
// 统计每个数的出现次数
20+
for(int num : nums)
21+
stats[num - min]++;
22+
// 遍历每个桶，按序获取数字放到结果数组
23+
int k = 0;
24+
for (int i = 0; i < stats.length; i++)
25+
for (int j = 0; j < stats[i]; j++)
26+
res[k++] = min + i;
27+
return res;
28+
}
29+
30+
public static void main(String[] args) {
31+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
32+
Bucket bucket = new Bucket();
33+
nums = bucket.bucketSort(nums);
34+
for (int num : nums)
35+
System.out.println(num);
36+
}
37+
}

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

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package sort;
2+
3+
import java.util.Arrays;
4+
5+
// 计数排序
6+
public class Count {
7+
public int[] countSort(int[] nums) {
8+
int max = Arrays.stream(nums).max().getAsInt();
9+
int min = Arrays.stream(nums).min().getAsInt();
10+
11+
int[] stats = new int[max - min + 1];
12+
Arrays.fill(stats, 0);
13+
int[] res = new int[nums.length];
14+
Arrays.fill(res, 0);
15+
16+
for (int num : nums)
17+
stats[num - min]++;
18+
// 记录每个数字存放的索引位置
19+
for (int i = 1; i < nums.length; i++)
20+
stats[i] += stats[i - 1];
21+
// 获取每个数字的最终索引并存入结果数组
22+
for (int num : nums) {
23+
res[stats[num - min] - 1] = num;
24+
stats[num - min]--;
25+
}
26+
return res;
27+
28+
}
29+
30+
public static void main(String[] args) {
31+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
32+
Count count = new Count();
33+
nums = count.countSort(nums);
34+
for (int num : nums)
35+
System.out.println(num);
36+
}
37+
}

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

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package sort;
2+
3+
// 堆排序
4+
public class Heap {
5+
private int n;
6+
7+
public int[] heapSort(int[] nums) {
8+
n = nums.length;
9+
// 堆的构造需要跟子节点比较，所以从最后一个非叶子结点开始向上构造最大堆
10+
for (int i = (n - 1) / 2; i >= 0; i--)
11+
max_heapify(nums, i);
12+
while (n > 0) {
13+
// 根节点与最后一个节点交换
14+
swap(nums, 0, n - 1);
15+
n--;
16+
// 交换完调整最大堆，父子两两交换，把小值往下换，把最大值升到根节点
17+
max_heapify(nums, 0);
18+
}
19+
return nums;
20+
}
21+
22+
// 堆调整的逻辑：父节点与子节点较大者交换，最终最大值会升到根节点
23+
private void max_heapify(int[] nums, int root) {
24+
int maxIndex = root;
25+
int left = root * 2, right = root * 2 + 1;
26+
// 如果有左孩子，且左孩子大于父节点，则将最大指针指向左孩子
27+
if (left < n && nums[left] > nums[maxIndex])
28+
maxIndex = left;
29+
// 如果有右孩子，且右孩子大于父节点和左孩子，则将最大指针指向右孩子
30+
if (right < n && nums[right] > nums[maxIndex] && nums[right] > nums[left])
31+
maxIndex = right;
32+
// 如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
33+
if (maxIndex != root) {
34+
swap(nums, maxIndex, root);
35+
max_heapify(nums, maxIndex);
36+
}
37+
}
38+
39+
private void swap(int[] nums, int x, int y) {
40+
int temp = nums[x];
41+
nums[x] = nums[y];
42+
nums[y] = temp;
43+
}
44+
45+
public static void main(String[] args) {
46+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
47+
Heap heap = new Heap();
48+
nums = heap.heapSort(nums);
49+
for (int num : nums)
50+
System.out.println(num);
51+
}
52+
}

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

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package sort;
2+
3+
// 插入排序
4+
public class Insert {
5+
public int[] insertSort(int[] nums) {
6+
for (int i = 1; i < nums.length; i++) {
7+
for (int j = i; j > 0; j--) {
8+
if (nums[j] < nums[j - 1]) {
9+
int temp = nums[j];
10+
nums[j] = nums[j - 1];
11+
nums[j - 1] = temp;
12+
}
13+
}
14+
}
15+
return nums;
16+
}
17+
18+
public static void main(String[] args) {
19+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
20+
Insert insert = new Insert();
21+
nums = insert.insertSort(nums);
22+
for (int num : nums)
23+
System.out.println(num);
24+
}
25+
}

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

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package sort;
2+
3+
import java.util.Arrays;
4+
5+
// 归并排序
6+
public class Merge {
7+
public int[] mergeSort(int[] nums) {
8+
int n = nums.length;
9+
if (n < 2)
10+
return nums;
11+
int mid = n / 2;
12+
// 递归拆分数组
13+
int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
14+
int[] right = mergeSort(Arrays.copyOfRange(nums, mid, n));
15+
return combine(left, right);
16+
}
17+
18+
// 将两个数组排序合并为一个数组
19+
private int[] combine(int[] left, int[] right) {
20+
int[] res = new int[left.length + right.length];
21+
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])
27+
res[i] = right[r++];
28+
else
29+
res[i] = left[l++];
30+
}
31+
return res;
32+
}
33+
34+
public static void main(String[] args) {
35+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
36+
Merge merge = new Merge();
37+
nums = merge.mergeSort(nums);
38+
for (int num : nums)
39+
System.out.println(num);
40+
}
41+
}

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

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package sort;
2+
3+
// 快速排序
4+
public class Quick {
5+
public int[] quickSort(int[] nums) {
6+
return mainSort(nums, 0, nums.length - 1);
7+
}
8+
9+
private int[] mainSort(int[] nums, int left, int right) {
10+
if (left < right) {
11+
int mid = partition(nums, left, right);
12+
// 递归排序左右两部分
13+
mainSort(nums, left, mid - 1);
14+
mainSort(nums, mid + 1, right);
15+
}
16+
return nums;
17+
}
18+
19+
// 一次排序操作
20+
private int partition(int[] nums, int left, int right) {
21+
int index = left + 1;
22+
for (int i = index; i <= right; i++) {
23+
if (nums[i] < nums[left]) {
24+
swap(nums, i, index);
25+
index++;
26+
}
27+
}
28+
swap(nums, left, index - 1);
29+
return index - 1;
30+
}
31+
32+
private void swap(int[] nums, int x, int y) {
33+
int temp = nums[x];
34+
nums[x] = nums[y];
35+
nums[y] = temp;
36+
}
37+
38+
public static void main(String[] args) {
39+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
40+
Quick quick = new Quick();
41+
nums = quick.quickSort(nums);
42+
for (int num : nums)
43+
System.out.println(num);
44+
}
45+
}

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

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package sort;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
6+
// 基数排序
7+
public class Radix {
8+
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+
// 获取最大数字的长度作为排序次数
14+
int times = String.valueOf(Arrays.stream(nums).max().getAsInt()).length();
15+
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();
29+
}
30+
}
31+
return nums;
32+
}
33+
34+
public static void main(String[] args) {
35+
int[] nums = {10, 244, 6, 212, 38, 528, 7777, 555, 9};
36+
Radix radix = new Radix();
37+
nums = radix.radixSort(nums);
38+
for (int num : nums)
39+
System.out.println(num);
40+
}
41+
}

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

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package sort;
2+
3+
// 选择排序
4+
public class Select {
5+
public int[] selectSort(int[] nums) {
6+
int n = nums.length;
7+
for (int i = 0; i < n - 1; i++) {
8+
int min_index = i;
9+
for (int j = i + 1; j < n; j++) {
10+
if (nums[j] < nums[min_index])
11+
min_index = j;
12+
}
13+
int temp = nums[i];
14+
nums[i] = nums[min_index];
15+
nums[min_index] = temp;
16+
}
17+
return nums;
18+
}
19+
20+
public static void main(String[] args) {
21+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
22+
Select select = new Select();
23+
nums = select.selectSort(nums);
24+
for (int num : nums)
25+
System.out.println(num);
26+
}
27+
}

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

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package sort;
2+
3+
// 希尔排序
4+
public class Shell {
5+
public int[] shellSort(int[] nums) {
6+
int n = nums.length;
7+
int gap = n / 2;
8+
// 分组插入排序
9+
while (gap > 0) {
10+
for (int i = gap; i < n; i++) {
11+
for (int j = i - gap; j >= 0; j -= gap) {
12+
if (nums[j] > nums[j + gap]) {
13+
int temp = nums[j];
14+
nums[j] = nums[j + gap];
15+
nums[j + gap] = temp;
16+
}
17+
}
18+
}
19+
gap /= 2;
20+
}
21+
return nums;
22+
}
23+
24+
public static void main(String[] args) {
25+
int[] nums = {1, 4, 6, 2, 3, 8, 7, 5, 9};
26+
Shell shell = new Shell();
27+
nums = shell.shellSort(nums);
28+
for (int num : nums)
29+
System.out.println(num);
30+
}
31+
}

0 commit comments

Comments
 (0)