[Python] 算法心得—排序

1. 冒泡排序

正如其名，不断地将最大/小的数冒泡上来，其时间复杂度为O(N^2)，具体实现代码如下：

def bubble_sort(my_list):
    circle_num = len(my_list) - 1

    for i in range(circle_num):
        for j in range(circle_num - i):
            if my_list[j] > my_list[j + 1]:
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]
    return my_list

2. 选择排序

与冒泡排序有些类似，使用选择排序每次都会得出当前列表中的最大值。比如有一个列表[3,2,4,1,5]，第一次会选出最大值5，随后在[3,2,4,1]中再次选择最大值4，随后在[3,2,1]中选出3......将每次选出的最大值进行组合，得到的就是排序后的结果。

def selection_sort(my_list):
    for i in range(0, len(my_list) - 1):
        index = i
        for j in range(i + 1, len(my_list)):
            if my_list[index] > my_list[j]:
                index = j
        my_list[i], my_list[index] = my_list[index], my_list[i]
    return my_list

3. 插入排序

插入排序有些类似理扑克牌的过程。假设桌上有一堆牌，首先我们拿一张在手上（假设是3），随后再从桌上挑一张牌理到手上（假设是2），那么此时手上的牌就是[2,3]。总之，需要保证手上的牌是排过序的，这样当桌上的牌拿完时，手上的牌就是排序完的"列表"。

所以我们可以构建一个新的空数组A，从需要排列的数组中取数插入A中，其时间复杂度依旧是O(N^2)，代码如下：

def insert_sort(my_list):
    for i in range(1, len(my_list)):
        cur = my_list[i]
        for j in range(0, i):
            if my_list[i] < my_list[j]:
                my_list = my_list[:i] + my_list[i+1:]
                my_list.insert(j, cur)
    return my_list

4. 快速排序

快速排序是很多标准库里的排序方法，其平均时间复杂度为O(N * LogN)(最差为O(N ^2))。

举一个栗子，有个列表为[33,10,15,7]，我们首先取出33并称其为基准值，随后将列表剩余元素小于33的放在其左边，大于33的放在其右边，得到列表[10,15,7,33]。

随后我们对33左边的子列表再次进行上述操作，取10为基准值，得到列表[7,10,15]，由于此时基准值左右均只有一个元素，排序完毕，得到排序完的列表[7,10,15,33]。

由于待排序的列表是无序的，所以我们无论用哪个值作为基准值理论上效果都是一样的，假设我们运气不好，恰好取了最小/大值作为基准值，如下图：

那么我们将进行O(N^2)时间的运行，如果运气好取了中值呢？

此时需要进行O(N*logN)时间的运算。

代码实现：

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

        return quick_sort(less) + [pivot] + quick_sort(greater)

5. 归并排序

归并排序是典型的使用分治思想的排序方法，首先我们来看一下如何"并"?

给定两个已排序的数组A[1,3,5,6]和B[2,4,7,8]，要求将其合并为一个已排序的数组。

首先我们比较A[0]和B[0]，将小的数A[0]放入一个新的数组R=[1]；

接着A的指针向后移一位，B的指针保持，比较A[1]和B[0]，将B[0]放入R，R=[1,2]；

比较A[1]和B[1]，R=[1,2,3]； 比较A[2]和B[1]，R=[1,2,3,4]；比较A[2]和B[2]，R=[1,2,3,4,5]；比较A[3]和B[2]，R=[1,2,3,4,5,6]，此时A的指针已经到了最后，但B还指向B[2]的位置，这时候我们需要将B[2]后的元素全部插入R尾部，得到R=[1,2,3,4,5,6,7,8]即为归并后排序完成的列表。

具体代码如下：

def merge_sorted_array(A, B):
    sorted_array = []
    l = 0
    r = 0
    while l < len(A) and r < len(B):
        if A[l] < B[r]:
            sorted_array.append(A[l])
            l += 1
        else:
            sorted_array.append(B[r])
            r += 1
    sorted_array += A[l:]
    sorted_array += B[r:]
    return sorted_array

了解了"并"后我们来看一下如何进行"分": 这就简单了，可以直接从中间二分，直到每个数组只有一个元素为止，完整的归并排序的代码如下：

class Sort:
    def mergesort(self, alist):
        if len(alist) <= 1:
            return alist
        mid = len(alist) // 2
        # 分
        left = self.mergesort(alist[:mid])
        right = self.mergesort(alist[mid:])
        # 合
        return Sort._merge_sorted_array(left, right)

    @staticmethod
    def _merge_sorted_array(A, B):
        sorted_array = []
        l = 0
        r = 0
        while l < len(A) and r < len(B):
            if A[l] < B[r]:
                sorted_array.append(A[l])
                l += 1
            else:
                sorted_array.append(B[r])
                r += 1
        sorted_array += A[l:]
        sorted_array += B[r:]
        return sorted_array

6. 希尔排序

希尔排序是使用插入排序的更高效的排序。

假定一个数组A[44，12，59，36，62，43，94，7，35，52，85]，该数组的长度为11，我们设定第一个增量值11//2=5，取A[0],A[5],A[10] (每个相隔5个距离)，然后我们仅对这三个数进行插入排序，A=[43, *, *, *, *, 44, *, *, *, *, 85]（*位置不进行任何操作）；

随后我们设定增量值为5//2=3，取A[0],A[3],A[6],A[9]排序，A=[35, 12, 7, 43, 52, 36, 62, 59, 44, 94, 85]；

最后用增量值1对序列进行插入排序，但经过前两次排序，此次排序的时间效率提高了很多，具体代码如下：

def shell_sort(my_list):
    length = len(my_list)
    step = length // 2
    while step > 0:
        for i in range(step):
            list = [my_list[x] for x in range(i, length, step)]
            list = insert_sort(list)
            for x in range(len(list)):
                my_list[x * step + i] = list[x]

        step = step // 2
    return my_list

参考资料