计算机 排序算法 1 sinsna Read more posts by this author. sinsna 24 Sep 2022 • 3 min read 一、冒泡排序属于交换排序,是稳定的,时间复杂度O(n2)思想:位置规则遵循前小后大,每相邻两个元素比较,如果不符合则交换位置,交换后再往后一位继续比较,直至最后一位。初始值:13,38,48,2,52,3 《比较流程》 1比2 :13,38,48,2,52,3 2比3 :13,38,48,2,52,3 3比4 :13,38,2,48,52,3 4比5 :13,38,2,48,52,3 5比6 :13,38,2,48,3,52 第一次排序结果:(13,38,2,48,3),52 1比2 :13,38,2,48,3,52 2比3 :13,2,38,48,3,52 3比4 :13,2,38,48,3,52 4比5 :13,2,38,3,48,52 5比6 :13,2,38,3,48,52 第二次排序结果:(13,2,38,3),48,52 1比2 :2,13,38,3,48,52 2比3 :2,13,38,3,48,52 3比4 :2,13,3,38,48,52 4比5 :2,13,3,38,48,52 5比6 :2,13,3,38,48,52 第三次排序结果:(2,13,3),38,48,52 1比2 :2,13,3,38,48,52 2比3 :2,3,13,38,48,52 3比4 :2,3,13,38,48,52 4比5 :2,3,13,38,48,52 5比6 :2,3,13,38,48,52 第四次排序结果:(2,3),18,38,48,52冒泡排序示例二、快速排序属于交换排序,是不稳定的,最坏时间复杂度O(n2),平均时间复杂度O(nlog2n)。初始数据越有序,排序恨不能越差,最坏情况是初始数据已经有序,用快速排序会导致最坏时间复杂度思想:根据基准进行比较,左边元素要小于基准,右边元素要大于基准,不符合就交换,排序时左边为L,右边为H,比较时要从H开始,如有交换就要切换到L比较,反复至所有数据比较完成。一次排序完成后会包含多次比较和位置交换,一次排序完成后,左边元素都小于基准,右边元素都 大于基准。示例如下初始数据:(30,29,58,40,5,10),以30为基准,由小到大排序 《比较流程》 游标6比1: 30:10,交换位置为10,29,58,40,5,30, 游标2比6:29:30,结果同上 游标3比6:58:30,交换位置为10,29,30,40,5,58 游标5比3:30:5,交换位置为10,29,5,40,30,58 游标4比5:40:30,交换位置为10,29,5,30,40,58 第一次排序结果:10,29,5,30,40,58, 以30为分割为[10,29,5],30,[40,58],此次只排10,29,5,以10为基准 游标3比1:10:5,交换位置为:5,29,10 游标2比3:29:10,交换位置为:5,10,29 第二次排序结果:[5,10,29] 以30为分割线要排序40,58了,以第一位40为基准 游标1比2:40:58,位置不变 第三次排序结果:40:58 至此,已经获取所有的排序结果[5,10,29],30,[40,58] 快速排序示例