Jadual Kandungan
Python 代码实现
Rumah pembangunan bahagian belakang Tutorial Python python如何实现堆排序(代码示例)

python如何实现堆排序(代码示例)

Nov 12, 2018 pm 05:28 PM
python

本篇文章给大家带来的内容是关于python如何实现堆排序(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点(但是不保证所有左子树比右子树小反之亦然)。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;

小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

堆排序的平均时间复杂度为 Ο(nlogn)。

算法步骤

1、创建一个堆 H[0……n-1];(**对非叶子节点的子节点进行调节,构建堆**)

2、把堆首(最大值)和堆尾互换;

3、把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;

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

Python 代码实现

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-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
Salin selepas log masuk

Atas ialah kandungan terperinci python如何实现堆排序(代码示例). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
1 bulan yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Bolehkah penterjemah Python dipadam dalam sistem Linux? Bolehkah penterjemah Python dipadam dalam sistem Linux? Apr 02, 2025 am 07:00 AM

Mengenai masalah menghapuskan penterjemah python yang dilengkapi dengan sistem Linux, banyak pengagihan Linux akan memasang semula penterjemah python apabila dipasang, dan ia tidak menggunakan pengurus pakej ...

Bagaimana menyelesaikan masalah pengesanan jenis pylance penghias tersuai di Python? Bagaimana menyelesaikan masalah pengesanan jenis pylance penghias tersuai di Python? Apr 02, 2025 am 06:42 AM

Penyelesaian Masalah Pengesanan Jenis Pylance Apabila menggunakan penghias tersuai dalam pengaturcaraan python, penghias adalah alat yang berkuasa yang boleh digunakan untuk menambah baris ...

Python 3.6 Memuatkan Ralat Fail Pickle ModulenotFoundError: Apa yang perlu saya lakukan jika saya memuatkan fail acar '__builtin__'? Python 3.6 Memuatkan Ralat Fail Pickle ModulenotFoundError: Apa yang perlu saya lakukan jika saya memuatkan fail acar '__builtin__'? Apr 02, 2025 am 06:27 AM

Memuatkan Fail Pickle di Python 3.6 Kesalahan Alam Sekitar: ModulenotFoundError: Nomodulenamed ...

Adakah Fastapi dan AIOHTTP berkongsi gelung acara global yang sama? Adakah Fastapi dan AIOHTTP berkongsi gelung acara global yang sama? Apr 02, 2025 am 06:12 AM

Isu keserasian antara perpustakaan asynchronous Python di Python, pengaturcaraan tak segerak telah menjadi proses kesesuaian tinggi dan I/O ...

Bagaimana untuk memastikan bahawa proses kanak -kanak juga tamat selepas membunuh proses induk melalui isyarat di Python? Bagaimana untuk memastikan bahawa proses kanak -kanak juga tamat selepas membunuh proses induk melalui isyarat di Python? Apr 02, 2025 am 06:39 AM

Masalah dan penyelesaian proses kanak -kanak terus berjalan apabila menggunakan isyarat untuk membunuh proses induk. Dalam pengaturcaraan Python, selepas membunuh proses induk melalui isyarat, proses anak masih ...

Apa yang perlu saya lakukan jika modul '__builtin__' tidak dijumpai apabila memuatkan fail acar di Python 3.6? Apa yang perlu saya lakukan jika modul '__builtin__' tidak dijumpai apabila memuatkan fail acar di Python 3.6? Apr 02, 2025 am 07:12 AM

Memuatkan Fail Pickle di Python 3.6 Kesalahan Laporan Alam Sekitar: ModulenotFoundError: Nomodulenamed ...

See all articles