公司网站设计 优帮云,开发公司宣传语,域名代备案,wordpress 页面标题首先需要你对排序算法的评价维度和一个理想排序算法应该是什么样的有一个基本的认知#xff1a; 《Hello算法之排序算法》
主要内容来自#xff1a;Hello算法11.3 冒泡排序
我觉得冒泡排序非常有意思#xff0c;也非常简单#xff0c;就是不停地交换相邻的元素即可#…首先需要你对排序算法的评价维度和一个理想排序算法应该是什么样的有一个基本的认知 《Hello算法之排序算法》
主要内容来自Hello算法11.3 冒泡排序
我觉得冒泡排序非常有意思也非常简单就是不停地交换相邻的元素即可最大的元素一直横冲直撞往右边过去。
然后我们再经过 n-1 次迭代即可找出顺序规律。
单次循环的流程可以看原文的图片冒泡排序
对于冒泡排序需要重点掌握的还是效率优化章节。
算法流程
重点就是抓住到底要冒泡几轮然后就是我们需要把最大的元素冒到最后面去也就是说我们的未匹配元素是从0开始到n、n-1、n-2…以此类推应该如何处理
对于数组长度为 n 冒泡排序流程如下
1.首先对 n 个元素执行“冒泡” 将数组的最大元素交换到正确位置 2. 接下来对剩余 n - 1个元素执行“冒泡”将第二大元素交换到正确位置 3. 以此类推一共经过 n - 1轮“冒泡”前 n - 1 大的元素都被交换到正确位置 4. 仅剩的一个元素必定是最小元素无须排序因此数组排序完成。
//版本一
void bubbleSort(vectorint nums) {int n nums.size();while (--n) {int k 0; //记录最大元素下标这样我觉得效率更高不用频繁swapfor (int i 1; i n; i) {if (nums[i] nums[k])k i;}swap(nums[k], nums[n]);}
}//版本二
void bubbleSort(vectorint nums) {// 外循环未排序区间为 [0, i]for (int i nums.size() - 1; i 0; i--) {// 内循环将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j 0; j i; j) {if (nums[j] nums[j 1]) {// 交换 nums[j] 与 nums[j 1]// 这里使用了 std::swap() 函数swap(nums[j], nums[j 1]);}}}
}⭐️效率优化
在冒泡排序中完全有可能某轮的冒泡没有执行任何交换操作说明数组已经完成排序可以直接返回结果。
所以我们可以增加一个标志位flag来监控该情况一旦出现立即返回。
经过优化冒泡排序的最差时间复杂度和平均时间复杂度仍为 O ( n 2 ) O(n^2) O(n2)但当输入数组完全有序时可达到最佳时间复杂度 O ( n ) O(n) O(n)。
//版本一
void bubbleSort(vectorint nums) {int n nums.size();while (--n) {int k 0; //记录最大元素下标这样我觉得效率更高不用频繁swapint flag 0;for (int i 1; i n; i) {if (nums[i] nums[k]) {k i;flag;}}if (!flag)break;swap(nums[k], nums[n]);}
}
//版本二
void bubbleSortWithFlag(vectorint nums) {// 外循环未排序区间为 [0, i]for (int i nums.size() - 1; i 0; i--) {bool flag false; // 初始化标志位// 内循环将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j 0; j i; j) {if (nums[j] nums[j 1]) {// 交换 nums[j] 与 nums[j 1]// 这里使用了 std::swap() 函数swap(nums[j], nums[j 1]);flag true; // 记录交换元素}}if (!flag)break; // 此轮“冒泡”未交换任何元素直接跳出}
}算法特性
时间复杂度为 O ( n 2 ) O(n^2) O(n2)、自适应排序各轮“冒泡”遍历的数组长度依次为 n − 1 、 n − 2 、 . . . 、 2 、 1 n-1 、n-2、...、2、1 n−1、n−2、...、2、1总和为 ( n − 1 ) n 2 \frac{(n-1)n}{2} 2(n−1)n。在引入优化后最佳时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1)、原地排序稳定排序由于在“冒泡”中遇到相等元素不会进行交换。
