Pythonの八大排序算法（整理进行中）

1.0 归并排序

1.1 起源

归并排序1945年由约翰·冯·诺伊曼首次提出。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

1.2 分治法的基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。
递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

1.3 归并排序的基本思想

排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

1.4 代码实现

def merge(left,right):
    '''合并和排序'''
    i,j = 0,0
    res = []
    len_left,len_right = len(left),len(right)
    while i < len_left and j < len_right:
        '''逐个比较两个列表的元素，小的添加进新表大的留下继续比较'''
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    '''最后加上未比较的元素'''
    res.extend(left[i:])
    res.extend(right[j:])
    return res

def mergeSort(lists):
    '''归并排序入口，拆分列表'''
    #递归退出条件判断
    length = len(lists)
    if length <= 1:
        return lists
    #递归拆分
    mid = length // 2
    left = mergeSort(lists[:mid])
    right = mergeSort(lists[mid:])
    return merge(left,right)

if __name__ == "__main__":
    arr = [5,4,3,6,9,2,1,7,8]
    print("Before sort: ", arr)
    print("After  sort: ", mergeSort(arr))

1.5 排序结果

mergeSort.png

2.0 快速排序

2.1 起源

快速排序(quick sort)的采用了分治的策略。由图灵奖得主C. A. R. Hoare(托尼·霍尔)在1962年提出。

2.2 快排的基本思想

时间复杂度： O(nlogn)
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行。

2.3 快排的基本原理

a.在数列之中，选择一个元素作为”基准”（pivot），或者叫比较值
b.数列中所有元素都和这个基准值进行比较，如果比基准值小就移到基准值的左边，如果比基准值大就移到基准值的右边
c.以基准值左右两边的子列作为新数列，不断重复第一步和第二步，直到所有子集只剩下一个元素为止

2.4 代码实现

def quickSort(lists):
    '''快速排序实现'''
    if len(lists) < 2:
        return lists
    # 第一步：随机选取基准，这里选列表中间的数便于理解,并从源列表中移除基准值
    mid = lists[len(lists) // 2]
    lists.remove(mid)
    # 第二步：定义基准值左右两个列表
    left,right = [],[]
    # 第三步：循环比较
    for num in lists:
        # 大于基准值的放到右边
        if num >= mid:
            right.append(num)
        else:
            # 小于基准值的放到左边
            left.append(num)
    # 第四步：利用递归迭代得到结果
    return quickSort(left) + [mid] + quickSort(right)
        
if __name__ == "__main__":
    arr = [5,4,3,6,9,2,1,0,7,8]
    print("Before sort: ", arr)
    print("After  sort: ", quickSort(arr))

2.5 排序结果

quickSort.png

3.0 冒泡排序

3.1 冒泡的基本思想

时间复杂度： O(n^2)
“冻结”列表的长度，然后进行遍历，把最大数推到最后，然后将“冻结”的列表长度减1，重复此操作完成排序

3.2 冒泡的基本原理

从第一项开始，将第一项 a 和第二项 b 比较，如果 a < b，则不动，否则交换两者的顺序。然后将第二项 b 和第三项 c 比较，和前面是一样的。重复此过程直到最后一项。

3.3 代码实现

def bubbleSort(lists):
    length = len(lists)
    while length > 0:
        for i in range(length-1):
            if lists[i] > lists[i+1]:
                lists[i],lists[i+1] = lists[i+1],lists[i]
        length -= 1
    return lists

if __name__ == "__main__":
    arr = [5,4,3,6,9,2,1,0,7,8]
    print("Before sort: ", arr)
    print("After  sort: ", bubbleSort(arr))

3.4 排序结果

bubbleSort.png

最后编辑于：2020.06.12 15:29:24