十大经典排序算法详解(I):冒泡排序(Bubble Sort)
最编程
2024-04-19 07:39:51
...
算法原理
冒泡排序通过多次遍历数组,比较相邻元素并交换,逐步将最大值(或最小值)"冒泡"到数组的一端。
算法描述
冒泡排序是一种简单的排序算法,它重复地遍历待排序的元素,比较相邻的两个元素,并根据需要交换它们的位置,直到整个序列排序完成。
冒泡排序的基本思想是通过相邻元素的比较和交换,将较大的元素逐渐“冒泡”到右侧,从而实现排序。具体步骤如下:
- 从序列的第一个元素开始,比较相邻的两个元素。
- 如果前一个元素大于后一个元素,则交换它们的位置。
- 继续比较下一对相邻元素,重复步骤2,直到遍历到序列的倒数第二个元素。
- 重复步骤1-3,直到没有任何一对元素需要比较和交换,即序列已经排序完成。
动画演示
代码实现
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
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;
}
}
}
算法复杂度
时间复杂度(最坏) | 时间复杂度(最好) | 时间复杂度(平均) | 空间复杂度 | 稳定性 |
---|---|---|---|---|
O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
冒泡排序的优化方式:
- 设置一个标志位,如果某一趟遍历中没有发生元素交换,则说明序列已经有序,可以提前结束排序。
public void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[i]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
- 记录每一趟遍历中最后一次发生元素交换的位置,下一趟遍历只需要比较到该位置即可,因为该位置之后的元素已经有序。
public void selectionSort(int[] arr) {
int n = arr.length;
int left = 0;
int right = n - 1;
while (left < right) {
int lastSwapIndex = left;
for (int i = left + 1; i <= right; i++) {
if (arr[i] < arr[lastSwapIndex]) {
int temp = arr[i];
arr[i] = arr[lastSwapIndex];
arr[lastSwapIndex] = temp;
lastSwapIndex = i;
}
}
right = lastSwapIndex - 1;
}
}
相关概念
• 稳定
:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
• 不稳定
:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
• 时间复杂度
:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
• 空间复杂度
:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。
下一篇: 十大经典排序法:气泡排序 | 快速排序