csdn堆排序怎么排序
时间: 2023-12-31 19:02:02 浏览: 26
堆排序是一种经典的排序算法,使用堆数据结构实现。下面是CSDN堆排序的具体步骤:
1. 首先,将待排序的序列构建成一个最大堆。最大堆要求父节点的值大于等于其子节点的值。构建最大堆的方法是从最后一个非叶子节点开始,逐个向上调整节点使其满足堆的性质。
2. 构建最大堆后,将堆顶元素(最大值)与堆的最后一个元素交换位置,并将堆的大小减1,相当于将最大值移到了数组的最后位置。
3. 交换位置后,重新调整堆,使其满足最大堆的性质。
4. 重复步骤2和步骤3,直到堆的大小为1。
以下是CSDN堆排序的示例代码:
```java
public class HeapSort {
public static void heapSort(int[] array) {
int n = array.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// 交换堆顶元素与最后一个元素,并重新调整堆
for (int i = n - 1; i >= 0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapify(array, i, 0);
}
}
private static void heapify(int[] array, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
// 找到左右子节点中的最大值
if (left < n && array[left] > array[largest]) {
largest = left;
}
if (right < n && array[right] > array[largest]) {
largest = right;
}
// 如果最大值不是根节点,则交换位置,并继续调整堆
if (largest != i) {
int temp = array[i];
array[i] = array[largest];
array[largest] = temp;
heapify(array, n, largest);
}
}
public static void main(String[] args) {
int[] array = {4, 2, 6, 8, 3, 1, 9, 5, 7};
heapSort(array);
System.out.println(Arrays.toString(array));
}
}
```
以上就是CSDN堆排序的排序过程。堆排序的时间复杂度为O(nlogn),其中n为待排序序列的长度。该排序算法是一种不稳定的排序算法,因为在调整堆的过程中会交换元素的位置。