常用排序算法

1.基本的排序算法

冒泡排序( Bubble Sort)
插入排序(Insertion Sort)

2.常考的排序算法

归并排序( Merge Sort )
快速排序(Quick Sort )
拓扑排序(Topological Sort)

3.其他排序算法

堆排序(Heap Sort)
桶排序(Bucket Sort)

注意：

1,冒泡排序和插入排序是最基础的,面试官有时候喜欢拿它们来考察你的基础知识,并且看看你能不能快速地写出没有bug的代码。
2.归并排序、快速排序和拓扑排序的思想是解决绝大部分涉及排序问题的关键,我们将在这节课里重点介绍它们。
3·桶排序,在一定的场合中(例如知道所有元素出现的范围时),能在线性的时间复杂度里解决战斗,掌握好它的解题思想能开阔解题思路。

一、冒泡排序( Bubble Sort)

基本思想

给定一个数组,我们把数组里的元素通通倒入到水池中,这些元素将通过相互之间的比较,按照大小顺序一个一个地像气泡一样浮出水面。

实现

每一轮,从杂乱无章的数组头部开始,每两个元素比较大小并进行交换,直到这一轮当中最大或最小的元素被放置在数组的尾部,然后不断地重复这个过程,直到所有元素都排好位置。其中,核心操作就是元素相互比较。

算法分析

空间复杂度

假设数组的元素个数是n,由于在整个排序的过程中,我们是直接在给定的数组里面进行元素的两两交换,所以空间复杂度是0(1)。

时间复杂度

1.给定的数组按照顺序已经排好在这种情况下,我们只需要进行n-1次的比较,两两交换次数为0,时间复杂度是O(n)。这是最好的情况。
2.给定的数组按照逆序排列在这种情况下,我们需要进行n(n-1)/2次比较,时间复杂度是O(n2)。这是最坏的情况。
3,给定的数组杂乱无章在这种情况下,平均时间复杂度是O(n2)。由此可见,冒泡排序的时间复杂度是O(n2)。它是一种稳定的排序算法。(稳定是指如果数组里两个相等的数,那么排序前后这两个相等的数的相对位置保持不变。)