校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 简单排序(冒泡、简单选择等)
题目

冒泡排序的原理?

解答

稳定,平均/最坏时间复杂度 O(n²),元素基本有序时最好时间复杂度 O(n),空间复杂度 O(1)。

比较相邻的元素,如果第一个比第二个大就进行交换,对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,每一轮排序后末尾元素都是有序的,针对 n 个元素重复以上步骤 n -1 次排序完毕。

public void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int index = 0; index < nums.length - 1 - i; index++) {
if (nums[index] > nums[index + 1])
swap(nums, index, index + 1)
}
}
}

当序列已经有序时仍会进行不必要的比较,可以设置一个标志记录是否有元素交换,如果没有直接结束比较。

public void betterBubbleSort(int[] nums) {
boolean swap;
for (int i = 0; i < nums.length - 1; i++) {
swap = true;
for (int index = 0; index < nums.length - 1 - i; index++) {
if (nums[index] > nums[index + 1]) {
swap(nums, index ,index + 1);
swap = false;
}
}
if (swap) break;
}
}
C 2条回复 评论
下雨天睡觉

大佬的文章让我受益匪浅,如痴如醉,以后的日子还希望能够得到大佬的谆谆指点

发表于 2021-09-11 10:00:00
0 0
假期

冒泡排序20

发表于 2021-02-07 23:56:40
0 0