Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit fc79da7

Browse filesBrowse files
committed
Create sort.md
1 parent 289fb9f commit fc79da7
Copy full SHA for fc79da7

File tree

Expand file treeCollapse file tree

1 file changed

+164
-0
lines changed
Filter options
Expand file treeCollapse file tree

1 file changed

+164
-0
lines changed

‎basic_algorithm/sort.md

Copy file name to clipboard
+164Lines changed: 164 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,164 @@
1+
# 排序
2+
3+
## 常考排序
4+
5+
### 快速排序
6+
7+
```java
8+
public void quickSort(int[] nums) {
9+
// 思路:把一个数组分为左右两段,左段小于右段
10+
quickSort(nums, 0, nums.length - 1);
11+
}
12+
13+
// 原地交换,所以传入交换索引
14+
private void quickSort(int[] nums, int start, int end) {
15+
if (start < end) {
16+
// 分治法:divide
17+
int pivot = partition(nums, start, end);
18+
quickSort(nums, 0, pivot - 1);
19+
quickSort(nums, pivot + 1, end);
20+
}
21+
}
22+
23+
// 分区
24+
private int partition(int[] nums, int start, int end) {
25+
// 选取最后一个元素作为基准pivot
26+
int p = nums[end];
27+
int i = start;
28+
// 最后一个值就是基准所以不用比较
29+
for (int j = start; j < end; j++) {
30+
if (nums[j] < p) {
31+
swap(nums, i, j);
32+
i++;
33+
}
34+
}
35+
// 把基准值换到中间
36+
swap(nums, i, end);
37+
return i;
38+
}
39+
40+
// 交换两个元素
41+
private void swap(int[] nums, int i, int j) {
42+
int temp = nums[i];
43+
nums[i] = nums[j];
44+
nums[j] = temp;
45+
}
46+
```
47+
48+
### 归并排序
49+
50+
```java
51+
public void mergeSort(int[] nums) {
52+
mergeSort(nums, 0, nums.length);
53+
}
54+
55+
private void mergeSort(int[] nums, int start, int end) {
56+
if (end - start <= 1) {
57+
return;
58+
}
59+
// 分治法:divide 分为两段
60+
int mid = start + (end - start) / 2;
61+
mergeSort(nums, start, mid);
62+
mergeSort(nums, mid, end);
63+
// 合并两段数据
64+
merge(nums, start, mid, end);
65+
}
66+
67+
private void merge(int[] nums, int start, int mid, int end) {
68+
int[] temp = new int[end - start];
69+
// 两边数组合并游标
70+
int l = start;
71+
int r = mid;
72+
int k = 0;
73+
// 注意不能越界
74+
while (l < mid && r < end) {
75+
// 谁小合并谁
76+
if (nums[l] < nums[r]) {
77+
temp[k++] = nums[l++];
78+
} else {
79+
temp[k++] = nums[r++];
80+
}
81+
}
82+
// 剩余部分合并
83+
while (l < mid) {
84+
temp[k++] = nums[l++];
85+
}
86+
while (r < end) {
87+
temp[k++] = nums[r++];
88+
}
89+
// 复制到原数组
90+
for (int i = 0; i < temp.length; i++) {
91+
nums[i + start] = temp[i];
92+
}
93+
}
94+
```
95+
96+
### 堆排序
97+
98+
用数组表示的完全二叉树 complete binary tree
99+
100+
> 完全二叉树 VS 其他二叉树
101+
102+
![image.png](https://img.fuiboom.com/img/tree_type.png)
103+
104+
[动画展示](https://www.bilibili.com/video/av18980178/)
105+
106+
![image.png](https://img.fuiboom.com/img/heap.png)
107+
108+
核心代码
109+
110+
```java
111+
public void heapSort(int[] nums) {
112+
// 1、无序数组nums
113+
// 2、将无序数组nums构建为一个大根堆
114+
for (int i = nums.length / 2 - 1; i >= 0; i--) {
115+
sink(nums, i, nums.length);
116+
}
117+
// 3、交换nums[0]和nums[len(a)-1]
118+
// 4、然后把前面这段数组继续下沉保持堆结构,如此循环即可
119+
for (int i = nums.length - 1; i >= 0; i--) {
120+
// 从后往前填充值
121+
swap(nums, 0, i);
122+
// 前面的长度也减一
123+
sink(nums, 0, i);
124+
}
125+
}
126+
127+
private void sink(int[] nums, int i, int length) {
128+
while (true) {
129+
// 左节点索引(从0开始,所以左节点为i*2+1)
130+
int l = i * 2 + 1;
131+
// 右节点索引
132+
int r = i * 2 + 2;
133+
// 保存根、左、右三者之间较大值的索引
134+
int index = i;
135+
// 存在左节点,左节点值较大,则取左节点
136+
if (l < length && nums[l] > nums[index]) {
137+
index = l;
138+
}
139+
// 存在右节点,且值较大,取右节点
140+
if (r < length && nums[r] > nums[index]) {
141+
index = r;
142+
}
143+
// 如果根节点较大,则不用下沉
144+
if (index == i) {
145+
break;
146+
}
147+
// 如果根节点较小,则交换值,并继续下沉
148+
swap(nums, i, index);
149+
i = index;
150+
}
151+
}
152+
153+
private void swap(int[] nums, int i, int j) {
154+
int temp = nums[i];
155+
nums[i] = nums[j];
156+
nums[j] = temp;
157+
}
158+
```
159+
160+
## 参考
161+
162+
[十大经典排序](https://www.cnblogs.com/onepixel/p/7674659.html)
163+
164+
[二叉堆](https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/er-cha-dui-xiang-jie-shi-xian-you-xian-ji-dui-lie)

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.