排序算法7：堆排序（HeapSort）

淩亂°似流年 2021-09-28 22:38 404阅读 0赞

# 排序算法7：堆排序（HeapSort） #

### 文章目录 ###

*  排序算法7：堆排序（HeapSort）
 *  前言
 *  1. 算法步骤
 *  2. 动图演示
 *  2、实现
 *   *  Java 代码实现
     *  JavaScript 代码实现
     *  Python 代码实现
     *  PHP 代码实现

# 前言 #

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；  
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；  
堆排序的平均时间复杂度为 Ο(nlogn)。

# 1. 算法步骤 #

1、创建一个堆 H\[0……n-1\]；

2、把堆首（最大值）和堆尾互换；

3、把堆的尺寸缩小 1，并调用 shift\_down(0)，目的是把新的数组顶端数据调整到相应位置；

4、重复步骤 2，直到堆的尺寸为 1。

# 2. 动图演示 #

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

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

# 2、实现 #

比如数组如下：  
1，2，4，3，0，-1

比如：该完全二叉树可以是：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmc0ODI_size_16_color_FFFFFF_t_70]

初始堆可以用完全二叉树标识，并且该完全二叉树可以用顺序数组标识。  
该数组特性有： 比如数组长度为n 某个节点i 可得出。  
节点i的父节点=（i-1）/2;  
节点i的左子节点 = 2\*i+ 1；  
节点i的右子节点

步骤：  
1、创建堆（完全二叉树），把数组元素放进去，该堆的层遍历和数组顺序一致  
2、调整堆为大根堆  
3、把根元素和堆尾替换  
4、删掉堆尾（堆尾部就是最大的数，删掉后重新调整，每次调整后堆尾部就是该堆最大数）  
5、重复2-4

## Java 代码实现 ##

public class HeapSort implements IArraySort { 
    
        @Override
        public int[] sort(int[] sourceArray) throws Exception { 
            // 对 arr 进行拷贝，不改变参数内容
            int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    
            int len = arr.length;
    
            buildMaxHeap(arr, len);
    
            for (int i = len - 1; i > 0; i--) { 
                swap(arr, 0, i);
                len--;
                heapify(arr, 0, len);
            }
            return arr;
        }
    
        private void buildMaxHeap(int[] arr, int len) { 
            for (int i = (int) Math.floor(len / 2); i >= 0; i--) { 
                heapify(arr, i, len);
            }
        }
    
        private void heapify(int[] arr, int i, int len) { 
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;
    
            if (left < len && arr[left] > arr[largest]) { 
                largest = left;
            }
    
            if (right < len && arr[right] > arr[largest]) { 
                largest = right;
            }
    
            if (largest != i) { 
                swap(arr, i, largest);
                heapify(arr, largest, len);
            }
        }
    
        private void swap(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }

## JavaScript 代码实现 ##

var len;    // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
    
    function buildMaxHeap(arr) {    // 建立大顶堆
        len = arr.length;
        for (var i = Math.floor(len/2); i >= 0; i--) { 
            heapify(arr, i);
        }
    }
    
    function heapify(arr, i) {      // 堆调整
        var left = 2 * i + 1,
            right = 2 * i + 2,
            largest = i;
    
        if (left < len && arr[left] > arr[largest]) { 
            largest = left;
        }
    
        if (right < len && arr[right] > arr[largest]) { 
            largest = right;
        }
    
        if (largest != i) { 
            swap(arr, i, largest);
            heapify(arr, largest);
        }
    }
    
    function swap(arr, i, j) { 
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    function heapSort(arr) { 
        buildMaxHeap(arr);
    
        for (var i = arr.length-1; i > 0; i--) { 
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

## Python 代码实现 ##

def buildMaxHeap(arr):
        import math
        for i in range(math.floor(len(arr)/2),-1,-1):
            heapify(arr,i)
    
    def heapify(arr, i):
        left = 2*i+1
        right = 2*i+2
        largest = i
        if left < arrLen and arr[left] > arr[largest]:
            largest = left
        if right < arrLen and arr[right] > arr[largest]:
            largest = right
    
        if largest != i:
            swap(arr, i, largest)
            heapify(arr, largest)
    
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]
    
    def heapSort(arr):
        global arrLen
        arrLen = len(arr)
        buildMaxHeap(arr)
        for i in range(len(arr)-1,0,-1):
            swap(arr,0,i)
            arrLen -=1
            heapify(arr, 0)
        return arr
    5. Go 代码实现
    func heapSort(arr []int) []int { 
    	arrLen := len(arr)
    	buildMaxHeap(arr, arrLen)
    	for i := arrLen - 1; i >= 0; i-- { 
    		swap(arr, 0, i)
    		arrLen -= 1
    		heapify(arr, 0, arrLen)
    	}
    	return arr
    }
    
    func buildMaxHeap(arr []int, arrLen int) { 
    	for i := arrLen / 2; i >= 0; i-- { 
    		heapify(arr, i, arrLen)
    	}
    }
    
    func heapify(arr []int, i, arrLen int) { 
    	left := 2*i + 1
    	right := 2*i + 2
    	largest := i
    	if left < arrLen && arr[left] > arr[largest] { 
    		largest = left
    	}
    	if right < arrLen && arr[right] > arr[largest] { 
    		largest = right
    	}
    	if largest != i { 
    		swap(arr, i, largest)
    		heapify(arr, largest, arrLen)
    	}
    }
    
    func swap(arr []int, i, j int) { 
    	arr[i], arr[j] = arr[j], arr[i]
    }

## PHP 代码实现 ##

参考文章：

[https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md][https_github.com_hustcc_JS-Sorting-Algorithm_blob_master_7.heapSort.md]

[20190605194254875.gif]: /images/20210923/08038bb5fc9a4f09b540ec8af82093e5.png
[20190605194305549.gif]: /images/20210923/5fdd2917482d4d04899d1606269c118e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bmZlbmc0ODI_size_16_color_FFFFFF_t_70]: /images/20210923/cd1a4e3a7ec644a0bd4a9a4e8dd1aedd.png
[https_github.com_hustcc_JS-Sorting-Algorithm_blob_master_7.heapSort.md]: https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md