排序算法之堆排序

╰+哭是因爲堅強的太久メ 2023-02-18 14:15 92阅读 0赞

堆排序的时间复杂度O(N\*logN),额外空间复杂度O(1)，是一个不稳定性的排序

![在这里插入图片描述][20200806095320516.gif]

# 准备 #

堆的结构可以分为大根堆和小根堆，是一个**完全二叉树**，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆

## 大根堆&&小根堆 ##

性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
我们对上面的图中每个数都进行了标记，上面的结构映射成数组就变成了下面这个样子  
![在这里插入图片描述][2020061811045624.png]  
还有一个基本概念：查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么

*  父结点索引：**(i-1)/2**（这里计算机中的除以2，省略掉小数）
 *  左孩子索引：**2\*i+1**
 *  右孩子索引：**2\*i+2**

所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：

*  大根堆：**arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)**
 *  小根堆：**arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)**

## 最后一个非叶子节点的序号是n/2-1的推理 ##

可以分两种情形考虑：

1.堆的最后一个非叶子节点若只有左子节点  
2.堆的最后一个非叶子节点有左右两个子节点

堆的定义：  
大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]  
小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]

完全二叉树的性质之一是：如果节点序号为i，在它的左子节点序号为2i+1，右子节点序号为2i+2。

对于第一种情形：左子节点的序号为n-1，则n-1=2\*i+1，推出i=n/2-1；

对于第二种情形：左子节点的序号为n-2，在n-2=2i+1，推出i=(n-1)/2-1；右子节点的序号为n-1，则n-1=2i+2，推出i=(n-1)/2-1；

很显然，当完全二叉树最后一个节点是其父节点的左子节点时，树的节点数为偶数；当完全二叉树最后一个节点是其父节点的右子节点时，树的节点数为奇数。

根据语法的特征，/ 符号取整，则若n为奇数时(n-1)/2-1=n/2-1。

# 代码实现 #

## Java ##

代码中主要两个方法：

1、将待排序数组构造成一个大根堆（元素上升）

2、固定一个最大值，将剩余的数再构造成一个大根堆（元素下降）

//堆排序
        public static void heapSort(int[] arr) {
        
            //构造大根堆
            heapInsert(arr);
            int size = arr.length;
            while (size > 1) {
        
                //固定最大值
                swap(arr, 0, size - 1);
                size--;
                //构造大根堆
                heapify(arr, 0, size);
     
            }
     
        }
     
        //构造大根堆（通过新插入的数上升）
        public static void heapInsert(int[] arr) {
        
            for (int i = 0; i < arr.length; i++) {
        
                //当前插入的索引
                int currentIndex = i;
                //父结点索引
                int fatherIndex = (currentIndex - 1) / 2;
                //如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
                //然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
                while (arr[currentIndex] > arr[fatherIndex]) {
        
                    //交换当前结点与父结点的值
                    swap(arr, currentIndex, fatherIndex);
                    //将当前索引指向父索引
                    currentIndex = fatherIndex;
                    //重新计算当前索引的父索引
                    fatherIndex = (currentIndex - 1) / 2;
                }
            }
        }
        //将剩余的数构造成大根堆（通过顶端的数下降）
        public static void heapify(int[] arr, int index, int size) {
        
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            while (left < size) {
        
                int largestIndex;
                //判断孩子中较大的值的索引（要确保右孩子在size范围之内）
                if (arr[left] < arr[right] && right < size) {
        
                    largestIndex = right;
                } else {
        
                    largestIndex = left;
                }
                //比较父结点的值与孩子中较大的值，并确定最大值的索引
                if (arr[index] > arr[largestIndex]) {
        
                    largestIndex = index;
                }
                //如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
                if (index == largestIndex) {
        
                    break;
                }
                //父结点不是最大值，与孩子中较大的值交换
                swap(arr, largestIndex, index);
                //将索引指向孩子中较大的值的索引
                index = largestIndex;
                //重新计算交换之后的孩子的索引
                left = 2 * index + 1;
                right = 2 * index + 2;
            }
     
        }
        //交换数组中两个元素的值
        public static void swap(int[] arr, int i, int j) {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

## golang ##

package main
    
    import (
    	"fmt"
    )
    
    // 最大堆登顶
    func HeapFindMax(arr[]int,  size int)  {
        
    	if size <= 1{
        
    		return
    	}else{
        
    		noLeaf := size / 2 - 1  // 最后一个非叶子节点索引
    		for i := noLeaf ; i >= 0; i-- {
         // 最后一个非叶子节点索引为0
    			left := 2 * i + 1   // 左孩子索引
    			right := 2 * i + 2 // 右孩子索引
    
    			max := i //假定当前索引为最大值
    
    			if left < size && arr[left] > arr[max] {
         // 避免溢出
    				max = left
    			}
    
    			if right < size && arr[right] > arr[max] {
        
    				max = right
    			}
    
    			if max != i {
          // 最大登顶
    				arr[max], arr[i] = arr[i], arr[max]
    			}
    		}
    	}
    }
    
    func HeapSort(arr []int)  {
        
    	size := len(arr)
    	if size <= 1{
        
    		return
    	}else{
        
    		for i := 0; i < size ; i++ {
        
    			cut := size - i // 每次截取一个
    			HeapFindMax(arr, cut)
    			if cut - 1 > 0 {
        
    				arr[0], arr[cut - 1] = arr[cut - 1], arr[0]
    			}
    		}
    	}
    }
    
    func main() {
        
    	arr:=[]int {
        9, 1, 3, 6, 5, 4, 2, 7, 8}
    	HeapSort(arr)
    	fmt.Println(arr)
    }

[20200806095320516.gif]: https://img-blog.csdnimg.cn/20200806095320516.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200618110420995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[2020061811045624.png]: https://img-blog.csdnimg.cn/2020061811045624.png