1. 排序

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减排列起来的操作。排序是计算机内经常进行的一种操作，其目的是将一组无序的记录序列调整为有序的记录序列。

1.1 评价指标

• 时间复杂度
• 空间复杂度
• 使用场景：针对实际对节省时间和空间的不同需求，选择适用于不同场景的排序算法
• 稳定性：稳定的算法在排序过程中不会改变元素彼此之间次序

1.2 不同排序算法O(n)分类

2. 算法介绍

2.1 选择排序

python 实现

def selection_sort(num_list):
    length = len(num_list)
    if length <= 1:
        return num_list

    for j in range(length):
        # 假设第一个元素为最小元素
        min_num_index = j
        
        # 遍历未排序区域元素，以此和未排序区域的第一个元素做对比
        for i in range(j+1, length):
            if num_list[i] < num_list[min_num_index]:
                min_num_index = i
         
        # 交换位置
        num_list[min_num_index], num_list[j] = num_list[j], num_list[min_num_index]

    return num_list

2.2 插入排序

python 实现

def insertion_sort(ls):
    for i in range(0,len(ls)):
        current_index = i
        while ls[current_index - 1] > ls[current_index] and current_index - 1 >= 0:
            ls[current_index] , ls[current_index - 1] = ls[current_index - 1] , ls[current_index]
            current_index -= 1
    return ls

2.3 归并排序

python 实现

# 1.将整个数组对半分开，直到只剩一个元素
 # 2.从一个元素开始往回进行对比合并，将合并的内容暂且放在一个空列表中
 # 定义合并merge函数
def merge(L,R):
    # 将两个排过序的两个列表进行合并并排序
    # 分别用于限定L、R的数据减少情况
    i, j = 0,0
    # 用于存放L与R的合并内容
    res = []
    while i < len(L) and j < len(R):
        # 如果左边的数大于右边的数，就将左边的数先添加到res中，再继续比较（合并的R、L已经排过序）
        # 如果如果右边的数大于左边的数，就将右边的数先添加到res中，再继续比较（合并的R、L已经排过序）
        if L[i] <= R[j]:
            res.append(L[i])
            i += 1
        else:
            res.append(R[j])
            j += 1
    # 因为当 i == len(L) 或者 j == len(R)时，跳出while循环，且每次循环只处理一个列表里的内容，所以其中有一个列表内容会先全部加入res中，另一个列表还剩内容未加进res中。
    # 对未处理完的列表，直接加入res中
    res += R[j:] if i == len(L) else L[i:]
    return res

 # 定义排序merge_sort函数
def merge_sort(List):
    length = len(List)
    if length <= 1:
        return List
    else:
        mid = length//2
        left = merge_sort(List[:mid])
        right = merge_sort(List[mid:])
        return merge(left,right)

参考资料：归并排序(Python代码）

2.4 堆排序

演示动画
原理及代码可参考python实现堆排序

2.5 快速排序

演示动画

python 代码

def quicksort(array):
	if len(array) < 2:
		return array
	else:
		pivot = array[0]
		less = [i for i in array[1:] if i <= pivot]
		greater = [i for i in array[1:] if i >= pivot]
		return quicksort(less) + [pivot] + quicksort(greater)

3. 思考题

思考题1.4.1 赛跑问题（GS）

假定有25名短跑选手比赛争夺前三名，赛场上有五条赛道，一次可以有五名选手同时比赛。比赛并不计时，只看相应的名次。假设选手的发挥是稳定的，也就是说如果约翰比张三跑得快，张三比凯利跑得快，约翰一定比凯利跑得快。最少需要几次比赛才能决出前三名？（在第6章给出了这一问题的解答。（难度系数3颗星））

答：参考了计算之魂第6章给出了的解答。

1. 先进行五组比赛，决出各组名次。并令各组第一分别为A1、B1、C1、D1、E1。

2. 第六组比赛：各组第一 A1、B1、C1、D1、E1 分别进行一次比赛。假设名次为 A1、B1、C1、D1、E1 。则整体第一名为A1。
3. 第七组比赛：如下表，整体第二名必出现在 A2、B1之间；整体第三名必出现在 A2、B1、 A3、B2、C1 之间。
   A2、B1、 A3、B2、C1 之间进行第七组比赛，第一名为整体第二名，第二名为整体第三名。

思考题1.4.2 区间排序

如果有N个区间[l1,r1],[l2,r2],…,[lN,rN]，只要满足下面的条件我们就说这些区间是有序的：存在xi∈[li,ri]，其中i=1,2,…,N。
比如，[1, 4]、[2, 3]和[1.5, 2.5]是有序的，因为我们可以从这三个区间中选择1.1、2.1和2.2三个数。同时[2, 3]、[1, 4]和[1.5, 2.5]也是有序的，因为我们可以选择2.1、2.2和2.4。但是[1, 2]、[2.7, 3.5]和[1.5, 2.5]不是有序的。
对于任意一组区间，如何将它们进行排序？（难度系数3颗星)

答：该题解答参考了博客《计算之魂》思考题1.4 - Q2，内容如下：

1. 按照右端点排序;
2. 将右端点最大的区间作为头区间，讨论剩余 n -1 个区间的情况;
3. 对剩余的 n - 1 个区间按照步骤二重复，直至仅剩 4 个区间为止（也就是右端点最小的四个区间）;
4. 如果第 4 个区间不能和第 3 个区间交换，则按照上图可以得到前三个区间的情况，并递归地讨论第 4 个区间与第 5 个区间是否能交换，直至递归到最后一个区间，算法终止；
5. 如果能交换，则将第 3 个区间作为最大的区间，并可以得到 N1、N2、N4（按照右端点的相对大小排序）这三个区间的情况，并归位；
6. 讨论第 4 个区间能否与第 2 个区间交换，不能的话则返回步骤 4；
7. 能的话则返回步骤 5，直至讨论到第 4 个区间与第 1 个区间是否能交换，并返回步骤4。