更多精彩内容：www.lifesmile.cn

导读

1. 如何分析一个排序算法？
2. 冒泡排序的实现与分析
3. 插入排序的实现与分析

 

1.如何分析一个排序算法：

• 时间复杂程度（执行效率）
• 空间复杂程度（内存消耗）
• 稳定性（排序后前后位置是否改变）

前两个都很容易理解，最后简单说下稳定性：假如有一串数字（1，3，5，7，9，5，2）排序后（1，2，3，5，5，7，9）如果5这个数字排序后和排序前前后顺序一样就是稳定的，反之不是稳定的。

那么稳定性有什么好处呢？比如一个双十一的订单，我们需要根据订单额进行排序，订单额相同的再根据下单时间排序。我们能轻易想到的就是先根据订单额排序，然后有订单额相同的我们再根据下单时间排序。这样是能实现的，但是要排序无数次。

如果我们用稳定性算法排序就只需要排序2次。具体实现是，先通过时间排序一次，排序完后再根据订单额排序，这样的结果就是需要的结果。时间排序完后，再根据订单额排序，因为前后顺序是不会变的，所以再根据订单额排序，实际上已经有时间排序咯。

2冒泡排序（Bubble Sort）

冒泡排序是比较相邻的两个数，如果满足条件就交换位置，一次冒泡排序会完成一个数字到达指定的位置，重复n次完成排序。

冒泡排序是可以优化的，如果一次冒泡排序中，没有一次数据交换说明排序已经完成，可以提前退出。

分析：

时间复杂：O(n^2)

空间复杂：O(1)

稳定排序：排序前后位置不变，稳定。

3插入排序(Insertion Sort)

插入排序就是一个已排区和一个未排区，初始一般是数字第一个，然后在未排区中取出一个放到已排区中的合适位置中。重复完成所有未排区的排序。

代码:

分析：

时间复杂：O(n^2)

空间复杂：O(1)

稳定排序：排序前后位置不变，稳定。

微信公众号：LifeSmile