常见排序算法及Java实现 冒泡排序 选择排序

1 冒泡排序
核心思想：重复地遍历要排序的列表，一次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。这个过程就像最大的气泡（最大的数字）一次次地“沉”到列表的底部。

时间复杂度：

最坏情况：数组完全逆序。需要比较 (n-1) + (n-2) + … + 1 = n(n-1)/2 次。所以是 O(n²)。

最好情况：数组已经有序。优化后的算法只需要遍历一次（n-1次比较）就会退出。所以是 O(n)。

平均情况：O(n²)。

空间复杂度：

排序过程只在原数组内部进行交换，只需要一个临时变量用于交换。所以是 O(1)，属于原地排序。
// 冒泡排序实现
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 优化标志：如果某次遍历没有交换，说明已排序完成
boolean swapped;

for (int i = 0; i < n – 1; i++) {
swapped = false;
// 每次遍历将最大的元素”冒泡”到最后
for (int j = 0; j < n – i – 1; j++) {
// 比较相邻元素
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

// 如果没有发生交换，说明数组已经有序
if (!swapped) {
break;
}
}
}

2 选择排序
核心思想：不断地从剩余未排序的元素中选择最小（或最大）的那个，将其放到已排序序列的末尾。

时间复杂度：

最好、最坏、平均情况均为 O(n²)。

无论数组是否有序，算法都需要进行 (n-1) + (n-2) + … + 1 = n(n-1)/2 次比较来寻找最小值。这是一个固定的次数。

交换操作的次数是 O(n)，最多进行 n-1 次交换。这比冒泡排序（交换次数多）要好一些。

空间复杂度：

排序过程只在原数组内部进行交换，只需要常数级别的额外空间（用于存储最小值的索引和临时交换变量）。所以是 O(1)，属于原地排序。

稳定性：

选择排序是不稳定的排序算法。
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n – 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换找到的最小元素和第一个未排序元素
if (minIndex != i) { // 小小的优化，避免不必要的交换
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}

}
}
}