《python》-14: 十大经典排序算法

2019-05-23  本文已影响0人  月上秦少

Python3 实现十大经典排序算法

算法分类

算法分类

算法比较

算法比较

术语说明

1.选择排序（Selection Sort）

def select_sort(data):
    """
    :param data: list
    :return: sorted data
    """

    length = len(data)
    if length < 2:
        return data

    for i in range(length - 1):
        # 最小值的索引
        minIndex = i
        for j in range(i + 1, length):
            # 找到最小值的索引
            if (data[j] < data[minIndex]):
                minIndex = j
            # 将最小的值放在i处
            data[i], data[minIndex] = data[minIndex], data[i]
        # print(data)
    return data

2.冒泡排序（Bubble Sort）

def bubble_sort(data):
    """
    :param data: list
    :return: sorted data
    """

    length = len(data)
    if length < 2:
        return data

    for i in range(length - 1):
        for j in range(length - 1 - i):
            if (data[j + 1] < data[j]):
                data[j], data[j + 1] = data[j + 1], data[j]
        # print(data)
    return data

3.插入排序（Insertion Sort）

def insert_sort(data):
    """
    :param data:list
    :return: sorted data
    """
    length = len(data)
    if length < 2:
        return data

    for i in range(0, length - 1):
        preIndex = i
        current = data[i + 1]
        while preIndex >= 0 and current < data[preIndex]:
            # 增加空间
            data[preIndex + 1] = data[preIndex]
            preIndex -= 1
        data[preIndex + 1] = current
        # print(data)
    return data

4.希尔排序（Shell Sort）

def shell_sort(data):
    """
    :param data: list
    :return: sorted data
    """
    length = len(data)
    if length < 2:
        return data

    step = length // 2
    while step > 0:
        for i in range(step, length):
            while i >= step and data[i - step] > data[i]:
                data[i - step], data[i] = data[i], data[i - step]
                i -= step
        # print(data)
        step = step // 2
    return data

5.归并排序（Merge Sort）

def merge_sort(data):
    """
    :param data: list
    :return: sorted data
    """
    length = len(data)
    if length < 2:
        return data
    mid = length // 2
    # 分别对两个子列表并归排序
    merge_left = merge_sort(data[:mid])
    merge_right = merge_sort(data[mid:])

    def merge(data_left, data_right):
        # print(data_left, data_right)
        """
        合并(将两个有序的列表合并成一个有序的列表)
        :param data_left: data[:mid]
        :param data_right:data[mid:]
        :return: sorted data
        """
        left, right = 0, 0
        len_left = len(data_left)
        len_right = len(data_right)
        sorted_data = []
        while left < len_left and right < len_right:
            if data_left[left] < data_right[right]:
                sorted_data.append(data_left[left])
                left += 1
            else:
                sorted_data.append(data_right[right])
                right += 1
        sorted_data += data_left[left:]
        sorted_data += data_right[right:]
        return sorted_data

    # 合并(将两个有序的列表合并成一个有序的列表)
    return merge(merge_left, merge_right)

6.快速排序（Quick Sort）

def quick_sort(data):
    """
    :param data:list
    :return:sorted data
    """
    length = len(data)
    if length < 2:
        return data

    # 随机基准
    import random
    index = random.randint(0, length - 1)

    left = [l for l in data[index + 1:] + data[0:index] if l <= data[index]]
    right = [r for r in data[index + 1:] + data[0:index] if r > data[index]]
    #  有序数据 = 基准左侧  + 基准 + 基准右侧
    return quick_sort(left) + [data[index]] + quick_sort(right)

快速排序，一行代码实现(为了方便查阅，用了换行)

one_quick_sort = (lambda array: array if len(array) <= 1 else
    one_quick_sort([item for item in array[1:] if item <= array[0]]) +  # 小于基准
    [array[0]] +                                                        # 等于基准
    one_quick_sort([item for item in array[1:] if item > array[0]]))    # 大于基准

7.堆排序（Heap Sort）

def heap_sort(data):
    """
    :param data:list
    :return:sorted data
    """

    length = len(data)
    if length < 2:
        return data

    def adjustHeap(i):
        """调整使之成为最大堆"""
        maxIndex = i
        if i * 2 < length and data[i * 2] > data[maxIndex]:
            maxIndex = i * 2
        if i * 2 + 1 < length and data[i * 2 + 1] > data[maxIndex]:
            maxIndex = i * 2 + 1
        if maxIndex != i:
            data[maxIndex], data[i] = data[i], data[maxIndex]
            adjustHeap(maxIndex)

    def buildMaxHeap():
        """建立最大堆"""
        # 从最后一个非叶子节点开始向上构造最大堆
        i = (length - 1) // 2
        while i >= 0:
            adjustHeap(i)
            i -= 1

    # 构建一个最大堆
    buildMaxHeap()

    # 循环将堆首位（最大值）与末位交换，然后再重新调整最大堆
    while length > 0:
        data[0], data[length - 1] = data[length - 1], data[0]
        length -= 1
        adjustHeap(0)
        # print(data)
    return data

8.计数排序（Counting Sort）

def count_sort(data):
    """
    :param data:list
    :return:sorted data
    """
    length = len(data)
    if length < 2:
        return data

    # 数组C,None表示当前位置没有记录数据信息
    C = [None] * (max(data) - min(data) + 1)

    # 将计数信息存入C数组中
    for i in range(length):
        C[data[i] - min(data)] += 1
    # print(C)

    # 从C数组中按序取出数值并返回
    sorted_data = []
    for index, value in enumerate(C):
        # 判断当前位置是否记录有信息
        if value is not None:
            sorted_data += [index + min(data)] * value
    return sorted_data

9.桶排序（Bucket Sort）

def bucket_sort(data, num=10):
    """
    :param data:list
    :param num:bucket num
    :return:sorted data
    """
    length = len(data)
    if length < 2:
        return data

    min_value = min(data)
    max_value = max(data)

    import re
    pattern = r'^[1-9]+[0-9]*$'
    # 桶的数量，如果不匹配默认取10
    num = num if num > 1 and re.match(pattern, str(num)) else 10
    # 桶的空间
    space = int((max_value - min_value) / num) + 1
    # 初始化桶空间,注意:[[]] * num生成list的坑,两者append方法结果不同
    buckets = [[] for _ in range(num)]

    # 将数据放到对应的桶里面,难点:数据与桶的映射关系
    for i in range(length):
        # 数据与桶的映射关系
        index = int((data[i] - min_value) / space)
        # print(data[i], index)
        buckets[index].append(data[i])
        # print(buckets)

    # 桶内数据排序
    # for n in buckets:
    #     print(n)
    #     n.sort()

    # 按序取出桶内的数据，组成有序序列
    sorted_data = []
    for n in buckets:
        n.sort()
        sorted_data += n
    return sorted_data

10.基数排序（Radix Sort）

def radix_sort(data):
    """
    :param data:list
    :return:sorted data
    """

    length = len(data)
    if length < 2:
        return data
    # 最大位数
    max_value = max(data)
    max_digit = str(max_value).__len__()

    # 将数据按照个位、十位、百位。。。上的数字放到对应编号的桶里
    for i in range(max_digit):
        # 初始化桶，因为每个位置数范围0-9，故初始化10个桶
        buckets = [[] for _ in range(10)]
        for d in data:
            index = int(d / (10 ** i) % 10)
            buckets[index].append(d)
        # 从桶中按序取出数据放回原数组
        data = [d for b in buckets for d in b]
        print(data)
    return data

后话

其实Python有自带的排序函数,这里自己实现十大经典排序，一方面提高Python语言熟练度，另一方面锻炼自己的思维。

# 一句话搞定的事儿，何必呢。。。孔乙己：你知道“回”有多少种写法吗。。。
print(sorted(data))

本文动图来自网络，感谢网友们的分享。

上一篇下一篇

猜你喜欢

热点阅读