专栏首页五分钟学算法算法面试经常需要你手写的三个排序算法(Python语言)

算法面试经常需要你手写的三个排序算法(Python语言)

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

End

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 聊聊「插入排序」的正确姿势

    面试官最爱考察的是一个被试者对知识掌握的灵活程度和熟练程度,当一道题目可以同时考察到被试者多个知识点的掌握程度和思考能力时,面试官最爱这样的题目,而且对于插入排...

    五分钟学算法
  • 这或许是东半球分析十大排序算法最好的一篇文章

    本文全长 14237 字,配有 70 张图片和动画,和你一起一步步看懂排序算法的运行过程。

    五分钟学算法
  • 看动画轻松理解「链表」实现「LRU缓存淘汰算法」

    前几节学习了「链表」、「时间与空间复杂度」的概念,本节将结合「循环链表」、「双向链表」与 「用空间换时间的设计思想」来设计一个很有意思的缓存淘汰策略:LRU缓存...

    五分钟学算法
  • golang数据结构之快速排序

    具体过程:黑色标记代表左指针,红色标记代表右指针,蓝色标记代表中间值。(依次从左往向下)

    绝命生
  • LeetCode111|独一无二的出现次数

    键值对HashMap的重要性真的是不言而喻的,因为它应用的太广泛了,可以说基本上你做应用就是使用它,和ArrayList的次数相差不大,所以你现在如果不懂的话,...

    码农王同学
  • [PHP] 算法-把数组排成最小的数的PHP实现

    陶士涵
  • Js实现数组排序

    常用排序的Js实现方案,包括原型链方法调用、简单选择排序、冒泡排序、插入排序、快速排序、希尔排序、堆排序、归并排序。

    WindrunnerMax
  • Sort Algorithm排序算法

    第一次迭代,寻找0到6个下标的数字哪个是最小的,找到最小的就和第一个交换,也就是2。第一次遍历所有

    西红柿炒鸡蛋
  • 快速排序

    程序员不务正业
  • golang数据结构之冒泡排序

    绝命生

扫码关注云+社区

领取腾讯云代金券