Skip to content

Commit 7bc7130

Browse files
byhiegbyhieg
committed
添加堆排序
1 parent 5af7b23 commit 7bc7130

File tree

2 files changed

+111
-29
lines changed

2 files changed

+111
-29
lines changed

‎src/main/java/cn/byhieg/algorithmtutorial/Sort.java‎

Lines changed: 95 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@ public class Sort {
1010
* 选择排序，每一轮排序，选择数组中数字最小的那一个放到指定的位置上。
1111
* 时间复杂度o(n^2),无论数组顺序如何都要选择一个最小的值，因为数组的是否有序，不影响时间复杂度
1212
* 空间复杂度o(1)
13+
*
1314
* @param nums
1415
*/
1516
public void chooseSort(int[] nums) {
@@ -32,43 +33,45 @@ public void chooseSort(int[] nums) {
3233
* 直接插入排序，每一轮排序，都是在i坐标之前，包括i坐标的序列是有序的，但是并不是最终的排序位置。
3334
* 时间复杂度o（n^2),对于第二重循环，只会在非有序的环境下才会执行每个元素后移，因此针对有序的数组，时间复杂度最好的情况是o(N)。
3435
* 空间复杂度o(1)
36+
*
3537
* @param nums
3638
*/
3739
public void insertDirectlySort(int[] nums) {
3840
int length = nums.length;
3941
for (int i = 1; i < length; i++) {
40-
for (int j = i ; j > 0; j --) {
41-
if (nums[j] < nums[j - 1]) {
42-
int tmp = nums[j - 1];
43-
nums[j - 1] = nums[j];
44-
nums[j] = tmp;
45-
}
46-
}
42+
for (int j = i; j > 0; j--) {
43+
if (nums[j] < nums[j - 1]) {
44+
int tmp = nums[j - 1];
45+
nums[j - 1] = nums[j];
46+
nums[j] = tmp;
47+
}
48+
}
4749
}
4850
}
4951

5052
/**
5153
* 折半插入排序，针对直接排序而言，每一个要插入的元素都是插入在有序的数组中，因此，只需要查找到插入的位置即可，查找的方式利用二分查找
5254
* 时间复杂度和直接插入是一样的，只是快在了查找的过程中，还是o(N^2),最好的环境下是o（N）
5355
* 空间复杂度还是o(1)
56+
*
5457
* @param nums
5558
*/
5659
public void insertBinarySort(int[] nums) {
5760
int length = nums.length;
58-
for (int i = 1; i < length;i++) {
61+
for (int i = 1; i < length; i++) {
5962
int tmp = nums[i];
6063
int low = 0;
6164
int high = i - 1;
6265
while (low <= high) {
6366
int mid = (low + high) / 2;
6467
if (tmp < nums[mid]) {
6568
high = mid - 1;
66-
}else{
69+
} else {
6770
low = mid + 1;
6871
}
6972
}
7073

71-
for (int j = i; j >= low + 1;j--) {
74+
for (int j = i; j >= low + 1; j--) {
7275
nums[j] = nums[j - 1];
7376
}
7477
nums[low] = tmp;
@@ -80,16 +83,17 @@ public void insertBinarySort(int[] nums) {
8083
* 这种实现是按照算法定义的，但是效率是最低的
8184
* 时间复杂度o(n^2)
8285
* 空间复杂度o(1)
86+
*
8387
* @param nums
8488
*/
8589
public void bubbleSort1(int[] nums) {
8690
int length = nums.length;
87-
for (int i = 1 ; i < length;i++) {
88-
for (int j = 0 ; j < length - i;j++) {
91+
for (int i = 1; i < length; i++) {
92+
for (int j = 0; j < length - i; j++) {
8993
if (nums[j] > nums[j + 1]) {
9094
int tmp = nums[j];
9195
nums[j] = nums[j + 1];
92-
nums[j+1] = tmp;
96+
nums[j + 1] = tmp;
9397
}
9498
}
9599
}
@@ -98,27 +102,30 @@ public void bubbleSort1(int[] nums) {
98102
/**
99103
* 冒泡排序，高效率实现，因为只需要用一个flag变量来记录本次的排序，是否修改
100104
* 如果没有修改，说明已经有序
105+
*
101106
* @param nums
102107
*/
103108
public void bubbleSort2(int[] nums) {
104109
int length = nums.length;
105110
boolean flag = true;
106111
while (flag) {
107112
flag = false;
108-
for (int j = 0 ; j < length - 1;j++) {
113+
for (int j = 0; j < length - 1; j++) {
109114
if (nums[j] > nums[j + 1]) {
110115
int tmp = nums[j];
111116
nums[j] = nums[j + 1];
112117
nums[j + 1] = tmp;
113118
flag = true;
114119
}
115120
}
116-
length -- ;
121+
length--;
117122
}
118123
}
119124

120125
/**
121126
* 快速排序，选定一个切分元素，每一轮排序后，都保证切分元素之前的元素都小于切分元素，切分元素之后的元素都大于切分元素
127+
* 时间复杂度o(NlgN)
128+
* 空间复杂度o(lgN)
122129
*
123130
* @param nums
124131
*/
@@ -130,6 +137,7 @@ public void quickSort(int[] nums) {
130137

131138
/**
132139
* 快速排序的递归实现
140+
*
133141
* @param nums
134142
* @param low
135143
* @param high
@@ -143,6 +151,7 @@ public void sort(int[] nums, int low, int high) {
143151

144152
/**
145153
* 快速排序的辅助方法，来对排序的数组，进行切分,
154+
*
146155
* @param nums
147156
* @param low
148157
* @param high
@@ -154,7 +163,7 @@ public int partition(int[] nums, int low, int high) {
154163
int x = nums[i];
155164
while (i < j) {
156165
//从右向左找到nums[j]小于x的元素
157-
while (i < j && nums[j] > x) j-- ;
166+
while (i < j && nums[j] > x) j--;
158167
if (i < j) {
159168
nums[i] = nums[j];
160169
i++;
@@ -171,6 +180,75 @@ public int partition(int[] nums, int low, int high) {
171180
return i;
172181
}
173182

174-
183+
184+
/**
185+
* 堆排序，建立一个小顶堆，小顶堆满足父节点比两个子节点的值要小
186+
* 堆的性质满足:1. 只能在堆顶删除元素
187+
* 2. 只能在堆的最后一位存元素。
188+
* 3. 堆的存储利用数组，满足i节点是父节点，则子节点是2 * i+ 1,2 * i + 2
189+
* 4. 堆的两种建方法，第一种是从上到下，@see sink（）,第二种是从下到上 @see swim
190+
* 5. 堆排序是指在弄好的堆中，输出第一个元素，然后将最后一个元素与第一个元素互换，换后调用sink，找到自己的位置后，在重复这个步骤，就输出一个有序的堆
191+
* 6. 如果要生序就需要大顶堆，要降序就需要小顶堆。
192+
* 时间复杂度：o(NlgN)
193+
* 空间复杂度: o(1)
194+
* 这是小顶堆的排序，所以nums数组最后是降序的
195+
* @param nums
196+
*/
197+
public void heapSort(int[] nums) {
198+
int length = nums.length;
199+
for (int i = 0; i < length; i++) {
200+
swim(nums, i);
201+
}
202+
while (length > 0) {
203+
int temp = nums[0];
204+
nums[0] = nums[length - 1];
205+
nums[length - 1] = temp;
206+
length--;
207+
sink(nums, 0, length);
208+
}
209+
}
210+
211+
/**
212+
* 将i放入对堆中,i的父节点是（i - 1）/ 2,父节点的值是小于他的两个子节点的
213+
* i节点放入后，要向上移动，如果父节点比i节点的值大，则i节点要继续上移。
214+
*
215+
* @param nums
216+
* @param i
217+
*/
218+
private void swim(int nums[], int i) {
219+
while (i > 0) {
220+
int father = (i - 1) / 2;
221+
if (nums[father] > nums[i]) {
222+
int temp = nums[father];
223+
nums[father] = nums[i];
224+
nums[i] = temp;
225+
}
226+
i = father;
227+
}
228+
}
229+
230+
231+
/**
232+
* 从i节点由上到下开始调整，i节点的子节点为2*i + 1, 2 * i + 2
233+
* i节点要向下移动，直到满足i节点小于两个子节点
234+
*
235+
* @param nums nums[] 数组
236+
* @param i i节点
237+
*/
238+
public void sink(int nums[], int i,int n) {
239+
int son = 2 * i + 1;
240+
while (son <= n - 1) {
241+
if (son < n - 1 && nums[son] > nums[son + 1]) son++;
242+
if (nums[i] > nums[son]) {
243+
int temp = nums[i];
244+
nums[i] = nums[son];
245+
nums[son] = temp;
246+
i = son;
247+
} else {
248+
break;
249+
}
250+
}
251+
}
252+
175253

176254
}

‎src/test/java/cn/byhieg/algorithmtutorialtest/SortTest.java‎

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -20,25 +20,29 @@ public void tearDown() throws Exception {
2020
}
2121
}
2222

23-
// public void testChooseSort() throws Exception {
24-
// new Sort().chooseSort(nums);
25-
// }
23+
public void testChooseSort() throws Exception {
24+
new Sort().chooseSort(nums);
25+
}
2626

2727

28-
// public void testInsertDirectlySort() throws Exception {
29-
// new Sort().insertDirectlySort(nums);
30-
// }
28+
public void testInsertDirectlySort() throws Exception {
29+
new Sort().insertDirectlySort(nums);
30+
}
3131

32-
// public void testInsertBinarySort() throws Exception {
33-
// new Sort().insertBinarySort(nums);
34-
// }
32+
public void testInsertBinarySort() throws Exception {
33+
new Sort().insertBinarySort(nums);
34+
}
3535

36-
// public void testBubbleSort() throws Exception {
37-
// new Sort().bubbleSort2(nums);
38-
// }
36+
public void testBubbleSort() throws Exception {
37+
new Sort().bubbleSort2(nums);
38+
}
3939

4040
public void testQuickSort() throws Exception {
4141
new Sort().quickSort(nums);
4242
}
4343

44+
public void testHeapSort() throws Exception {
45+
new Sort().heapSort(nums);
46+
}
47+
4448
}

0 commit comments

Comments
 (0)