Java实现：常见排序算法（选择、冒泡、插入）详解

本文档主要介绍了三种常见的基础排序算法：选择排序、冒泡排序和插入排序，它们在计算机科学中被广泛应用于数据的预处理和初步组织。接下来，我们将逐一探讨这些算法的实现细节、时间复杂度、空间复杂度以及稳定性。 ### 1. **选择排序（Selection Sort）** 选择排序是一种简单直观的排序算法，其时间复杂度为 O(N^2)，其中 N 是数组的长度。它具有线性额外空间复杂度，即 O(1)。非稳定性体现在排序过程中，可能会改变相同元素的相对位置。算法的核心逻辑是遍历数组，每次找到剩余部分中的最小（或最大）元素，然后将其放置在已排序部分的末尾。Java 实现如下： ```java public class SelectionSort { public static void selectionSort(int[] arr) { if (arr == null || arr.length == 0) return; 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; } Swap.swap_simple(i, minIndex, arr); } } } ``` ### 2. **冒泡排序（Bubble Sort）** 冒泡排序也是 O(N^2) 时间复杂度，但它是稳定的排序方法，因为如果两个相邻元素相等，它们的位置不会改变。算法通过反复交换相邻的元素，将较大的数逐渐“冒”到数组的末尾。Java 实现如下： ```java public class BubbleSort { public static void bubbleSort(int[] arr) { if (arr == null || arr.length == 0) return; for (int e = arr.length - 1; e > 0; e--) { for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { Swap.swap_bit(i, i + 1, arr); } } } } } ``` ### 3. **插入排序（Insertion Sort）** 插入排序的时间复杂度取决于输入数据的状态。在最好情况下（数组已经排序），它的时间复杂度为 O(N)；最坏情况下（逆序数组），时间复杂度为 O(N^2)。插入排序的空间复杂度为 O(1)。算法的工作原理是将每个元素插入到已排序部分的正确位置，这类似于把扑克牌逐张插入已排序的部分。Java 实现没有给出，但大致可以理解为： ```java public class InsertionSort { public static void insertionSort(int[] arr) { // 类似于上述冒泡排序，通过循环逐步完成排序 // ... } } ``` 总结起来，选择排序、冒泡排序和插入排序都是简单的排序算法，适用于小型数据集或作为更复杂算法的辅助步骤。理解它们的工作原理和性能特点有助于在实际编程中根据具体需求选择合适的排序策略。