002-数据结构与算法-常见排序算法

如何分析一个排序算法

判断一个排序是否符合需求,可以从执行效率、占用内存、稳定性三个方面分析。

执行效率

首先看这个算法的时间复杂度,复杂度越低越好。复杂度相同的情况下,还要具体分析复杂度系数、常数、低阶部分。

占用内存

分析这个算法的空间复杂度,其中复杂度为O(1)的算法又被成为原地排序算法,是要优先考虑的。

稳定性

稳定性是指,相同的数据再排序前后,其相对位置是否会发生改变。例如下面的数据:

3,2,6,2,1

这里面有两个2,我们将第一个2记为2(1),第二2记为2(2)。

排序前,2(1)处于2(2)的左边,如果排序后,2(1)仍然处于2(2)的左边,那么这个算法就是一个稳定的排序算法。

稳定算法可以用在需要根据多个条件进行排序的场景中,例如订单信息中包含了下单时间和金额两个字段,需要金额排序,如果金额相同,则在根据下单时间排序。

如果是稳定的排序算法,可以先根据下单时间排序,再根据金额排序,得到最后的结果,例如下图。

如果是不稳定的排序算法,就不能这么做了,因为根据金额重新排序是,下单时间的顺序可能会乱。所以需要采用其它的方法,但是相比与稳定算法来讲,要复杂很多。

冒泡排序

原理

  • 从下标0开始,取相邻的一个数进行比较,符合条件则进行交换,否则不交换。比较完成后下标加1,重复前面的逻辑。
  • 所有元素比较完成之后,可以得到所有元素中最大/最小的数,并且将这个数放在末尾的位置。
  • 回到下标0,重复上面的逻辑。

图例:

分析

  • 时间复杂度:O(n^2)
  • 是否原地排序:是
  • 是否稳定:稳定

插入排序

原理

将元素分为已排序区未排序区,每次从未排序区取出一个元素,找到其在已排序区的位置并插入,直到所有元素都进入已排序区。

图例:

分析

  • 时间复杂度:O(n^2)
  • 是否原地排序:是
  • 是否稳定:稳定

选择排序

原理

将元素分为已排序区未排序区,每次从未排序区的所有元素中,选出最大/最小的元素,放入已排序去的末尾,直到所有元素都进入已排序区。

图例:

分析

  • 时间复杂度:O(n^2)
  • 是否原地排序:是
  • 是否稳定:稳定

归并排序

原理

将所有元素平局分成两组,然后两组内的数据分别排序,最后合并两个组,得到一个有序数组。

分组不是只有一次,而是采用分治的思想,将划分后的组继续分成更小的组,直到最后无法划分(只有1个元素)为止。

图例:

分析

  • 时间复杂度:O(nlogn)
  • 是否原地排序:否。归并算法需要额外的空间来存储分解后的元素,其空间复杂度为O(n)
  • 是否稳定:稳定

快速排序

原理

快速排序也采用了分治的思想,与归并排序自下向上排序的思路不同,快速排序是自上向下排序。

  • 假设数组下表从p到r,在p到r之间选择一个分区点pivot。
  • 遍历数组,将比分区点小的数据,放到p到分区点(q)之间的位置,将比分区点大的数据,放到分区点(q)到r之间的位置。
  • 对p到q-1和q+1到r之间的数据,重复上面的逻辑。

图示:

分析

  • 时间复杂度:O(nlogn)
  • 是否原地排序:是。 为了满足原地排序的要求,快排使用了非常巧妙的逻辑。 通过游标i把A[p…r]分成两部分,A[p…i-1]称为已处理区间,是小于pivot的数据,A[i…r]称为未处理区间,是还未进行比较的数据。 我们每次都从未处理区间取出一个元素与pivot进行比较,如果比pivot小,就将其加入到已处理区间尾部。

    图示:

  • 是否稳定:不稳定。前面的方法虽然保证了节省了快排算法的空间消耗,但是牺牲了稳定性。

快排与归并的取舍

  • 时间复杂度。两个算法的平均时间复杂度是一样的。但是归并排序非常稳定,最好和最坏都是O(nlogn),而快排在最坏情况下会退化成O(n^2)。
  • 空间复杂度。归并排序空间复杂度是O(n),快排是O(1),由于这两种算法都是应用在大量数据的场景中,因此对空间的消耗比较敏感。这也是为什么快排的应用比归并更多的原因。
  • 稳定性。归并稳定,快排不稳定。
上篇002-数据结构与算法-哈希算法
下篇002-数据结构与算法-散列表