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

news/2024/12/23 16:56:27/

引言

在数据排序的世界里，选择排序是一类简单而直观的算法，它通过不断选取未排序部分中的最小（或最大）元素来逐步构建有序序列。今天，我们将深入探讨两种基于选择思想的排序方法——直接选择排序和堆排序，并提供它们的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));}
}