标签：one   通过   ror   length   位置   直接   dex   自身   bre   

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] 

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

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] 

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] 

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) 

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)  pivot]

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

排序算法整理（Python实现）

标签：one   通过   ror   length   位置   直接   dex   自身   bre   

原文地址：https://www.cnblogs.com/lvnux/p/12770805.html