堆排序
堆排序的python实现
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序。
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾
元素就变成了最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复进行交换、重建堆的操作，直到
排序完成。
堆排序流程
- 将无序序列构造成一个大顶堆。
- 交换堆顶元素和末尾元素。
- 重新调整结构，使其满足大顶堆定义。
- 重复步骤2、3，直到排序完成。
堆排序实现
Python
def heapify(arr: List, n: int, i: int) -> None:
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr: List) -> List:
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 arrJava
public class HeapSort {
public static void heapSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}堆排序时间复杂度
堆排序的时间复杂度为O(nlogn)。