排序(上):冒泡排序、插入排序、选择排序

  • A+
所属分类:算法与数据结构

排序(上):冒泡排序、插入排序、选择排序

基本准备

复杂度与稳定性

对于排序算法我们要考虑其时间复杂度、空间复杂度和稳定性。

时间复杂度:最好、最坏、平均。

空间复杂度:是否需要额外的空间。原地排序是指空间复杂度为O(1)排序算法

稳定性:稳定排序算法、不稳定排序算法。如果有相等的元素,排序后,他们前后的顺序是否与排序前相同。因为在实际项目中,一个元素通常有多种属性,在按照一种属性进行排序后,不要影响其他属性的顺序。

有序度、逆序度

有序度:满足a[i] < a[j], i < j的元素对的个数。

[2, 4, 3, 1, 5]的有序度为 6 即(2,4) (2,3) (2,5) (4,5) (3,5) (1,5)

[1, 2, 3, 4, 5]完全有序,有序度为10,称为满有序度,即n*(n-1)/2。

逆序度:满足a[i] > a[j], i < j的元素对的个数。

[2, 4, 3, 1,5]的逆序度为 4 即(2,1) (4,3) (4,1) (3,1)

逆序度=满有序度-有序度

冒泡排序

思想

从第一个元素到最后一个元素之前的一个元素,按顺序都与其后一个相邻的元素进行比较,若其大于后面相邻的元素,则进行交换,是否交换,不影响比较的进行。此为一次遍历,每次遍历都会找到最大的并放在数组的末尾(相对的最大的,第一次是最大的,第二次是次大的,第三次是次次大的),因此最多遍历n次即完成排序。

代码

 

复杂度分析

最好时间复杂度O(n),最坏时间复杂度为O(n^2),平均时间复杂度为O(n^2)

空间复杂度为O(1)

是稳定排序算法。注意在编写代码时,只有在大于时才交换,等于时不交换。

插入排序

思想

将数组中的数据分为两个区间,已排序区间和未排序区间,从未排序区间中取一个元素,与已排序区间中的元素进行比较,在合适的位置插入(将大于此元素的元素依次向后移动)。

代码

复杂度分析

最好时间复杂度O(n),最坏时间复杂度为O(n^2),平均时间复杂度为O(n^2)

空间复杂度为O(1)

是稳定排序算法。注意代码中元素移动的条件。

选择排序

跟插入排序类似,在未排序区间中选择最小的元素插入已排序区间最后(即与已排序区间后的相邻的元素交换)。

复杂度分析

最好时间复杂度O(n^2),最坏时间复杂度为O(n^2),平均时间复杂度为O(n^2)。

空间复杂度为O(1)

不稳定的排序算法。例子:5 8 5 2 9,当2和第一个5交换时,两个5的位置互换了。

冒泡排序与插入排序的比较

插入排序要快于冒泡排序,虽然时间复杂度相同,但在元素交换时,冒泡排序需要3次赋值操作,插入排序只需一次。

链表

如果需要排序的数据装在链表中的。

冒泡排序:交换过程更加复杂。

插入排序:不需要移动,找到位置后,直接插入。

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: