九大排序算法的 Python 实现

Author Avatar
Tr0y 10月 14, 2018 22:28:49 本文共 1.9k 字
  • 文为知己者书
  • 在其它设备中阅读本文章

九大排序算法的 Python 实现。继续加油~

在此基础上加了 桶排序

代码

# -*- coding: utf-8 -*-
from __future__ import print_function
import random


def func(a, b, reversed):
    return a < b if reversed else a > b


def insertSort(unsorted_list, reversed=False):
    '''
    直接插入排序
    把 n 个待排序的元素看成一个有序表和一个无序表,
    开始时有序表中只有一个元素,无序表中有 n-1 个元素。
    排序过程即每次从无序表中取出第一个元素,
    将它插入到有序表中,使之成为新的有序表,重复 n-1 次完成整个排序过程。
    '''
    print("raw: ", unsorted_list)

    for i in range(1, len(unsorted_list)):
        j = i-1
        cmp = unsorted_list[i]

        while j > -1 and func(unsorted_list[j], cmp, reversed):
            unsorted_list[j+1], unsorted_list[j] = unsorted_list[j], cmp
            j -= 1
        print("NO.%d:" % i, unsorted_list)
    print("last:", unsorted_list)
    return unsorted_list


def shellSort(unsorted_list, reversed=False):
    '''
    希尔排序是一种插入排序算法,又称作缩小增量排序。是对直接插入排序算法的改进。其基本思想是: 
    先取一个小于 n 的整数作为第一个增量,把全部数据分成个组。所有距离为的倍数的记录放在同一个组中。
    先在各组内进行直接插入排序;
    然后,取第二个增量重复上述的分组和排序,直至所取的增量,即所有记录放在同一组中进行直接插入排序为止。
    该方法实质上是一种分组插入方法。
    1 2 3 4 5 6 7 8 9 10 11
    -----------
      -----------
        -----------
    '''
    print("raw: ", unsorted_list)
    n = len(unsorted_list)/2
    num = 1
    while n:
        for ni in range(n):
            group = range(ni, len(unsorted_list), n)
            for i in range(1, len(group)):
                j = i-1
                cmp = unsorted_list[group[i]]
                while j > -1 and func(unsorted_list[group[j]], cmp, reversed):
                    unsorted_list[group[j+1]], unsorted_list[group[j]] = unsorted_list[group[j]], cmp
                    j -= 1

        print("NO.%d:" % num, unsorted_list)
        n /= 2
        num += 1
    print("last:", unsorted_list)
    return unsorted_list


def selectSort(unsorted_list, reversed=False):
    '''
    每一趟从待排序的数据元素中选出最小(最大)的元素,
    顺序放在待排序的数列最前,直到全部待排序的数据元素全部排完。
    一共需要 n-1 趟
    '''
    print("raw: ", unsorted_list)
    for loc in range(len(unsorted_list)-1):
        for i in range(loc, len(unsorted_list)):
            if func(unsorted_list[loc], unsorted_list[i], reversed):
                unsorted_list[i], unsorted_list[loc] = unsorted_list[loc], unsorted_list[i]
        print("NO.%d:" % loc, unsorted_list)
    print("last:", unsorted_list)
    return unsorted_list


def heapSort(unsorted_list, reversed=False):
    '''
    堆排序涉及到的概念
    - 堆排序是利用 堆进行排序的
    - 堆是一种完全二叉树
    - 堆有两种类型: 大根堆 小根堆
    - 两种类型的概念如下:
        - 大根堆:每个结点的值都大于或等于左右孩子结点
        - 小根堆:每个结点的值都小于或等于左右孩子结点

    首先将待排序的数组构造出一个大根堆
    取出这个大根堆的堆顶节点(最大值),与堆的最下最右的元素进行交换,
    然后把剩下的元素再构造出一个大根堆。
    重复第二步,直到这个大根堆的长度为 1,此时完成排序。

    例子:
     1  2   3  4  5  6  7  8  9  10
    [3, 4, 10, 6, 8, 2, 5, 1, 7, 9]

            3
       4        10
     6   8    2    5
    1 7 9 x  x x  x x

    规律:
    - 如何找到 6 这个节点:(length-1)/2 => (10-1)/2=4
    - https://www.jianshu.com/p/d174f1862601
    '''

    def heap_adjust(L, start, end):
        temp = L[start]
        i = start
        j = 2 * i
        while j <= end:
            if (j < end) and func(L[j+1], L[j], reversed):
                j += 1
            if func(L[j], temp, reversed):
                L[i], i, j = L[j], j, 2*j
            else:
                break
        L[i] = temp

    print("raw: ", unsorted_list)
    unsorted_list.insert(0, 0)
    L_length = len(unsorted_list) - 1

    first_Sort_count = L_length / 2
    for i in range(first_Sort_count):
        heap_adjust(unsorted_list, first_Sort_count - i, L_length)

    print("Heap:", unsorted_list[1:])
    for i in range(L_length - 1):
        unsorted_list[1], unsorted_list[L_length -
                                        i] = unsorted_list[L_length - i], unsorted_list[1]
        heap_adjust(unsorted_list, 1, L_length - i - 1)
        print("No.%d:" % i, unsorted_list[1:])

    unsorted_list.pop(0)
    print("last:", unsorted_list)
    return unsorted_list


def bubbleSort(unsorted_list, reversed=False):
    '''
    S1:从待排序序列的起始位置开始,从前往后依次比较各个位置和其后一位置的大小并执行 S2。 
    S2:如果当前位置的值大于其后一位置的值,就把他俩的值交换
       (完成一次全序列比较后,序列最后位置的值即此序列最大值,所以其不需要再参与冒泡)。 
    S3:将序列的最后位置从待排序序列中移除。若移除后的待排序序列不为空则继续执行 S1,否则冒泡结束。
    '''
    print("raw: ", unsorted_list)
    num = 0
    while len(unsorted_list)-num:
        for i in range(0, len(unsorted_list)-num-1):
            if func(unsorted_list[i], unsorted_list[i+1], reversed):
                unsorted_list[i], unsorted_list[i+1] = unsorted_list[i+1], unsorted_list[i]

        print("No.%d:" % num, unsorted_list)
        num += 1

    print("last:", unsorted_list)


def quickSort(unsorted_list, base_loc=0, reversed=False):
    '''
    快速排序是对冒泡排序的一种改进。
    基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,
    其中一部分的所有数据都比另外一部分的所有数据都要小,
    然后再按此方法对这两部分数据分别进行快速排序,
    整个排序过程可以递归进行,以此实现整个数据变成有序序列。
    '''
    print("raw: ", unsorted_list)
    num = [0]

    def _sort(l, r):
        if l < r:
            if num[0]:
                print("No.%d:" % num[0], unsorted_list)
            num[0] += 1
            if base_loc:
                q = partition_final(unsorted_list, l, r)
            else:
                q = partition_first(unsorted_list, l, r)
            _sort(l, q - 1)
            _sort(q + 1, r)

    def partition_final(unsorted_list, l, r):
        x = unsorted_list[r]
        i = l - 1
        for j in range(l, r):
            if x > unsorted_list[j]:
                i += 1
                unsorted_list[i], unsorted_list[j] = unsorted_list[j], unsorted_list[i]
        unsorted_list[i+1], unsorted_list[r] = unsorted_list[r], unsorted_list[i+1]
        return i+1

    def partition_first(unsorted_list, l, r):
        x = unsorted_list[l]
        i = r + 1
        for j in range(r, l, -1):
            if x < unsorted_list[j]:
                i -= 1
                unsorted_list[i], unsorted_list[j] = unsorted_list[j], unsorted_list[i]
        unsorted_list[i-1], unsorted_list[l] = unsorted_list[l], unsorted_list[i-1]
        return i-1

    _sort(0, len(unsorted_list)-1)
    print("last:", unsorted_list)


def mergeSort(unsorted_list, reversed=False):
    '''
    合并两个已排序好的列表,产生一个新的已排序好的列表
    归并排序的算法我们通常用递归实现。
    先把待排序区间[s,t]以中点二分,接着把左边子区间排序,
    再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
    '''
    print("raw: ", unsorted_list)

    def _sort(unsorted_list):
        if len(unsorted_list) <= 1:
            return unsorted_list

        mid = len(unsorted_list) / 2
        left = _sort(unsorted_list[:mid])
        right = _sort(unsorted_list[mid:])
        result = merge(left, right)
        return result

    def merge(left, right):
        result = []  # 新的已排序好的列表

        left = left[::-1]
        right = right[::-1]

        while left and right:
            left_num = left.pop()
            right_num = right.pop()

            if func(right_num, left_num, reversed):
                result.append(left_num)
                right.append(right_num)
            else:
                result.append(right_num)
                left.append(left_num)

        return result+left[::-1]+right[::-1]

    unsorted_list = _sort(unsorted_list)
    print("last:", unsorted_list)
    return unsorted_list


def bucketSort(unsorted_list, reversed=False):
    '''
    桶排序
    '''
    print("raw: ", unsorted_list)
    buckets = [0] * ((max(unsorted_list)-min(unsorted_list))+1)
    for num in unsorted_list:
        buckets[num-min(unsorted_list)] += 1

    unsorted_list = sum([[i+min(unsorted_list)]*num for i, num in enumerate(buckets)], [])
    print("last:", unsorted_list)


def radixSort(unsorted_list, reversed=False):
    '''
    将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。
    然后,从最低位开始,依次进行一次排序。
    这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
    '''
    import math

    for i in range(int(math.log10(max(unsorted_list)))+1):
        bucket = [[] for _ in range(10)]
        for val in unsorted_list:
            bucket[int(val % (10 ** (i+1)) / (10 ** i))].append(val)

        unsorted_list = sum(bucket, [])

    if reversed:
        unsorted_list = unsorted_list[::-1]

    print(unsorted_list)
    return unsorted_list

unsorted_list = range(10, 0, -1)
random.shuffle(unsorted_list)

# insertSort(unsorted_list)
# shellSort(unsorted_list)
# selectSort(unsorted_list)
# heapSort(unsorted_list)
# bubbleSort(unsorted_list)
# quickSort(unsorted_list)
# mergeSort(unsorted_list)
# bucketSort(unsorted_list)
# radixSort(unsorted_list)

一些感想

算法的精妙之处,有时候自己实现一遍才能体会到。而且我在实现的过程中,会到了算法与代码结合的难点(明明知道意思,却不知道怎么用代码表达出来)。

ACM 大佬是真的大佬。

End

What do you think?

本文标题: 九大排序算法的 Python 实现
原始链接: http://www.tr0y.wang/2018/10/14/sorts/
发布时间: 2018.10.14-22:28
最后更新: 2018.11.03-21:18
版权声明: 本站文章均采用CC BY-NC-SA 4.0协议进行许可。转载请注明出处!