堆排序

今天看到一篇面经,算法题是手写堆排序,《算法》放在书架已经有一段时间了,想试试能不能写出来,然而并没有,所以记录一下

自顶到底构造堆

这是一道 lintcode上面的题目堆化

构造一个堆只需要从左到右遍历数组,每次只要保证所遍历到的位子能满足堆的条件

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
public class Solution {
/*
* @param A: Given an integer array
* @return: nothing
*/
public void heapify(int[] A) {

for (int i = 0; i < A.length; i++) {
swim(A, i);
}
}
// 上浮
private void swim(int[] A, int i) {
while(i > 0 && A[i] < A[(i-1) / 2]) {
swap(A, i, (i-1) / 2);
i = (i-1) / 2;
}
}

private void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}

自底到顶构造堆

而堆排序采用的是自底到顶构造堆,每次把第一个元素和最后一个元素交换,交换之后把第一个元素下沉,同时堆数组减一,下面是代码

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
public class Heap {

private static void heapSort(int[] array) {
int len = array.length - 1;
for (int i = (len - 1) / 2; i >= 0; i--) {
sink(array, i, len);
}
printArr(array);
while (len >= 0) {
swap(array, 0, len);
sink(array, 0, --len);
}
}

private static void sink(int[] array, int i, int len) {
while (i * 2 + 1 <= len) {
int j = i * 2 + 1;
if (j + 1 <= len && array[j+1] > array[j]) j++;
if (array[i] > array[j]) break;
swap(array, i, j);
i = j;
}
}

private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

public static void main(String[] args) {
int[] array = {2, 3, 1, 6, 4, 5, 2, 1};
heapSort(array);
printArr(array);
}

private static void printArr(int[] array) {
Arrays.stream(array).forEach(a -> System.out.print(a + " "));
System.out.println();
}
}
-------------本文结束感谢您的阅读-------------

本文标题:堆排序

文章作者:cuzz

发布时间:2018年11月23日 - 22:11

最后更新:2019年07月16日 - 19:07

原始链接:http://blog.cuzz.site/2018/11/23/堆排序/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请博主吃包辣条
0%