-
10个数冒泡排序流程图_五十四、最基础的冒泡排序
2021-01-15 08:53:15排序是一个非常经典的问题,它以一定的顺序对一个数组(或一个列表)中的项进行重新排序。排序算法有很多种,每个都有其自身的优点和局限性。今天我们来学习最最简单的冒泡排序算法。冒泡排序要学习冒泡排序必须知道它...「@Author: Runsen」
排序可能是所有的算法中最最基础和最最常用的了。排序是一个非常经典的问题,它以一定的顺序对一个数组(或一个列表)中的项进行重新排序。
排序算法有很多种,每个都有其自身的优点和局限性。
今天我们来学习最最简单的冒泡排序算法。
冒泡排序
要学习冒泡排序必须知道它的原理:
所谓冒泡,就是将元素两两之间进行比较,谁大就往后移动,直到将最大的元素排到最后面,接着再循环一趟,从头开始进行两两比较,而上一趟已经排好的那个元素就不用进行比较了。
下面,我们就进入代码环节。
Python实现冒泡排序 现在,我给你一个nums = [3,1,25,6,8,10,15],要求你用Python将nums实现冒泡排序。
看上去很难入手,其实很简单,我先给出代码
nums = [3,1,25,6,8,10,15]for i in range(len(nums)-1): for j in range(len(nums) - i -1): if nums[j] > nums[j+1]: nums[j],nums[j+1] = nums[j+1],nums[j] print("第"+str(j)+"次内循环"+str(nums)) print("第"+str(i)+"次外循环"+str(nums))print("最后的结果"+str(nums))
我们先遍历nums,这不就是我们的range(len(nums)-1),至于为什么是range(len(nums)-1),其实就是我们的下标从0开始的,len(nums)返回是7,range是左开右闭,但是冒泡排序,我们只需要取到nums[5] = 10 就足够了,所以这里range(len(nums)-1),取到[3,1,25,6,8,10]。
然后,我们在遍历之后的nums,比如i = 0,我们将j取值范围到len(nums) - i -1,用nums[j] > nums[j+1]判断两两的大小, 每次内循环将最大的移到最右边。
每一次内循环的目的就是将当中最大的移到最右边,而每一次外循环的目的就是当最大的移到最右边后,缩小范围,再寻找最大的数,再把它移到最右边。
我们执行上面的代码的结果如下:
第0次内循环[1, 3, 25, 6, 8, 10, 15]第1次内循环[1, 3, 25, 6, 8, 10, 15]第2次内循环[1, 3, 6, 25, 8, 10, 15]第3次内循环[1, 3, 6, 8, 25, 10, 15]第4次内循环[1, 3, 6, 8, 10, 25, 15]第5次内循环[1, 3, 6, 8, 10, 15, 25]第0次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第2次内循环[1, 3, 6, 8, 10, 15, 25]第3次内循环[1, 3, 6, 8, 10, 15, 25]第4次内循环[1, 3, 6, 8, 10, 15, 25]第1次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第2次内循环[1, 3, 6, 8, 10, 15, 25]第3次内循环[1, 3, 6, 8, 10, 15, 25]第2次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第2次内循环[1, 3, 6, 8, 10, 15, 25]第3次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第1次内循环[1, 3, 6, 8, 10, 15, 25]第4次外循环[1, 3, 6, 8, 10, 15, 25]第0次内循环[1, 3, 6, 8, 10, 15, 25]第5次外循环[1, 3, 6, 8, 10, 15, 25]最后的结果[1, 3, 6, 8, 10, 15, 25]
我们可以看到,第0次外循环,已经将25放在了最右边,第1次外循环确定把15放到最右边,这样从右往左,从大到小,这就是完整的冒泡排序。
冒泡排序的时间复杂度是:假设被排序的数列中有N个数。遍历一趟的时间复杂度是,需要遍历多少次呢?N-1次!因此,冒泡排序的时间复杂度。
冒泡排序是稳定的算法:它满足稳定算法的定义;所谓算法稳定性指的是对于一个数列中的两个相等的数a[i]=a[j],在排序前,a[i]在a[j]前面,经过排序后a[i]仍然在a[j]前,那么这个排序算法是稳定的。
下面是Java冒泡排序代码。
public class Sort { public static void sort() { Scanner input = new Scanner(System.in); int sort[] = new int[10]; int temp; System.out.println("请输入10个排序的数据:"); for (int i = 0; i
JavaScript冒泡排序代码。
function sort(arr) { for (var i = 0; i arr[j + 1]) { var temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } return arr;}//举例如下var arr = sort([1, 7, 4, 97, 23, 45]);console.log(arr);
❝
本文已收录 GitHub,传送门~[1] ,里面更有大厂面试完整考点,欢迎 Star。
❞
Reference
[1]
传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
-
10个数冒泡排序流程图_冒泡排序算法C++实现
2021-01-14 05:55:39十个数,实现正序排序功能。冒泡排序法#include<iostream> using namespace std; int main() { int s[10] = { 9,8,7,6,5,4,3,2,1,0 }; int i, j, temp; for (i = 0; i < 9; i++)//注意数组下标从s[0]...十个数,实现正序排序功能。
冒泡排序法
#include<iostream> using namespace std; int main() { int s[10] = { 9,8,7,6,5,4,3,2,1,0 }; int i, j, temp; for (i = 0; i < 9; i++)//注意数组下标从s[0]开始 { for (j = 0; j < 10-1-i; j++) { if (s[j] > s[j + 1]) { temp = s[j]; s[j] = s[j + 1]; s[j + 1] = temp; } } } cout << "The sort numbers:" << endl; for (i = 0; i < 10; i++) { cout << s[i] << ""; } return 0; }
- 其中i=0时: j从0开始a[0],a[1]比较大小,把其中的较大者给a[1],然后j++,a[1]和a[2]再比较,再把两者中的较大者给a[2],这样a[0],a[1],a[2]中的最大者已经交换到a[2]中,这个过程继续,直到j=10-i-1=9,这样 a[9]中的为10个数中的最大数。
- 然后i=1时: 由于最大数已找到并放到a[9]中,所以这一次循环j最大只需到10-i-1=8,即a[8]即可,再次从j=0开始a[j]和a[j+1]两两比较交换,最后次大数放到a[8]中
- 然后i++,继续...
- 当i=9时已经过9次两两比较完成所有排序,i<9不再成立退出比较。
图解 对于n个数,只需要进行n-1次外循环的两两比较就完成排序。
至于按降序排列只需将if(a[j]>a[j+1])改为if(a[j]<a[j+1])即可。
-
[排序/C++]6. 基数排序
2020-08-17 22:45:03数字是有范围的,均由0-9这十个数字组成,则只需设置十个箱子,相继按个、十、百…进行排序。 注: 算法思路及详细过程可参考后续的示例和代码及代码流程图! 6.1.2 算法示例 6.1.3 算法代码 //基数排序算法 void...6. 基数排序
也叫桶排序或箱排序
6.1.1 算法分析和思路
-
基本思想:
分配+收集- 分配:设置若干个箱子,将关键字为k的记录放入第k个箱子;
- 收集:按序号将非空的连接。
-
数字是有范围的,均由0-9这十个数字组成,则只需设置十个箱子,相继按个、十、百…进行排序。
注:
算法思路及详细过程可参考后续的示例和代码及代码流程图!6.1.2 算法示例
6.1.3 算法代码
//基数排序算法 void RadixSort(SqList &L){ int len = L.length; int maxBitNum = MaxBitNum(L);//获取数据的最大位数 int *count = new int[10];//计数器,关键字取值范围10个值:0~9 ReadType *tempNums = new ReadType[len];//新建辅助数组tempNums int radix = 1;//基数初始为1,即表示个位 int i, j; int k; //进行maxBitNum次排序 for(i = 1; i <= maxBitNum; i++){ //每次分配前清空计数器 for(j = 0; j < 10; j++){ count[j] = 0; } //统计每个桶中的记录数 for(j = 1; j <= len; j++){//有哨兵位,索引从1开始 k = (L.nums[j].key / radix) % 10; count[k]++; } //将tempNum中的位置依次分给每一个桶 for(j = 1; j < 10; j++){ count[j] = count[j-1] + count[j]; } //将所有桶中记录依次收集到tempNum中 for(j = len; j >= 1; j--){//有哨兵位,索引从1开始 k = (L.nums[j].key / radix) % 10; tempNums[count[k] - 1] = L.nums[j]; count[k]--; } //将临时数组中的值复制到L.nums[]中 for(j = 0; j < len; j++){ L.nums[j+1] = tempNums[j]; } radix *= 10; } } //辅助函数,求关键字个数,即求数据的最大位数 //先求出最大数,再求出其位数 int MaxBitNum(SqList &L){ KeyType maxData = L.nums[1].key; //先求出最大数 for(int i = 2; i<= L.length; i++){ if(L.nums[i].key > maxData){ maxData = L.nums[i].key; } } //再求出最大位数,即最大数的位数 int maxBitNum = 1; while(maxData >= 10){ maxData /= 10; maxBitNum++; } return maxBitNum; }
- 代码流程图:
6.1.4 算法性能分析
- 时间复杂度:
- k:关键字个数,决定了需要分配多少趟;
- m:关键字取值范围为m个值。桶的个数,有多少个桶,收集时就要收集多少次;
- n:分配时,每趟要往桶里扔多少个元素。
- 每一趟都需要扔n个,收m次,总共需要k趟
- 空间复杂度:
- 是一种稳定的排序方法
-
-
手写算法并记住它:基数排序
2019-09-26 15:11:44位,是进位的位,比如十进制数的基数是10,就可以按照个十百千万等位来排序。 上图演示了基数排序算法的总体流程。先按个位从小到大排序,然后再按十位、百位排序。只要排序算法是稳定的,那么最后整体就是有序的.....对于经典算法,你是否也遇到这样的情形:学时觉得很清楚,可过阵子就忘了?
本系列文章就尝试解决这个问题。
研读那些排序算法,细品它们的名字,其实都很贴切。
比如基数排序,就是按照数字的“位”来排序。
位,是进位的位,比如十进制数的基数是10,就可以按照个十百千万等位来排序。
上图演示了基数排序算法的总体流程。先按个位从小到大排序,然后再按十位、百位排序。只要排序算法是稳定的,那么最后整体就是有序的。为了方便看出数字的每一位具体是多少,这里对位数少的数字进行了左边补0。可见该算法的核心在于选择的排序算法是稳定的。
排序是稳定的意思说,排序后,其相同元素的相对顺序并不会改变。比如19和18,按个位排,9大于8,因而顺序是18、19。二者十位上的数值相等(都为1),如果此时排十位的算法是不稳定的话,会可能出现19在前,18在后这样的情形,那么之前先按个位排序的意义将不复存在了。
了解了整体原理后,我们来一步步写出它。
首先,如何判断数字最长有多少位?遍历一遍就能解决:
let array = [666, 520, 36, 49, 9, 600, 8, 502, 998, 32] let maxLength = 0 for (let v of array) { let length = String(v).length if (length > maxLength) { maxLength = length } } console.log(maxLength) // 3 复制代码
这里我们取巧,通过转化为字符串,来获取每个数字的位数。也可以通过,找到最大数,用它不断除以10来获取位数。
另一个问题是:如何获取数字某位上的数字呢?
比如获取36的百位上的数字,通过转字符串后,补0取第一位:
String(36).padStart(maxLength, '0')[0] // 0 复制代码
有了上述铺垫后,整体逻辑就有了:
for (i = 0; i < maxLength; i++) { array = sort(array, i) console.log(array) } 复制代码
对数组排序三次,每一次的输出作为下一次的输入。其中sort方法只要是稳定的排序算法即可。
这里推荐使用桶排序算法,下面我们简单过一遍。
由于个位上的数值范围是从0到9,需要构建10个桶:
let buckets = [] for (let i = 0; i < 10; i++) { buckets.push([]) } 复制代码
然后把按个位上的数值把元素分别分到这些桶里:
for (let v of array) { let pad = String(v).padStart(maxLength, '0') let num = pad[maxLength -1] buckets[num].push(v) } console.log(buckets) // [ [ 520, 600 ], [], [ 502, 32 ], [], [], [], [ 666, 36 ], [], [ 8, 998 ], [ 49, 9 ] ] 复制代码
因为桶的区间大小特殊(为1),因此桶内部不需再排(有点计数排序的意味)。直接按顺序输出每个桶的元素即可:
let result = [] for (let bucket of buckets) { result.push(...bucket) } console.log(result) // [ 520, 600, 502, 32, 666, 36, 8, 998, 49, 9 ] 复制代码
sort方法完整代码是:
function sort(array, index) { let buckets = [] for (let i = 0; i < 10; i++) { buckets.push([]) } for (let v of array) { let pad = String(v).padStart(maxLength, '0') let num = pad[maxLength - 1 - index] buckets[num].push(v) } let result = [] for (let bucket of buckets) { result.push(...bucket) } return result } 复制代码
至此,基数排序原理和实现已经说完了。查看完整代码:codepen。
需要补充的是,基数排序也有从高位开始遍历的。另外,用它也可以轻松实现字典排序。
这里总结一下,基数排序的性能,取决于内部排序算法的选择。如果使用桶排序,时间复杂度为O(k*n),其中k为最大元素的位数,一般都是很小数。
基数排序,要做到能分分钟手写出来,是需要掌握其排序原理的。核心是使用稳定排序从低位逐次排列到高位,一旦理解就容易写出来,不需要死记硬背的。
希望有所帮助,本文完。
服务推荐
-
用汇编语言实现冒泡排序——基于MIPS指令系统
2017-04-06 09:03:11欢迎访问我的个人博客:Talk is cheap. Show me the code!。我相信会有所收获的。...冒泡排序流程图 C语言实现冒泡排序 void swap(int a[], int k) { int temp; temp = a[k]; a[k] = a[k + 1 -
-
2020-05-29
2020-05-29 23:14:44求助:在以BUF为首址的字存储区中存放有N个有符号数,现需将它们按大到小的顺序排列序。 要求:1.画流程图2.使用冒泡排序算法3.在屏幕上显示这n个有符号数的十进制数(带正负号)及最终排序结果 ... -
PHP基础教程 是一个比较有价值的PHP新手教程!
2010-04-24 18:52:44# 十六进制数(等于十进制数的18) $a = 1.234; # 浮点数"双精度数" $a = 1.2e3; # 双精度数的指数形式 字符串 字符串可以由单引号或双引号引出的字段定义。注意不同的是被单引号引出的字符串是以字面定义的,而双... -
C#开发实战1200例(第1卷).(清华出版.王小科.王军.扫描版).part1
2016-06-16 20:55:43实例110 通过定义方法求一个数的平方 实例111 使用重载方法实现不同类型数据的计算 5.2 结构与类 实例112 通过结构计算矩形的面积 实例113 通过类继承计算梯形面积 实例114 封装类实现一个简单的计算器 实例... -
C#开发实战1200例(第1卷).(清华出版.王小科.王军.扫描版).part2
2016-06-16 20:59:52实例110 通过定义方法求一个数的平方 实例111 使用重载方法实现不同类型数据的计算 5.2 结构与类 实例112 通过结构计算矩形的面积 实例113 通过类继承计算梯形面积 实例114 封装类实现一个简单的计算器 实例... -
C#开发实战1200例(第1卷).(清华出版.王小科.王军.扫描版).part3
2016-06-16 21:02:21实例110 通过定义方法求一个数的平方 实例111 使用重载方法实现不同类型数据的计算 5.2 结构与类 实例112 通过结构计算矩形的面积 实例113 通过类继承计算梯形面积 实例114 封装类实现一个简单的计算器 实例... -
上海电机学院C语言实训答案
2012-01-22 15:28:32 程序流程图、函数说明 源程序代码清单 测试数据和测试过程记录 遇到的问题及解决方法分析 实训小结 4. 程序运行方式 构建一个简易菜单,形如: 用户通过输入数值选择所需运行的子程序,当一个子... -
进玉电极模块_v5.0_nx4.0_简体版
2013-10-29 13:24:56如:您在拆完铜公出完放电数后发现在模仁的某一处需要增加一个铜公,拆完这个铜公出这个铜公的放电数时,您不想为这个铜公单独出一张放电图纸,这时您可以用这个选项把这个铜公数增加到您上次出放电图的最后一张图纸... -
C#开发实例大全(基础卷).软件开发技术联盟(带详细书签) PDF 下载
2018-02-20 01:26:55实例110 通过定义方法求一个数的平方 133 实例111 使用重载方法实现不同类型数据的计算 135 5.2 结构与类 136 实例112 通过结构计算矩形的面积 136 实例113 通过类继承计算梯形面积 137 实例114 封装类实现一个简单... -
C#开发实战1200例(第一卷+第二卷)+源码下载地址.txt
2019-05-17 09:24:24实例110 通过定义方法求一个数的平方 133 实例111 使用重载方法实现不同类型数据的计算 135 5.2 结构与类 136 实例112 通过结构计算矩形的面积 136 实例113 通过类继承计算梯形面积 137 实例114 封装... -
Quartus_II使用教程
2012-11-26 23:20:43会发现该波形图比原波形图多出了8个信号,正好与原来波形图中的双向信号对应,只 是多了个后缀result。这正是你要总线输出信号。你可以试着去修改波形图(其实修改不了, 所以我一般随便双击一段波),会弹出对话框... -
《Android开发艺术探索》第十五章笔记 《深入理解Java虚拟机》第12章 《Java编程思想》第一章读书笔记 《Java编程思想》第二章读书笔记 Project(项目) 项目难点 第六部分 InterviewExperience(面试经验) ...
-
网趣网上购物系统时尚版V13.0
2015-09-12 16:35:34应用户强烈要求,时尚版具有商品批量添加功能,可自定义一次性添加的商品个数,可一次提交保存所有商品信息,抛弃单调、重复的工作,网趣时尚版新版脱颖而出,让您的管理工作更轻松,管理更方便! 十、订单自动... -
网趣商城ASP源码
2013-02-17 17:11:35应用户强烈要求,时尚版具有商品批量添加功能,可自定义一次性添加的商品个数,可一次提交保存所有商品信息,抛弃单调、重复的工作,网趣时尚版新版脱颖而出,让您的管理工作更轻松,管理更方便! 十、订单自动... -
javascript入门笔记
2018-05-15 15:01:07可以由0或多个参数的名称来组成,多个参数的话中间用 , 隔开 定义函数时的参数列表,都称为 "形参(形式参数)" 2、调用语法 任意合法JS位置处 函数名(参数列表); 调用函数时,所传递的参数列表,称之为"实参... -
Visual C++程序员实用大全(精华版).(水利水电.邓劲生.张晓明译).part3
2016-06-21 20:50:39200 示例:求一个数的平方 第十九章 C/C++中的字符串 201 理解字符变量类型 202 理解C和C++语言存储字符串的方式 203 理解NUL字符(\0) 204 理解和使用字符串指针 205 获取字符串的大小 第二十章 声明字符串 206 ... -
千里马酒店前台管理系统V7使用手册
2011-06-16 14:09:38酒店前台管理是一个流程复杂、实时性强的系统,是酒店的标志性的关键核心业务。前台管理的水平,决定了整个酒店管理系统的水平。因此,前台管理系统是千里马酒店管理系统的核心系统。 通常房务管理(Room Division... -
Visual C++程序员实用大全(精华版).(水利水电.邓劲生.张晓明译).part4
2016-06-21 21:13:27200 示例:求一个数的平方 第十九章 C/C++中的字符串 201 理解字符变量类型 202 理解C和C++语言存储字符串的方式 203 理解NUL字符(\0) 204 理解和使用字符串指针 205 获取字符串的大小 第二十章 声明字符串 206 ... -
Visual C++程序员实用大全(精华版).(水利水电.邓劲生.张晓明译).part1
2016-06-21 21:05:54200 示例:求一个数的平方 第十九章 C/C++中的字符串 201 理解字符变量类型 202 理解C和C++语言存储字符串的方式 203 理解NUL字符(\0) 204 理解和使用字符串指针 205 获取字符串的大小 第二十章 声明字符串 206 ... -
Visual C++程序员实用大全(精华版).(水利水电.邓劲生.张晓明译).part2
2016-06-21 21:09:54200 示例:求一个数的平方 第十九章 C/C++中的字符串 201 理解字符变量类型 202 理解C和C++语言存储字符串的方式 203 理解NUL字符(\0) 204 理解和使用字符串指针 205 获取字符串的大小 第二十章 声明字符串 206 ... -
谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar
2013-06-13 22:35:212.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 ... -
软件工程教程
2012-07-06 23:10:29过去数十种面向对象的建模语言各自为战,而UML可以消除一些潜在差异,一统江湖 通过统一语义和符号表示,提高面向对象技术 使项目建立在一个成熟的标准建模语言基础之上 便于沟通和交流,统一的理解 UML主要内容 ...
-
java bcd转二进制_实训汇编语言设计——将bcd码转化为二进制数
-
idea java文件乱码_idea生成class文件乱码
-
腾讯研究院-未来经济白皮书2021:数实共生.zip
-
PrintServer.rar
-
java jnlp applet_通过chrome中的jnlp启动applet的问题
-
华为机试 完全数
-
Mysql数据库面试直通车
-
java 枚举的本质_《Java编程的逻辑》笔记22--枚举的本质
-
基于Flink+Hudi构建企业亿级云上实时数据湖教程(PC、移动、小
-
java 定义变量时 赋值与不赋值_探究Java中基本类型和部分包装类在声明变量时不赋值的情况下java给他们的默认赋值...
-
Unity RUST 逆向安全开发
-
基于SSM实现的房屋租赁系统【附源码】(毕设)
-
NeatDM_setup.exe
-
不同的Python实现方式的区别
-
MySQL 管理利器 mysql-utilities
-
财务小管家 - 2016.7z
-
第5章 PROFIBUS网络.pdf
-
华为1+X——网络系统建设与运维(中级)
-
Hi3520DV400.rar
-
使用 Linux 平台充当 Router 路由器