【唐叔学算法】第18天：解密选择排序的双重魅力-直接选择排序与堆排序的Java实现及性能剖析

引言

在数据排序的世界里，选择排序是一类简单而直观的算法，它通过不断选取未排序部分中的最小（或最大）元素来逐步构建有序序列。今天，我们将深入探讨两种基于选择思想的排序方法——直接选择排序和堆排序，并提供它们的Java实现代码。此外，我们还会分析这两种排序算法的时间复杂度和空间复杂度，帮助你理解其背后的运作机制。

直接选择排序（Selection Sort）

算法描述

直接选择排序是一种最基础的选择排序形式。它的基本思想是每次从未排序的元素中选出最小的一个元素，然后将其与未排序部分的第一个元素交换位置。如此反复，直到所有元素都被排好序为止。

时间复杂度

• 最佳、平均和最差情况均为 O(n²)，其中 n 是待排序数组的长度。

空间复杂度

• 因为只需要常数级别的额外空间，所以空间复杂度为 O(1)。

Java实现

public class SelectionSort {
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换找到的最小元素和当前元素
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] data = {64, 25, 12, 22, 11};
        sort(data);
        System.out.println("Sorted array: " + Arrays.toString(data));
    }
}

堆排序（Heap Sort）

算法描述

堆排序利用了二叉堆的数据结构特性。首先将待排序的数组构建成一个大根堆（对于升序排列），接着依次取出堆顶的最大元素放到数组末尾，再调整剩余元素重新构成大根堆，重复此过程直至所有元素都被排序。

时间复杂度

• 构建堆的时间复杂度为 O(n)，而每一次调整堆的操作时间复杂度为 O(log n)，因此总的时间复杂度为 O(n log n)。

空间复杂度

• 和直接选择排序一样，堆排序的空间复杂度也是 O(1)，因为它是在原地进行排序。

Java实现

public class HeapSort {
    public static void sort(int[] arr) {
        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--) {
            // 移动当前根到末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调用heapify函数在减少的堆上
            heapify(arr, i, 0);
        }
    }

    // 对大小为n的以i为根节点的堆进行heapify操作
    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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归地heapify受影响的子树
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] data = {12, 11, 13, 5, 6, 7};
        sort(data);
        System.out.println("Sorted array is: " + Arrays.toString(data));
    }
}

结语

通过上述讲解，我们可以看出直接选择排序和堆排序虽然都属于选择排序，但它们有着显著的不同之处。前者更易于理解和实现，但在处理大数据量时效率较低；后者则具有更好的性能表现，特别是在需要频繁访问最大或最小值的应用场景下。希望这篇文章能为你揭开选择排序的神秘面纱，并为你的编程之旅增添一份力量。