本文共 2816 字，大约阅读时间需要 9 分钟。

选择排序和堆排序是两种经典的排序算法，在不同的场景下各有优劣。以下从原理、代码实现及性能分析等方面详细阐述。

选择排序

原理

选择排序是一种简单有效的排序算法。其工作原理是：每次从当前数组中找出最小或最大元素，将其移动到已排序区间的最末端或最前端。这个过程重复进行，直至整个数组排序完成。

具体而言：

这种方法的最优性在于其逻辑简单，时间复杂度为O(n²)，适合针对数据规模较小时使用。

代码实现

以下是基于Java的选择排序代码示例：

import java.util.Arrays;public class SelectSort {    public static void main(String[] args) {        int[] array = {5, 1, 25, 4, 8, 11, 5, 7, 5, 0};        System.out.println(Arrays.toString(array));        selectSort(array);        System.out.println(Arrays.toString(array));    }    public static void selectSort(int[] array) {        int left = 0, right = array.length - 1;        while (left < right) {            int maxPos = left;            for (int i = left + 1; i <= right; i++) {                if (array[i] > array[maxPos]) {                    maxPos = i;                }            }            int max = array[maxPos];            array[maxPos] = array[left];            array[left] = max;            left++;        }    }}

性能分析

• 时间复杂度：O(n²)，排序时间与数组长度的平方成正比。
• 空间复杂度：O(1)，算法仅使用常数额外空间。
• 稳定性：不稳定，较大值多次被交换可能破坏相对顺序。

堆排序

原理

堆排序与选择排序类似，但采用了不同的策略：通过构建堆（最大堆或最小堆）来快速找到无序区间的最大或最小值。关键步骤包括：

这与选择排序相比，减少了逐次查找最大值的时间复杂度，从O(n) 降低至 O(log n)，但增加了堆操作的复杂性。

代码实现

以下是基于Java的堆排序代码示例：

import java.util.Arrays;public class HeapSort {    public static void main(String[] args) {        int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};        printArray(array);        heapSort(array);        printArray(array);    }    private void printArray(int[] array) {        System.out.println(Arrays.toString(array));    }    public void heapSort(int[] array) {        int size = array.length;        int[] heap = new int[size];        for (int i = 0; i < size; i++) {            heap[i] = array[i];        }        for (int i = size - 1; i > 0; i--) {            adjustHeap(i, size);        }        int end = size - 1;        while (end > 0) {            int temp = heap[0];            heap[0] = heap[end];            heap[end] = temp;            adjustHeap(0, end);            end--;        }    }    private void adjustHeap(int parent, int len) {        int child = 2 * parent + 1;        while (child < len) {            if (child < len - 1 && heap[child] > heap[child + 1]) {                child++;            }            if (heap[child] > heap[parent]) {                swapElements(child, parent);                parent = child;                child = 2 * parent + 1;            } else {                break;            }        }    }    private void swapElements(int i, int j) {        int temp = heap[i];        heap[i] = heap[j];        heap[j] = temp;    }}

性能分析

• 时间复杂度：O(n log n)，排序时间与数组长度的对数成正比。
• 空间复杂度：O(n)，需要额外存储用于构建堆。
• 稳定性：不稳定，较大值多次被交换可能破坏相对顺序。

转载地址：http://bwkpz.baihongyu.com/