模板做网站影响seo,在线自动翻译整个网页,浙江建设信息港官网证书查询,企业网站icp是什么一、什么是冒泡排序 冒泡排序#xff08;Bubble sort#xff09;是一种简单的排序算法#xff0c;其基本思想是通过相邻元素的比较和交换#xff0c;将较大的元素逐渐交换到序列的一端#xff0c;从而达到排序的目的。 具体步骤如下#xff1a; 从序列的第一个元素开始Bubble sort是一种简单的排序算法其基本思想是通过相邻元素的比较和交换将较大的元素逐渐交换到序列的一端从而达到排序的目的。 具体步骤如下 从序列的第一个元素开始依次比较相邻的两个元素。如果它们的顺序不正确比如当前元素大于下一个元素则进行交换将较大的元素向序列的末尾移动。继续向后遍历序列重复进行相邻元素的比较和交换操作直到完成一轮遍历。重复上述步骤直到序列排序完成即没有发生任何元素交换的情况。 冒泡排序的一轮遍历会使至少一个元素移动到正确的位置经过n-1轮的遍历n为序列长度即可完成排序。冒泡排序的时间复杂度为O(n^2)。 冒泡排序虽然简单易懂但对于大规模的数据排序效率较低不适用于处理大量数据的情况。然而对于小规模的数据或者部分有序的序列冒泡排序仍有一定的实际应用价值。 二、代码实现
注意本代码已效率优化经过优化冒泡排序的最差平均时间复杂度仍为 O(n^2)但当输入数组完全有序时可达到最佳时间复杂度 O(n)。
public static void BubbleSort(int[] nums){int size nums.length;// 外循环未排序区间为 [0, i]for(int i size - 1 ; i 0 ; i--){// 记录交换元素boolean flag false;// 内循环将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for(int j 0 ; j i ; j){if(nums[j] nums[j1]){// 记录交换元素flag true;// 交换 nums[j] 与 nums[j 1]int tmp nums[j];nums[j] nums[j1];nums[j1] tmp;}}if (flag false){// 此轮冒泡未交换任何元素直接跳出return ;}}}
三、算法特性 时间复杂度 O(n^2)各轮冒泡遍历的数组长度依次为 n−1、n−2、…、2、1 总和为 (n−1)n/2 。在引入flag优化后最佳时间复杂度可达到 O(n) 。 空间复杂度O(1)。 稳定排序由于冒泡排序遇到相等的元素不交换因此是稳定排序。
