网站是用php还是asp 怎么区别,局域网,网站搭建步骤,服装设计好找工作吗引言
在数据排序的世界里#xff0c;选择排序是一类简单而直观的算法#xff0c;它通过不断选取未排序部分中的最小#xff08;或最大#xff09;元素来逐步构建有序序列。今天#xff0c;我们将深入探讨两种基于选择思想的排序方法——直接选择排序和堆排序#xff0c;…引言
在数据排序的世界里选择排序是一类简单而直观的算法它通过不断选取未排序部分中的最小或最大元素来逐步构建有序序列。今天我们将深入探讨两种基于选择思想的排序方法——直接选择排序和堆排序并提供它们的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));}
}结语
通过上述讲解我们可以看出直接选择排序和堆排序虽然都属于选择排序但它们有着显著的不同之处。前者更易于理解和实现但在处理大数据量时效率较低后者则具有更好的性能表现特别是在需要频繁访问最大或最小值的应用场景下。希望这篇文章能为你揭开选择排序的神秘面纱并为你的编程之旅增添一份力量。
