堆排序原理及JAVA实现

选择类排序

• 基本思想&＃xff1a;在第i趟的记录序列中选取关键字第i小的记录作为有序序列的第i个记录。
• 关键&＃xff1a;如何从剩余的待排序列中找出最大或最小的那个记录。

堆排序是利用堆的性质对记录序列进行排序的一种排序方法。堆排序是选择类排序。

堆是满足下列性质的数列{K0&＃xff0c;K1&＃xff0c;K2&＃xff0c;……&＃xff0c;K&＃xff08;n-1&＃xff09;}&＃xff1a;

• (1)小根堆&＃xff1a;Ki <&＃61; K(2i&＃43;1)&＃xff0c;且Ki <&＃61; K(2i&＃43;2)&＃xff08;0<&＃61;i<&＃61;n/2-1&＃xff09;&＃xff1b;
• 或者(2)大根堆&＃xff1a;Ki >&＃61; K(2i&＃43;1)&＃xff0c;且Ki >&＃61; K(2i&＃43;2)&＃xff08;0<&＃61;i<&＃61;n/2-1&＃xff09;&＃xff1b;

其中&＃xff0c;Ki相当于二叉树的非叶子节点&＃xff0c;K(2i&＃43;1)是左孩子节点&＃xff0c;K(2i&＃43;2)是右孩子节点。

若将此数列看成是一颗完全二叉树&＃xff0c;则堆是空数列或是满足下列特性的完全二叉树&＃xff1a;

1. 其左、右子树分别是堆&＃xff1b;
2. 当左、右子树不空时&＃xff0c;根结点的值小于&＃xff08;或大于&＃xff09;左、右子树根结点的值。

基本思想&＃xff1a;

1. 建堆&＃xff1a;先将待排序序列文件R[0……n-1]构建成一个大根堆&＃xff0c;此堆为初始的无序区&＃xff1b;
2. 交换&＃xff1a;将堆顶记录&＃xff08;无序区的最大记录R[0]&＃xff09;和无序区的最后一个记录R[n-1]交换&＃xff0c;无序区记录个数减去1&＃xff0c;有序区记录个数加1&＃xff0c;由此得到新的无序区R[0……n-2]和有序区R[n-1]&＃xff1b;
3. 调整&＃xff1a;将当前无序区R[0……n-2]调整为大根堆&＃xff1b;
4. 重复交换操作&＃xff1a;将堆顶记录和无序区最后一个记录交换&＃xff0c;无序区记录个数减去1&＃xff0c;有序区记录个数加1&＃xff1b;
5. 重复调整操作&＃xff1a;将当前无序区调整为大根堆&＃xff1b;
6. ……
7. 直到无序区只有一个元素为止。

假设待排序序列为{7&＃xff0c; 3&＃xff0c; 5&＃xff0c; 1&＃xff0c; 6}&＃xff0c;要将其按升序排序&＃xff0c;其堆排序具体过程如下&＃xff1a;

步骤一&＃xff1a;建初始堆。&＃xff08;升序使用大根堆&＃xff0c;降序使用小根堆&＃xff09;

初始的无序序列逻辑及物理存储结构如下&＃xff1a;

从最后一个非叶子结点开始&＃xff0c;其下标为i &＃61; arr.length/2-1 &＃61; 1&＃xff0c;即从arr[1]处开始&＃xff0c;看其左、右孩子结点的值&＃xff0c;找出左、右孩子结点中值最大的结点&＃xff0c;记住其下标&＃xff0c;然后与其父结点交换&＃xff1b;然后&＃xff0c;从左往右&＃xff0c;从下向上&＃xff0c;依次进行调整。直到将其调整成大根堆。

步骤二&＃xff1a;交换。将堆顶记录和无序区最后一个记录交换。

圈出来的部分就是新的无序区&＃xff0c;即需要下次调整为大根堆的部分。此时下标为4的arr[4]就是有序区。

步骤三&＃xff1a;调整。将新的无序区调整为大根堆。

从最后一个非叶子结点&＃xff08;新的无序区的最后一个非叶子结点&＃xff09;开始&＃xff0c;其下标为i &＃61; &＃xff08;arr.length-1&＃xff09;/2-1 &＃61; 1&＃xff0c;即从arr[1]处开始&＃xff0c;看其左、右孩子结点的值&＃xff0c;找出左、右孩子结点中值最大的结点&＃xff0c;记住其下标&＃xff0c;然后与其父结点交换&＃xff1b;然后&＃xff0c;从左往右&＃xff0c;从下向上&＃xff0c;依次进行调整。直到将其调整成大根堆。

步骤四&＃xff1a;然后重复交换、调整、交换、调整……操作&＃xff0c;直到无序区只有一个记录。

圈出来的是新的无序区&＃xff0c;是下一次需要调整的新的无序区。

最终的堆排序结果为下图:

此时&＃xff0c;堆排序结束。

public class HeapSort {/*** 调整一个非叶子结点及它的左、右孩子这三个结点为一个大根堆* &＃64;param arr* &＃64;param i* &＃64;param length*/private static void adjust(int[] arr, int i, int length) {//先保存第一个非叶子结点记录int temp &＃61; arr[i];//从左孩子结点开始for(int j &＃61; 2*i&＃43;1; j &＃61; 0; i--) {adjust(arr, i, arr.length);}/*** 交换 &＃43; 调整*/for(int i &＃61; arr.length-1; i >&＃61; 0; i--) {//先交换堆顶记录和无序区最后一个记录swap(arr, 0, i);//调整无序区为大根堆adjust(arr, 0, i);}}private static void showArr(int[] arr) {for(int i &＃61; 0; i

运行结果&＃xff1a;