o(logn^2)的冒泡、插入、选择排序

最常见的排序算法时间复杂度的比较：

image

时间复杂度

如何衡量一个排序算法的指标

1.执行效率：

包括最好、最坏、平均的时间复杂度。

时间复杂度的系数、常数、低阶

2.内存消耗

就是空间复杂度

3.稳定性

对于排序后的相等的数据，其位置还是跟排序之前的一样。

o(n^2)的：插入排序、冒泡排序、选择排序

冒泡排序

冒泡排序，是相邻两个元素的对比交换。这里的代码加入一个判断当前的排序是否是有序的，如果是有序的就不用在往下比较了。那样的话最好的时间复杂度是o(n)，最坏的时间复杂度是o(n^2)，对于平均时间复杂度 n*(n-1)/4，就是 O(n2)。空间复杂度是o（1）,是稳定排序。

通俗的讲:就是每次都比较相邻的两个数值，每次都找到一个最大或最小值。

image

冒泡排序

image

流程图

插入排序

插入排序，分为排序好和未排序好两部分，就是将前面的元素先排序好，在将当前元素与前面的元素逐个比较，找到合适的位置。最好的时间复杂度是o(n)(从尾元素开始遍历)，最坏的时间复杂度是o(n^{2)，平均复杂度是o(n}2),空间复杂度是o(1),稳定排序

通俗的讲:就是开始就将前面(0和1开始)开始排序好，然后将下一个还未排序的位置元素，从离它最近的位置开始比较，如果比他大的排序好的元素全部向上移动一位，直到找到一个元素比它小，那么这个比他小的元素的上一位就是它的位置。

image

插入排序

image

流程图

选择排序

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

image

选择排序

image

流程图

适合大规模的o(nlogn)：归并排序、快速排序