java实现堆排序以及时间复杂度的分析

下面我会详细讲解“java实现堆排序以及时间复杂度的分析”的完整攻略，包括定义、算法步骤、实现过程和时间复杂度的分析。

定义

堆排序是一种树形选择排序，它的排序过程类似于选择排序，建立在堆的基础之上。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：

• 父节点的键值总是大于或等于任何一个子节点的键值。
• 每个节点的左右子树都是一个堆。

算法步骤

1. 创建一个初始数组，并将其转换为最大堆。最大堆是指，除根节点外，其它节点都满足父节点的值大于子节点。
2. 交换根节点与最后一个节点，使最后一个节点成为新的堆的根节点。
3. 对新的堆进行排序，除根节点外将其它节点转换为最大堆。
4. 重复步骤2和3，直到全部节点都已经完成排序。

实现过程

public void heapSort(int[] arr) {
    // Step 1: 转换为最大堆
    createMaxHeap(arr);

    // Step 2-4: 实现排序
    for (int i = arr.length - 1; i >= 0; i--) {
        swap(arr, 0, i);
        maxHeapify(arr, i, 0);
    }
}

// 创建最大堆
void createMaxHeap(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--)
        maxHeapify(arr, arr.length, i);
}

// 整理堆
void maxHeapify(int[] arr, int heapSize, int idx) {
    int leftIdx = idx * 2 + 1;
    int rightIdx = leftIdx + 1;
    int largestElemIdx = idx;

    if (leftIdx < heapSize && arr[leftIdx] > arr[largestElemIdx])
        largestElemIdx = leftIdx;
    if (rightIdx < heapSize && arr[rightIdx] > arr[largestElemIdx])
        largestElemIdx = rightIdx;

    if (largestElemIdx != idx) {
        swap(arr, largestElemIdx, idx);
        maxHeapify(arr, heapSize, largestElemIdx);
    }
}

// 交换数组中的值
void swap(int[] arr, int idx1, int idx2) {
    int tmp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = tmp;
}

时间复杂度的分析

堆排序的时间复杂度为O(n*log n)。其中，O(log n)为调整堆节点的时间复杂度，总共需要调整n个节点。因此，堆排序的时间复杂度近似与归并排序，但堆排序的空间复杂度更优，为O(1)。

示例：

假设需要对下列无序数组进行排序：arr = [4, 1, 6, 9, 3, 2]。

1. 首先将数组转换为最大堆，即[9, 4, 6, 1, 3, 2]。
2. 交换最大堆的根节点9和最后一个节点2，得到[2, 4, 6, 1, 3, 9]。
3. 对除根节点外的剩余节点进行最大堆转换，得到[6, 4, 2, 1, 3]。
4. 交换最大堆的根节点6和最后一个节点3，得到[3, 4, 2, 1, 6]。
5. 对除根节点外的剩余节点进行最大堆转换，得到[4, 3, 2, 1]。
6. 交换最大堆的根节点4和最后一个节点1，得到[1, 3, 2, 4]。
7. 对除根节点外的剩余节点进行最大堆转换，得到[3, 1, 2]。
8. 交换最大堆的根节点3和最后一个节点2，得到[2, 1, 3]。
9. 对除根节点外的剩余节点进行最大堆转换，得到[2, 1]。
10. 交换最大堆的根节点2和最后一个节点1，得到[1, 2]。
11. 最后得到有序数组[1, 2, 3, 4, 6]。