點擊下載
本文文檔

當前位置：首頁 - 科技 - 知識百科 - 正文

堆排序怎么建立初始堆

來源：懂視網責編：小采時間：2022-08-04 22:12:29

堆排序怎么建立初始堆

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

推薦度：

點擊下載本文 文檔為doc格式

導讀堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。以下是堆排序算法：

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；
小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

堆排序的平均時間復雜度為 Ο(nlogn)。

1. 算法步驟

創建一個堆 H[0……n-1]；
把堆首（最大值）和堆尾互換；
把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；
重復步驟 2，直到堆的尺寸為 1。

2. 動圖演示

代碼實現

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

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]
}

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;
}

}

PHP

實例

function buildMaxHeap(&$arr)
{
global $len;
for ($i = floor($len/2); $i >= 0; $i--) {
heapify($arr, $i);
}
}

function heapify(&$arr, $i)
{
global $len;
$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)
{
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}

function heapSort($arr) {
global $len;
$len = count($arr);
buildMaxHeap($arr);
for ($i = count($arr) - 1; $i > 0; $i--) {
swap($arr, 0, $i);
$len--;
heapify($arr, 0);
}
return $arr;
}

C

實例

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
}

void max_heapify(int arr[], int start, int end) {
// 建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { // 若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else { // 否則交換父子內容再繼續子節點和孫節點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}

void heap_sort(int arr[], int len) {
int i;
// 初始化，i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}

int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf(" ");
return 0;
}

C++

實例

#include <iostream>
#include <algorithm>
using namespace std;

void max_heapify(int arr[], int start, int end) {
// 建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { // 若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else { // 否則交換父子內容再繼續子節點和孫節點比較
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}

void heap_sort(int arr[], int len) {
// 初始化，i從最後一個父節點開始調整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// 先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完畢
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}

int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
return 0;
}

參考文章：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/7.heapSort.md
https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

以下是熱心網友對堆排序算法的補充，僅供參考：

熱心網友提供的補充1：

上方又沒些 C# 的堆排序，艾孜爾江補充如下：

/// <summary>
/// 堆排序
/// </summary>
/// <param name="arr">待排序數組</param>
static void HeapSort(int[] arr)
{
    int vCount = arr.Length;
    int[] tempKey = new int[vCount + 1];
    // 元素索引從1開始
    for (int i = 0; i < vCount; i++)
    {
        tempKey[i + 1] = arr[i];
    }
    // 初始數據建堆（從含最后一個結點的子樹開始構建，依次向前，形成整個二叉堆）
    for (int i = vCount / 2; i >= 1; i--)
    {
        Restore(tempKey, i, vCount);
    }
    // 不斷輸出堆頂元素、重構堆，進行排序
    for (int i = vCount; i > 1; i--)
    {
        int temp = tempKey[i];
        tempKey[i] = tempKey[1];
        tempKey[1] = temp;
        Restore(tempKey, 1, i - 1);
    }
    //排序結果
    for (int i = 0; i < vCount; i++)
    {
        arr[i] = tempKey[i + 1];
    }
}
/// <summary>
/// 二叉堆的重構（針對于已構建好的二叉堆首尾互換之后的重構）
/// </summary>
/// <param name="arr"></param>
/// <param name="rootNode">根結點j</param>
/// <param name="nodeCount">結點數</param>
static void Restore(int[] arr, int rootNode, int nodeCount)
{
    while (rootNode <= nodeCount / 2) // 保證根結點有子樹
    {
        //找出左右兒子的最大值
        int m = (2 * rootNode + 1 <= nodeCount && arr[2 * rootNode + 1] > arr[2 * rootNode]) ? 2 * rootNode + 1 : 2 * rootNode;
        if (arr[m] > arr[rootNode])
        {
            int temp = arr[m];
            arr[m] = arr[rootNode];
            arr[rootNode] = temp;
            rootNode = m;
        }
        else
        {
            break;
        }
    }
}

熱心網友提供的補充2：

堆排序是不穩定的排序！

既然如此，每次構建大頂堆時，在父節點、左子節點、右子節點取三者中最大者作為父節點就行。我們追尋的只是最終排序后的結果，所以可以簡化其中的步驟。

我將個人寫的 Java 代碼核心放在下方，有興趣的同學可以一起討論下：

public int[] sort(int a[]) {
    int len = a.length - 1;    
    for (int i = len; i > 0; i--) {
        maxHeap(a, i);        
        //交換 跟節點root 與 最后一個子節點i 的位置        
        swap(a, 0, i);        
        //i--無序數組尺寸減少了 
    }  
    return a;
}

/**構建一個大頂堆（完全二叉樹 ） 
* 從  最后一個非葉子節點  開始，若父節點小于子節點，則互換他們兩的位置。然后依次從右至左，從下到上進行！ 
* 最后一個非葉子節點，它的葉子節點 必定包括了最后一個（葉子）節點，所以 最后一個非葉子節點是 a[（n+1）/2-1] 
 
* @param a 
* @param lastIndex 這個數組的最后一個元素 
*/
static void maxHeap(int a[], int lastIndex) {
    for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
       //反正 堆排序不穩定，先比較父與左子，大則交換；與右子同理。（不care 左子與右子位置是否變了?。?
        if (i * 2 + 1 <= lastIndex && a[i] < a[i * 2 + 1]) {
            swap(a, i, i * 2 + 1);        
        }    
        if (i * 2 + 2 <= lastIndex && a[i] < a[i * 2 + 2]) {
            swap(a, i, i * 2 + 2);        
        }
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

以上為堆排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用一張圖概括：

關于時間復雜度

平方階 (O(n2)) 排序各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序快速排序、堆排序和歸并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數。希爾排序

線性階 (O(n)) 排序基數排序，此外還有桶、箱排序。

關于穩定性

穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模

k："桶"的個數

In-place：占用常數內存，不占用額外內存

Out-place：占用額外內存

穩定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:0731-84117792 E-MAIL:11247931@qq.com

堆排序怎么建立初始堆

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

推薦度：

點擊下載本文 文檔為doc格式

熱門焦點

最新推薦

猜你喜歡

熱門推薦

產品服務發展歷程企業資訊企業文化關于我們加入我們聯系我們網站導航網站律師

中國掃黃打非網

Copyright ? 2019-2022 湖南福仁科技有限公司版權所有

湘ICP備19013665號-5 視頻許可證編號：（湘）字第00637號湘公網安備 43010402000898號

違法及侵權請聯系：TEL:0731-84117792 E-MAIL:11247931@qq.com 本站由北京市萬商天勤律師事務所王興未律師提供法律服務

Top 国产精品久久久久精品…-国产精品可乐视频最新-亚洲欧美重口味在线-欧美va免费在线观看