堆排序时间复杂度和桶排序的时间复杂度

堆排序的时间复杂度为O(nlogn)，桶排序的时间复杂度为O(n)。

堆排序是一种基于二叉堆的排序算法，它的时间复杂度为O(nlogn)。堆排序的过程包括建堆和排序两个步骤。建堆的时间复杂度为O(n)，排序的时间复杂度为O(nlogn)。因此，堆排序的总时间复杂度为O(nlogn)。

桶排序是一种线性时间复杂度的排序算法，它的时间复杂度为O(n)。桶排序的过程是将待排序的元素分配到不同的桶中，然后对每个桶中的元素进行排序，最后将所有桶中的元素按顺序合并起来。由于桶排序的过程中，每个元素只需要与其他桶中的元素进行比较，所以桶排序的时间复杂度为O(n)。

以下是堆排序和桶排序的示例代码：

堆排序的示例代码：

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)

arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:", arr)

桶排序的示例代码：

def bucketSort(arr):
    n = len(arr)
    max_val = max(arr)
    min_val = min(arr)
    bucket_range = (max_val - min_val) / n

    buckets = [[] for _ in range(n)]

    for num in arr:
        index = int((num - min_val) / bucket_range)
        buckets[index].append(num)

    for i in range(n):
        buckets[i].sort()

    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

arr = [12, 11, 13, 5, 6, 7]
sorted_arr = bucketSort(arr)
print("Sorted array is:", sorted_arr)