最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 1. 归并排序

    1.1 算法步骤

    • 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
    • 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
    • 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
    • 重复步骤 3 直到某一指针达到序列尾;
    • 将另一序列剩下的所有元素直接复制到合并序列尾。

    1.2 动画视频演示

    1.3 参考代码

    def mergeSort(arr):
        import math
        if(len(arr)<2):
            return arr
        middle = math.floor(len(arr)/2)
        left, right = arr[0:middle], arr[middle:]
        return merge(mergeSort(left), mergeSort(right))
    def merge(left,right):
        result = []
        while left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0));
            else:
                result.append(right.pop(0));
        while left:
            result.append(left.pop(0));
        while right:
            result.append(right.pop(0));
        return result

    2. 快速排序

    2.1 算法步骤

    • 从数列中挑出一个元素,称为 “基准”(pivot);
    • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

    2.2 动画视频演示

    2.3 参考代码

    def quickSort(arr, left=None, right=None):
        left = 0 if not isinstance(left,(int, float)) else left
        right = len(arr)-1 if not isinstance(right,(int, float)) else right
        if left < right:
            partitionIndex = partition(arr, left, right)
            quickSort(arr, left, partitionIndex-1)
            quickSort(arr, partitionIndex+1, right)
        return arr
    def partition(arr, left, right):
        pivot = left
        index = pivot + 1
        i = index
        while  i <= right:
            if arr[i] < arr[pivot]:
                swap(arr, i, index)
                index += 1
            i += 1
        swap(arr,pivot,index – 1)
        return index – 1
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]

    3. 堆排序

    3.1 算法步骤

    • 创建一个堆 H[0……n-1];
    • 把堆首(最大值)和堆尾互换;
    • 把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
    • 重复步骤 2,直到堆的尺寸为 1。

    3.2 动画视频演示

    3.3 参考代码

    def buildMaxHeap(arr):
        import math
        for i in range(math.floor(len(arr)/2),-1,-1):
            heapify(arr,i)
    def heapify(arr, i):
        left = 2*i+1
        right = 2*i+2
        largest = i
        if left < arrLen and arr[left] > arr[largest]:
            largest = left
        if right < arrLen and arr[right] > arr[largest]:
            largest = right
        if largest != i:
            swap(arr, i, largest)
            heapify(arr, largest)
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]
    def heapSort(arr):
        global arrLen
        arrLen = len(arr)
        buildMaxHeap(arr)
        for i in range(len(arr)-1,0,-1):
            swap(arr,0,i)
            arrLen -=1
            heapify(arr, 0)
        return arr
    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 算法面试经常需要你手写的三个排序算法(Python语言)

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 101会员总数(位)
    • 3672资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 128稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级