八大排序-堆排序（手写堆排序）[java版]

客官°小女子只卖身不卖艺 2023-07-24 15:59 27阅读 0赞

# 八大排序-堆排序（手写堆排序）  #

## 原理 ##

以最大堆为例，利用最大堆结构的特点：每个最大堆的根节点必然是数组中最大的元素，构建一次最大堆即可获取数组中最大的元素。剔除最大元素后，反复构建余下数字为最大堆获取根元素最终保证数组有序。

以上都是废话，建议直接看图

### 最大堆定义 ###

*  最大堆图示

![format_png][]

*  最大堆数组

![format_png 1][]

满足父节点大于或等于左右子节点即为最大堆，最大堆二叉树以及对应数组如上图。

## 堆排序流程 ##

### 1.一趟堆排序 ###

以数组int n\[\] = \{ 6, 5, 2, 7, 3, 9, 8 \}为例：

![format_png 2][]

### 步骤 ###

一、构建最大堆：

从最后一个非叶子节点（计算公式为n.length/2-1,可自行验证)开始，从后往前进行调整构建，调整的规则是：若子节点大于父节点，则将子节点中较大的节点元素与父节点交换。

1.调整节点2（数组索引2），对比子节点9和8，再对比较大子节点9和父节点2，将9和2进行交换；

![format_png 3][]

2.调整节点5（数组索引1），对比子节点7和3，将7和5进行交换；

![format_png 4][]

3.调整节点6（素组索引0），对比子节点7和9，将6和9进行交换；

![format_png 5][]

二、取出最大堆数组的第一位根元素与数组末位元素交换：

![format_png 6][]

### 2.循环构建最大堆 ###

根据上述构建最大堆的原理可以得出堆排序的完整过程

*  第1趟堆排序：

![format_png 7][]

*  第2趟堆排序：

![format_png 8][]

*  第3趟堆排序：

![format_png 9][]

*  第4趟堆排序：

![format_png 10][]

*  第5趟堆排序：

![format_png 11][]

*  第6趟堆排序：

![format_png 12][]

## 编码实践 ##

public class Test {
    
    	public static void main(String[] args) {
    		int n[] = { 6, 5, 2, 7, 3, 9, 8 };
    		heapsort(n);
    		System.out.print("堆排序结果：");
    		for (int m : n) {
    			System.out.print(m + " ");
    		}
    	}
    
    	/**
    	 * 堆排序
    	 * @param n 待排序数组
    	 */
    	public static void heapsort(int n[]) {
    		for (int i = n.length - 1; i >= 1; i--) {
    			buildHeap(n, i);
    			swap(n, 0, i);
    		}
    	}
    
    	/**
    	 * 
    	 * @param n   待排序数组
    	 * @param end 待排序数组末位下标
    	 */
    	public static void buildHeap(int n[], int end) {
    		int len = end + 1;
    		for (int i = len / 2 - 1; i >= 0; i--) {
    		//堆中i节点对应的左右子节点l和r
    			int l = 2 * i + 1, r = l + 1;
    		//指向较大数节点的指针
    			int p = l;
    			if (r <= len - 1 && n[l] < n[r]) {
    				p = r;
    			}
    			if (n[i] < n[p]) {
    				swap(n, i, p);
    			}
    		}
    	}
    
    	/**
    	 * 
    	 * @param n 待排序数组
    	 * @param i 待交换数字数组下标
    	 * @param j 待交换数字数组下标
    	 */
    	private static void swap(int n[], int i, int j) {
    		n[i] ^= n[j];
    		n[j] ^= n[i];
    		n[i] ^= n[j];
    	}

*  结果

堆排序结果：2 3 5 6 7 8 9

## 编码说明 ##

一、heapsort堆排序方法
    for循环（注意循环次数比数组长度小1，原因最低2个数构成最大堆）
    i.根据数组长度构建最大堆；
    ii.交换数组首位（最大堆根节点）与数组末位；
    
    二、buildHeap构建最大堆
    1.声明数组长度len；
    2.for循环从最后一个非叶子结点开始往回遍历到根节点;
     i.找到当前非叶子结点的左右子节点下标；
     ii.声明较大数指针，默认指向左子节点；
     iii.对比左右子节点，若右子节点存在且右大于左则指向右子节点；
     iv.对比交换较大的子节点和父节点。

## 结语 ##

本篇以最简单的图文形式讲解八大排序之一的堆排序的核心思想和具体实现，堆排序和快速排序均为相对其他排序出现频率最高的排序算法。

[format_png]: /images/20230528/4beba1fd7055466da8b0e625721efa5c.png
[format_png 1]: /images/20230528/2b35ed802c6b4f0abe40bb5ccc20643f.png
[format_png 2]: /images/20230528/59aa502a05764791bf0b8775cab55790.png
[format_png 3]: /images/20230528/408bdf5e87604682ba3815cf13ed775a.png
[format_png 4]: /images/20230528/c671f2ad4bc04b30a2943bde4ff96e09.png
[format_png 5]: /images/20230528/a1b042cd502f4ad2adc8142ebb792252.png
[format_png 6]: /images/20230528/67350825f6584ada93c3e29f1e0296c4.png
[format_png 7]: /images/20230528/7b4c6d58711a4507a4d6d6d2ff382f63.png
[format_png 8]: /images/20230528/e80364a667804657b167f4646011c663.png
[format_png 9]: /images/20230528/ef06964db1ee49929860097ab92080b0.png
[format_png 10]: /images/20230528/67a19d4d53934893ad6450cafcda15db.png
[format_png 11]: /images/20230528/8a60c1101c9240ffa25f41b15673bb11.png
[format_png 12]: /images/20230528/f62503f4a7f9416398f343e9226a4e93.png