算法趣解之基础排序算法（中）

说起音乐，很多人都喜欢。大多数人的手机中几乎都至少有一款音乐app，这些app除了给你提供音乐播放的功能，也在悄悄记录着你的一些个性化信息。比如：某首歌你听了多少次、听歌在什么时候等等。这些数据杂乱无章，似乎没有任何价值，但是其中却深藏着你的喜好厌恶。在当今手机用户增长缓慢（甚至增长停滞）的阶段，各大同类型的app面临着非常激烈的竞争。不抓住这些用户数据，可能就会在这场残酷的竞争中败下阵来。

如何利用这些数据来留住留住用户，提升用户在产品上的粘性呢？很多app给出了如下的答卷：

这种方案便是基于用户的行为数据构建用户的标签，依据各种标签的综合，提供个性化的服务。

回到我们的音乐软件，如何利用音乐软件记录的用户行为数据来构建用户标签呢？我们先从简单的一方面——分析你对你听过的歌曲的喜爱程度——入手，其他方面可以类比解决。

首先，我们要量化“对歌曲的喜爱程度” 这个属性。我们做如下简单的规定（实际情况可能没这么简单）：对于一首歌的喜爱程度由用户听这首歌的次数决定，次数越多，说明喜爱程度越高。其次，尝试找到该用户前几个喜欢的歌曲，对这些歌曲的属性进行分析，寻找相似性，得到综合的标签，标记给这位用户。最后，依据这些标签做相似性推荐即可。

这个流程中关键的问题之一，便是依据听歌的次数找到用户最喜欢的几首歌（其他关键性问题这里不做讨论，不能偏题）。原本的数据是无序的，为了解决这个问题，我们就需要对数据进行排序。

之前的文章中，我们已经学会了利用冒泡排序，对一个无序的序列进行排序。那么还有没有其他的排序方法呢？

当然有，且听我慢慢道来。

一种可行的方法如下：

在所有用户听过的歌曲中，选择一个听的次数最多的，放在新开辟的一个序列的第一个位置；

在剩下的歌曲中，找到次数最大的的歌曲，放在第二个位置；

···（其他以此类推，直到整个序列有序）

这种方法的流程可以这样概括：在待比较的序列中，找到最大的，依此放到有序序列的末尾。循环上述操作，直至整个序列有序。

上述方法，我们可以很容易发现，需要两倍于数据容量大小的空间（一个用于存储原始的无序序列，另一个用于保存排序后的结果），这样做，对于空间的来说，是十分浪费的。可以将使用空间进行缩减吗？当然可以。我们可以将找到的最 \(i\) 大的数据和序列中第 \(i\) 个元素交换即可。

所以，改进后的流程可以这样概括：在剩余的待比较的数中选择一个最大的数与这个剩余序列的第1 个数交换位置。循环上述操作，直至整个序列有序。

这样的“选择”“交换”的排序算法，我们称它为“选择排序”。

由于这个算法流程比较简单，我们结合代码来观察一下它的排序过程：

def find_max(lst,start):
    """
    find_max:
     寻找列表从下标start开始的后续元素中最大值的下标
    参数：
     lst：待寻找的列表
     start：开始搜索的下标
    返回：
     start下标后续元素最大值的下标
    """
    max_index = start
    max_elem = lst[max_index]
    for i in range(start + 1, len(lst)):
        if lst[i] > max_elem:
            max_index = i
            max_elem = lst[i]
    return max_index

def selection_sort(lst):
    """
    选择排序：
     将一个无序的列表变成一个从大到小的列表
    参数：
     lst：待排序的列表
    返回：
     排好序的列表
    """
    for i in range(len(lst)):
        max_index = find_max(lst,i)
        lst[i], lst[max_index] = lst[max_index], lst[i]
        print("第{}次排序结果:".format(i+1),lst)
    return lst

# 测试例子
print (selection_sort([84, 83, 88, 87, 67]))

# 输出结果
"""
第1次排序结果: [88, 83, 84, 87, 67]
第2次排序结果: [88, 87, 84, 83, 67]
第3次排序结果: [88, 87, 84, 83, 67]
第4次排序结果: [88, 87, 84, 83, 67]
第5次排序结果: [88, 87, 84, 83, 67]
[88, 87, 84, 83, 67]
"""

选择排序的排序流程在上述输出结果中已有体现，这里留给大家观察思考，我不过多分析。

在实际实现选择排序这个算法时，我没有像传统的方式一样，将“选择”和“交换”写在一个函数里面；而是将“选择”和“交换”分开，先实现“选择”（即上面代码中的 find_max函数），在排序算法中调用，然后实现交换，并循环完成排序。这样做（称作“函数嵌套”），有优有劣。一方面，可以使算法的主要函数（如本例的selection_sort）的逻辑比较清晰，容易理解（这就像你写程序时，main函数写的非常简洁，只是调用了相关函数一样）；同时，子问题模块化（如本例的find_max），方便别的地方调用。另一方面，当代码量比较庞大时，可能会存在多层函数嵌套，这对于理解完整的实现细节流程无疑增加了难度。希望大家在这一方面，自己做好权衡。

这个算法的性能如何呢？其效率不是很高，时间复杂度为 \(O ( N^{2} )\) 。具体的推算流程留给大家思考。

好了，在文章的最后，照例进行今天的总结：

排序操作其实是一种朴素的数据信息分析的手段：将无序的数据转换成有序的序列，也许就会发现潜在于数据中的价值。
选择排序算法的核心思想：在剩余的待比较的数中选择一个最大的数与这个剩余序列的第1个数交换位置。循环上述操作，直至整个序列有序（降序情况）。

P.S.升序情况也可类似实现
选择排序的时间复杂度为 \(O ( N^{2} )\)
函数嵌套作为一种实现手段，有优有劣，需要大家做好权衡