排序算法整理(Python实现)

1. 冒泡排序

??冒泡排序(Bubble Sort)是稳定排序,其基本思想是:遍历待排序列,依次两两比较,如果顺序错误就交换。如果从头开始遍历,把较大的交换到后面,结果就是越大的数据越往下沉,所以也可以称为“下沉排序”;如果从尾开始向前遍历,把较小的交换到前面,结果就是越小的数据越往上浮,这就是“冒泡排序”名称的由来。冒泡排序比较简单,python实现如下:

def bubble_sort(array):
    length = len(array)
    for i in range(0, length):  # 这轮遍历只是表示整个排序最大需要几轮
        j = length - 1  # 这个例子从后开始遍历,演示的是“上浮冒泡排序”
        while j >= i:  # 每轮遍历只需要剩下的比较未排序的序列,前i个元素已经有序了(也就是说整个序列下标小于i的元素都已经有序)
            if array[j] < array[j-1]:
                array[j-1], array[j] = array[j], array[j-1]
            j -= 1

上面的例子是不管待排序列本身是否有序,全部遍历。而实际上待排序列可能本身就已经有序(或部分有序),这样在遍历并比较的过程中就不会交换数据。也就是说如果在某一轮的遍历过程中没有交换数据,就说明整个序列已经有序了。所以上面的代码还可以略做优化:

def optimized_bubble_sort(array):
    length = len(array)

    has_switched = True  # 是否有数据交换
    for i in range(0, length):  # 这轮遍历只是表示整个排序最大需要几轮
        # 没有数据交换,说明序列有序,退出循环,完成排序
        if has_switched is False:
            break

        has_switched = False  # 每轮比较,初始假设没有数据交换

        j = length - 1  # 这个例子从后开始遍历,演示的是“上浮冒泡排序”
        while j >= i:  # 每轮遍历只需要剩下的比较未排序的序列,前i个元素已经有序了(也就是说整个序列下标小于i的元素都已经有序)
            if array[j] < array[j-1]:
                array[j-1], array[j] = array[j], array[j-1]
                has_switched = True  # 有数据交换
            j -= 1

2. 选择排序

??选择排序(Selection Sort)是不稳定排序,它的过程为:从整个序列中找出最小的元素和第一个元素交换,然后再从剩下的序列中找出最小的和第二个元素交换...,共需重复待排序列的长度减一的次数,最终得到一个有序序列。Python实现如下:

def simple_selection_sort(array):
    length = len(array)  # 获取最后一个元素的下标

    # 需要遍历 len(array) - 1 次。因为前面的都排好序后,最后只剩一个元素,
    # 而且最后的这个元素是前面比较替换之后确定的一个元素,自然是有序的
    for i in range(length-1):
        index_min_value = i  # index_min_value 为最小元素对应的下标,假设下标为i的元素最小

        # 从剩下的元素里面找出最小的
        for j in range(i+1, length):
            if array[j] < array[index_min_value]:
                index_min_value = j

        # 如果第i个元素不是最小的,将最小元素与第i个元素交换位置
        if index_min_value != i:
            array[i], array[index_min_value] = array[index_min_value], array[i]

3. 插入排序

??插入排序(Insertion Sort)是稳定排序,它的基本操作是将一条记录插入到已经排好序的有序序列中,从而得到一个新的、记录数增1的有序序列。具体实现为:从待排序列的第二个元素开始,将当前元素抽出来插入到前面的有序序列中。第一步抽出第2个元素(它的前面就只有一个元素,可以看做是只包含一个元素的有序序列),然后将这第2个元素插入到前面的有序序列中,得到一个有两个元素的有序序列。第二步抽出第3个元素,重复第一步的操作。最后就得到一个完整的有序序列。

def insertion_sort(array):
    # i 从第2个元素开始
    for i in range(1, len(array)):
        # 第i个元素之前的序列是有序序列,这里将第i个元素插入到之前的有序序列中
        # 插入第i个元素完成后的有序序列长度会多一个,这里先将第i个元素暂存起来,空出位置
        temp_value = array[i]

        # 第i个位置已经是空位了,从第i-1个元素逆向遍历,将 temp_value 插入到合适的位置
        j = i
        while j > 0 and array[j-1] > temp_value:
            array[j] = array[j-1]  # 就是将第j-1个元素后移一个位置
            j -= 1

        # 最后第j个位置就是 temp_value 需要插入的位置
        array[j] = temp_value

4. 归并排序

??归并排序(Merge Sort)是稳定排序。归并排序采用D&C(分治,divide and conquer)策略,首先将待排序列分解成有序序列(空序列或只包含一个元素的序列可以看做是有序序列),再讲每个有序序列归并,最终得到一个完整的有序序列。

def merge_sort(array):
    if len(array) <= 1:  # 基线条件,此时的序列就是有序序列,分解的停止条件
        return array

    # 分解待排序列
    mid = len(array) // 2
    left = merge_sort(array[:mid])  # 递归调用自身,直到子序列有序,即达到上面的基线条件
    right = merge_sort(array[mid:])

    # 合并有序的子序列
    return merge(left, right)

def merge(left, right):
    """
    合并left、right,left和right均为有序序列
    """
    result = []  # 结果集
    left_course = 0  # 指向left的游标,初始指向left的第一个元素
    right_course = 0  # 指向right的游标,初始指向right的第一个元素

    # 从left的第一个元素和right的第一个元素开始对比,
    # 哪边的元素较小则将哪边的元素放入result,并将较小元素的游标往后移一位
    while left_course < len(left) and right_course < len(right):
        if left[left_course] < right[right_course]:
            result.append(left[left_course])
            left_course += 1
        else:
            result.append(right[right_course])
            right_course += 1

    if left_course == len(left):
        # 左边的游标已经指向left的最后一个元素,说明左边的元素已经全部添加到result了,直接把右边剩下的依次追加到result
        for i in right[right_course:]:
            result.append(i)
    else:
        # 否则就是右边的元素已经全部添加到result了,直接把左边剩下的依次追加到result
        for i in left[left_course:]:
            result.append(i)

    return result

5. 快速排序

??快速排序(Quick Sort)是不稳定排序。快速排序也采用了D&C策略,首先选取一个基准值,然后通过一次遍历将待排序列分成三部分(这被称为分区,partitioning):所有元素都小于或者等于基准值的一个序列less_array、基准值、所有元素都大于基准值的一个序列grater_array。这个时候对整个序列排序就很容易了:less_array + 基准值 + grater_array,对于less_array和grater_array再分别采用递归的方式进行快速排序,最后得到整个待排序列的一个有序序列。

def quick_sort(array):
    if len(array) < 2:  # 退出递归的基线条件
        return array

    pivot = array[0]  # 基准值,可随便选取

    # 分区
    less_array = [i for i in array[1:] if i <= pivot]
    grater_array = [j for j in array[1:] if j > pivot]

    #  采用一次遍历分区的方法,偶尔会报错:RecursionError: maximum recursion depth exceeded while calling a Python object
    # less_array, grater_array = [], []
    # for num in array:
    #     if num <= pivot:
    #         less_array.append(num)
    #     else:
    #         grater_array.append(num)

    return quick_sort(less_array) + [pivot] + quick_sort(grater_array)

相关推荐