o(logn^2)的冒泡、插入、选择排序
2020-06-27 本文已影响0人
isLJli
最常见的排序算法时间复杂度的比较:

时间复杂度
如何衡量一个排序算法的指标
1.执行效率:
包括最好、最坏、平均的时间复杂度。
时间复杂度的系数、常数、低阶
2.内存消耗
就是空间复杂度
3.稳定性
对于排序后的相等的数据,其位置还是跟排序之前的一样。
o(n^2)的:插入排序、冒泡排序、选择排序
冒泡排序
冒泡排序,是相邻两个元素的对比交换。这里的代码加入一个判断当前的排序是否是有序的,如果是有序的就不用在往下比较了。那样的话最好的时间复杂度是o(n),最坏的时间复杂度是o(n^2),对于平均时间复杂度 n*(n-1)/4,就是 O(n2)。空间复杂度是o(1),是稳定排序。
通俗的讲:就是每次都比较相邻的两个数值,每次都找到一个最大或最小值。

冒泡排序

流程图
插入排序
插入排序,分为排序好和未排序好两部分,就是将前面的元素先排序好,在将当前元素与前面的元素逐个比较,找到合适的位置。最好的时间复杂度是o(n)(从尾元素开始遍历),最坏的时间复杂度是o(n2),平均复杂度是o(n2),空间复杂度是o(1),稳定排序
通俗的讲:就是开始就将前面(0和1开始)开始排序好,然后将下一个还未排序的位置元素,从离它最近的位置开始比较,如果比他大的排序好的元素全部向上移动一位,直到找到一个元素比它小,那么这个比他小的元素的上一位就是它的位置。

插入排序

流程图
选择排序
选择排序是将一组数据中最小或最大的数值,然后排在相关的位置。其最好、最坏、平均时间复杂度都是o(n^2),空间复杂度是o(1),不是稳定排序。

选择排序

流程图
适合大规模的o(nlogn):归并排序、快速排序