冒泡排序快速排序归并排序堆排序的时间复杂度(冒泡排序和简单排序)
导语：冒泡排序、快速排序、归并排序、基数排序 | 排序算法（二）
上一部分讲了
排序的分类与插入类排序（直接插入排序、希尔排序）、选择类排序（简单选择排序、堆排序）
点这里看上一部分
如果觉得有帮助的话，可以转发点赞支持一下哦！
冒泡排序思想：
1.相邻元素俩俩比较，小的在前、大的在后。（这时按从小到大排序时，从大到小排序时相反）
2.重复这个步骤 n 次。（n为序列的长度，实际上比较的次数可能比n小，可以设置一个判断（该轮没有元素交换时排序完成）来优化冒泡排序）
3.俩俩比较时，不是位置 1 和 2、3和4 比较。 而是！！！，1 和 2 位置元素比较完后，比较 2和3位置的元素，一直到n - 1与 n 位置的元素比较。
如
{9、5、4、3、2、1}
第一次交换：
先判断 9 与 5 ，9比5大，交换 {5、9、4、3、2、1}
判断9与4，9比4大，交换{5、4、9、3、2、1}
重复，一直到最后两个位置比较....
可以知道，第一次交换后，9被挪到了最后位置：{5、4、3、2、1、9}
第二次交换
5被挪到了1的位置。
{4、3、2、1、5、9}
....
像这样重复n次后，将得到{1、2、3、4、5、9}
（从上面我们也可以知道，与我们需要的次序正好完全相反时，冒泡排序必须要执行n次，此时冒泡排序的效率最低）
快速排序思想：
主要用到分治思想。
1.在该序列中，选择一个数（处于中间的数（mid = （ l + r ）/ 2 ）。把序列中比它小的放在它左边，把序列中比它大的放在右边。
2.根据分治思想，我们知道，现在的步骤可以使该序列有序。那么对它（mid）左边的序列中也执行这个步骤，对它（mid）右边的序列中也执行这个步骤。
3.这样后整个序列都有序。
排序步骤：
要怎么快速地执行上述（1）中的操作呢？
可以用一个递归函数 套 循环来实现。
现在排序（序列头位置为l，序列尾位置为r的序列）{ 找到中间位置元素mid while（元素A的位置小于元素B的位置（相当于序列还未遍历完））{ 从左到右找到 第一个比mid大的元素A 从右到左找到 第一个比mid小的元素B if（元素A的位置小于元素B的位置）{ 交换元素A与元素B } } if（元素A的位置小于元素mid的位置） 现在排序（A的位置，mid的位置） if（元素B的位置大于元素mid的位置） 现在排序（mid的位置，B的位置) 如序列{9、5、4、3、2、1}
中间位置元素是
4
9是第一个比4大的左边元素
1是第一个比4小的右边元素
交换
{1、5、4、3、2、9}
再继续，5与2互换
{1、2、4、3、5、9}
再交换
{1、2、3、4、5、9}
排序完成
归并排序思想：
1.先拆分、后合并。
2.把俩个及以上的有序子表，二路合并到一个新的有序序列。
如
{5，9，6，3，4，2}
先拆分到最小：
{5} {9} {6} {3} {4} {2}
然后俩俩合并，并保证合并后有序
{5，9}、{3，6}、{2，4}
再俩俩合并（如果是奇数可以先保留最后一组不合并）
{3，5，6，9} {2，4}
再合并
{2，3，4，5，6，9}
排序过程：
最重要的就是合并过程：
如有两个有序序列AB，如何把他们合并到序列C呢？
下面是伪代码：
用 i 来遍历 A，j 来遍历 Bwhile( i 未遍历完 A 且 j 未遍历完 B){ if( A[ i ] 比 B [ j ] 小 ) { 把 A[ i ] 放入 序列 C中。 i++ // i 后移 } else{ 把 B[ j ] 放入 序列 C中。 j++ // j 后移 }}while(i 未遍历完 A ){ 把 A[ i ] 放入 序列 C中。 i++ }//当有一个已经遍历完后，把另一个序列剩下的直接存入序列Cwhile(j 未遍历完 B ){ 把 B[ j ] 放入 序列 C中。 j++ }思路：
比较新奇，是按照数字每个位置的数来排序。（时候于）
并且需要有10个编号为0到9的不定长容器（容量大于n的数组也可以）
1.先取出每个数的个位数（为什么不是从最高位开始？因为如果有某个数的位数远远超过其他数，那么会从最高位开始会浪费很多时间）
2.从第一个数开始到最后一个数，把对应的数放到编号为个位数的容器里。（同一个容器中时，按照先进的在前面的顺序）
3.然后取出每个数的十位数，按照容器的编号0到9顺序取出每个数，重新把对应的数放到编号为十位数的容器里。
4.一直取，直到容器内元素无变化，或者取到最高位。
排序步骤：
如，序列{135，242，192，93，345，11，24，19}
先取个位，依次放入对应容器里。（同一个容器中时，按照先进的在前面的顺序）
再取十位，下面是根据容器顺序，重新排序后的序列。
再取百位，下面是根据容器顺序，重新排序后的序列。
最后根据容器的顺序，得到排好后的序列。
本文内容由小涵整理编辑！