堆排序是借助堆来实现的选择排序，思想同简单的选择排序，以下以大顶堆为例。注意：如果想升序排
序就使用大顶堆，反之使用小顶堆。原因是堆顶元素需要交换到序列尾部。
首先，实现堆排序需要解决两个问题：
如何由一个无序序列键成一个堆？
如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
第一个问题，可以直接使用线性数组来表示一个堆，由初始的无序序列建成一个堆就需要自底向上从第
一个非叶元素开始挨个调整成一个堆。
第二个问题，怎么调整成堆？首先是将堆顶元素和最后一个元素交换。然后比较当前堆顶元素的左右孩
子节点，因为除了当前的堆顶元素，左右孩子堆均满足条件，这时需要选择当前堆顶元素与左右孩子节
点的较大者（大顶堆）交换，直至叶子节点。我们称这个自堆顶自叶子的调整成为筛选。
从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树，则最后一个
非终端节点是
n/2
取底个元素，由此筛选即可。举个栗子：
left ++;
arr[right] = arr[left]; //
把大的移动到右边
}
arr[left] = pivotKey; //
最后把
pivot
赋值到中间
return left;
}
public static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}
public static void sort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
quickSort(arr, 0, arr.length-1);
}
}
49,38,65,97,76,13,27,49
序列的堆排序建初始堆和调整的过程如下
实现代码：
public class
HeapSort
{
public static
void
heapAdjust
(
int
[]
arr
,
int
start
,
int
end
) {
int
temp
=
arr
[
start
];
for
(
int
i
=
2
*
start
+
1
;
i
<=
end
;
i
*=
2
) {
//
左右孩子的节点分别为
2*i+1,2*i+2
//
选择出左右孩子较小的下标
if
(
i
<
end
&&
arr
[
i
]
<
arr
[
i
+
1
]) {
i
++
;
}
if
(
temp
>=
arr
[
i
]) {
break
;
//
已经为大顶堆，
=
保持稳定性。
}
arr
[
start
]
=
arr
[
i
];
//
将子节点上移
start
=
i
;
//
下一轮筛选
}
arr
[
start
]
=
temp
;
//
插入正确的位置
}
public static
void
heapSort
(
int
[]
arr
) {
if
(
arr
==
null
||
arr
.
length
==
0
)
return
;
//
建立大顶堆
for
(
int
i
=
arr
.
length
/
2
;
i
>=
0
;
i
--
) {
heapAdjust
(
arr
,
i
,
arr
.
length
-
1
);
}
for
(
int
i
=
arr
.
length
-
1
;
i
>=
0
;
i
--
) {
swap
(
arr
,
0
,
i
);
heapAdjust
(
arr
,
0
,
i
-
1
);
}
}
public static
void
swap
(
int
[]
arr
,
int
i
,
int
j
) {
int
temp
=
arr
[
i
];
arr
[
i
]
=
arr
[
j
];
arr
[
j
]
=
temp
;
}
}
