Java版堆排序

分析&回答

动态演示 -> 跳转到博客查看

实现代码

/**
 * 堆排序
 * <p>
 * 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
 * 将初始待排序关键字序列（R1，R2 ... .Rn）构建成大顶堆，此堆为初始的无序区;
 * 将堆顶元素R [1]与最后一个元素 - [R [n]的交换，此时得到新的无序区（R1，R2，...... Rn中-1）和新的有序区（RN），且满足ř并[1,2，...，N-1] <= R [N];
 * 由于交换后新的堆顶R [1]可能违反堆的性质，因此需要对当前无序区（R1，R2，...... Rn中-1）调整为新堆，
 *    然后再次将R [1]与无序区最后一个元素交换，得到新的无序区（R1，R2 ... .Rn-2）和新的有序区（RN-1，RN）的。
 *    不断重复此过程直到有序区的元素个数为ñ -1，则整个排序过程完成。
 * @param numbers
 */
public static void heapSort(int[] numbers) {
    int n = numbers.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heap(numbers, i, n);
    }
    for (int j = n - 1; j > 0; j--) {
        int temp = numbers[j];
        numbers[j] = numbers[0];
        numbers[0] = temp;
        heap(numbers, 0, j);
    }
}

public static void heap(int[] numbers, int index, int max) {
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    int larges = 0;
    if (left < max && numbers[left] > numbers[index]) {
        larges = left;
    } else {
        larges = index;
    }
    if (right < max && numbers[right] > numbers[larges]) {
        larges = right;
    }
    if (larges != index) {
        int temp = numbers[larges];
        numbers[larges] = numbers[index];
        numbers[index] = temp;
        heap(numbers, larges, max);
    }
}

性能分析

• 不稳定 
• 平均时间复杂度O(n ㏒n)
• 空间复杂度O(1) 

堆排序简单总结：

• 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
• 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
• 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

反思&扩展

Java版常用排序算法复杂度