python实现heapsort算法

Heapsort算法是一种基于堆数据结构的排序算法。在堆中，每个节点的值都大于或小于它的子节点的值，这种性质被称为堆属性。在Heapsort算法中，首先将未排序的列表构建成最大堆（或最小堆），然后对堆进行排序，每次取出堆顶元素，将其放到数组的末尾，然后重新构建堆，重复上述操作，直到整个列表排序完成。Heapsort算法的时间复杂度为O(nlogn)，它具有稳定性、适用于数据量很大的排序任务和同时排序多个数据的优点。

相关问题

python可视化界面实现十大排序算法

可以使用 Python 的 tkinter 模块来实现可视化界面，使用 matplotlib 库来绘制排序过程中的图形。

以下是一个示例代码，实现了十大排序算法的可视化界面：

import random
import time
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
import tkinter as tk


class SortingVisualization:
    def __init__(self, sort_algorithm, length=100):
        self.length = length
        self.data = [i+1 for i in range(length)]
        random.shuffle(self.data)
        self.sort_algorithm = sort_algorithm(self.data)
        
        self.fig, self.ax = plt.subplots()
        self.ax.set_title(self.sort_algorithm.__class__.__name__)
        self.bar_rects = self.ax.bar(range(len(self.data)), self.data, align="edge")
        self.ax.set_xlim(0, len(self.data))
        self.ax.set_ylim(0, int(1.07 * length))
        
        self.iteration = self.sort_algorithm.sort()
        self.start_time = time.time()
        
    def update(self, rects, iteration):
        for rect, val in zip(rects, self.data):
            rect.set_height(val)
        try:
            next(self.iteration)
        except StopIteration:
            self.ax.set_title(f"{self.sort_algorithm.__class__.__name__} ({time.time()-self.start_time:.2f}s)")
            return False
        return True
        
    def animate(self, i):
        return self.update(self.bar_rects, i)
    
    def start(self):
        anim = FuncAnimation(self.fig, self.animate, frames=range(len(self.data)), interval=1,
                             repeat=False, blit=True)
        plt.show()


class BubbleSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        n = len(self.data)
        for i in range(n):
            for j in range(n-i-1):
                if self.data[j] > self.data[j+1]:
                    self.data[j], self.data[j+1] = self.data[j+1], self.data[j]
            yield


class SelectionSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        n = len(self.data)
        for i in range(n):
            min_idx = i
            for j in range(i+1, n):
                if self.data[min_idx] > self.data[j]:
                    min_idx = j
            self.data[i], self.data[min_idx] = self.data[min_idx], self.data[i]
            yield


class InsertionSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        n = len(self.data)
        for i in range(1, n):
            key = self.data[i]
            j = i - 1
            while j >= 0 and key < self.data[j]:
                self.data[j+1] = self.data[j]
                j -= 1
                yield
            self.data[j+1] = key
            yield


class QuickSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        def _quick_sort(l, r):
            if l < r:
                p = self.partition(l, r)
                yield from _quick_sort(l, p-1)
                yield from _quick_sort(p+1, r)
        yield from _quick_sort(0, len(self.data)-1)
                
    def partition(self, l, r):
        pivot = self.data[r]
        i = l - 1
        for j in range(l, r):
            if self.data[j] < pivot:
                i += 1
                self.data[i], self.data[j] = self.data[j], self.data[i]
                yield
        self.data[i+1], self.data[r] = self.data[r], self.data[i+1]
        yield
        return i + 1


class MergeSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        def _merge_sort(l, r):
            if l < r:
                m = (l + r) // 2
                yield from _merge_sort(l, m)
                yield from _merge_sort(m+1, r)
                yield from self.merge(l, m, r)
        yield from _merge_sort(0, len(self.data)-1)
                
    def merge(self, l, m, r):
        L = self.data[l:m+1]
        R = self.data[m+1:r+1]
        i = j = 0
        k = l
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                self.data[k] = L[i]
                i += 1
            else:
                self.data[k] = R[j]
                j += 1
            k += 1
            yield
        while i < len(L):
            self.data[k] = L[i]
            i += 1
            k += 1
            yield
        while j < len(R):
            self.data[k] = R[j]
            j += 1
            k += 1
            yield


class HeapSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        n = len(self.data)
        for i in range(n // 2 - 1, -1, -1):
            yield from self.heapify(n, i)
        for i in range(n-1, 0, -1):
            self.data[0], self.data[i] = self.data[i], self.data[0]
            yield
            yield from self.heapify(i, 0)
                
    def heapify(self, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and self.data[largest] < self.data[l]:
            largest = l
        if r < n and self.data[largest] < self.data[r]:
            largest = r
        if largest != i:
            self.data[i], self.data[largest] = self.data[largest], self.data[i]
            yield
            yield from self.heapify(n, largest)
            

class ShellSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        n = len(self.data)
        gap = n // 2
        while gap > 0:
            for i in range(gap, n):
                temp = self.data[i]
                j = i
                while j >= gap and self.data[j-gap] > temp:
                    self.data[j] = self.data[j-gap]
                    j -= gap
                    yield
                self.data[j] = temp
                yield
            gap //= 2
            

class CountingSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        n = len(self.data)
        output = [0] * n
        count = [0] * (max(self.data) + 1)
        for i in range(n):
            count[self.data[i]] += 1
        for i in range(1, len(count)):
            count[i] += count[i-1]
        for i in range(n-1, -1, -1):
            output[count[self.data[i]]-1] = self.data[i]
            count[self.data[i]] -= 1
            yield
        self.data = output


class RadixSort:
    def __init__(self, data):
        self.data = data
        
    def sort(self):
        def _counting_sort(exp):
            n = len(self.data)
            output = [0] * n
            count = [0] * 10
            for i in range(n):
                idx = (self.data[i] // exp) % 10
                count[idx] += 1
            for i in range(1, len(count)):
                count[i] += count[i-1]
            for i in range(n-1, -1, -1):
                idx = (self.data[i] // exp) % 10
                output[count[idx]-1] = self.data[i]
                count[idx] -= 1
                yield
            self.data = output
        
        max_val = max(self.data)
        exp = 1
        while max_val // exp > 0:
            yield from _counting_sort(exp)
            exp *= 10


class GUI:
    def __init__(self):
        self.window = tk.Tk()
        self.window.title("Sorting Visualization")
        self.window.geometry("320x240")
        
        self.sorts = {"Bubble Sort": BubbleSort, "Selection Sort": SelectionSort, 
                      "Insertion Sort": InsertionSort, "Quick Sort": QuickSort,
                      "Merge Sort": MergeSort, "Heap Sort": HeapSort, 
                      "Shell Sort": ShellSort, "Counting Sort": CountingSort, 
                      "Radix Sort": RadixSort}
        self.sort_var = tk.StringVar(self.window, sorted(self.sorts.keys())[0])
        sort_menu = tk.OptionMenu(self.window, self.sort_var, *self.sorts.keys())
        sort_menu.pack(pady=10)
        
        length_var = tk.StringVar(self.window, "100")
        length_entry = tk.Entry(self.window, textvariable=length_var)
        length_entry.pack(pady=5)
        
        start_button = tk.Button(self.window, text="Start", command=self.start)
        start_button.pack(pady=10)
        
        self.window.mainloop()
        
    def start(self):
        try:
            length = int(length_var.get())
            sort_algorithm = self.sorts[self.sort_var.get()]
            SortingVisualization(sort_algorithm, length).start()
        except ValueError:
            return
    

if __name__ == "__main__":
    GUI()

运行该代码，会弹出一个 GUI 界面，选择排序算法和数据长度后，点击 Start 按钮即可开始可视化排序过程。

注意：由于排序算法的实现方式不同，排序时间也会有所不同，因此排序过程中的动画时间也会有所不同。

用python实现堆排序

可以使用以下代码实现堆排序：

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]

        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr

这个代码实现了堆排序算法，可以对一个数组进行排序。