网站积分程序怎么建设,哪个网站做简历好,如何把广告发到网上,手机开发网站建设冒泡排序
概念 冒泡排序#xff08;Bubble Sort#xff09;是一种简单直观的排序算法#xff0c;它重复地遍历待排序序列#xff0c;一次比较两个相邻的元素#xff0c;如果它们的顺序错误就将它们交换过来。通过多次的遍历#xff0c;使得最大的元素逐渐移动到待排序序…冒泡排序
概念 冒泡排序Bubble Sort是一种简单直观的排序算法它重复地遍历待排序序列一次比较两个相邻的元素如果它们的顺序错误就将它们交换过来。通过多次的遍历使得最大的元素逐渐移动到待排序序列的最后从而实现排序。 算法思想 主要思路就是比较两个相邻的元素大小如果顺序错误与要实现的排序对比而言则将两个元素交换位置。迭代比对下去比完一趟后实现最大的数移动到最后升序或最小的数移动到最后降序将数组的序列长度减1。 按照以上的步骤进行多趟的排序最终实现数组的排序。我们那实现升序的一趟冒泡排序来进行模拟演变。 示例
如下是数组arr1 { 6 , 4 , 3 , 9 , 2 , 1 , 5 , 7 , 8 }初始状态下的图文演示 变量i存放未排序的第一个元素下标end存放着数组的个数数组最后一个元素的下标为end-1。 第一步 比较下标 i 和 i1 相邻两个元素的大小。arr1[i] arr[i1]。交换元素的顺序然后对变量 i 自加1迭代下去进行下一对的比较。 第二步 比较下标 i 和 i1 相邻两个元素的大小。arr1[i] arr[i1]。交换元素的顺序然后变量 i 自加1迭代下去进行下一对的比较。 迭代过程就是重复以上的动作。下面是后序的全部过程如下 第一趟冒泡排序完后数组中最大的元素9已经被移动到最后此时对end减1。end从原来的9变为了8。end-1 “指向” 的是下标7。此时可以数组划分为了两个序列一个是排好序的下标为8的元素另一个序列式未排好序的下标为0 ~ 7的元素。 整个数组分为两个序列前序列是未排好序的后序列是排好序的。 一趟冒泡排序排好一个元素数组中还剩8个未排序的元素那么只需要再执行七趟冒泡排序最后当变量 i 1 等于 end-1 时判断是否交换arr1[i] 和 arr[i1]然后整个数组排序完成。最后一个不用排肯定就是在最左端。 算法实现 // 冒泡排序
void BubbleSort(int* a, int n)
{// 实现代码1int end n;// 执行n-1趟冒泡排序while (end-1){// 一趟冒泡排序的实现for (int i 0; i end - 1; i){if (a[i] a[i 1]){Swap(a[i], a[i 1]);}}end--;} 实现代码2//for (int i 0; i n-1; i)//{// for (int j 0; j n - 1 -i; j)// {// if (a[j] a[j 1])// {// Swap(a[j], a[j 1]);// }// }//}}时间复杂度
O(N^2)。
计算过程为
考虑最坏的情况如对逆序的数组进行升序的排序
移动第一个元素时需要挪动n-1次
移动第二个元素时需要挪动n-2次
...
移动第n-1个元素时需要挪动1次
移动第n个元素时需要挪动0次。挪动的次数是一个公差为1的等差数列对该数列求和根据等差数列的前n项和公式求得
Snn^2/2;
即时间复杂度为O(n^2/2)又因为时间复杂度不计入系数的。
所以时间复杂度为O(n^2)。空间复杂度
O(1)。
因为是在原数组上进行排序的没有用到多余的空间所以空间复杂度为O(1)。 特性总结
1、 冒泡排序是一种非常容易理解的排序 2.、时间复杂度O(N^2) 3.、空间复杂度O(1) 4.、稳定性稳定
