合作专线:17362615757
行业资讯

AI资讯

当前位置:首页 > 行业资讯 > AI资讯

机器学习算法最终面试经常我需要你手写稿的三个排序算法(Python使用语言)


作者 | 程序员小吴来源 | 五分钟学算法(ID: CXYxiaowu)
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
(本文为 AI科技大本营转载文章,转载请联系原作者)在线分享会◆3月21日晚8点◆近年来,聊天机器人技术及产品得到了快速的发展,本课程将全面阐述聊天机器人的技术框架及工程实现细节,并对于聊天机器人的下一代范式:虚拟生命,进行了详细的剖析,同时,聚焦知识图谱在实现认知智能过程中的重要作用,给出了知识图谱的落地实践。

推荐阅读:Pig变飞机?AI为什么这么蠢 | Adversarial Attack3.15曝光:40亿AI骚扰电话和11家合谋者如何从零开始用PyTorch实现Chatbot?(附完整代码)杨超越第一,Python第二麦克阿瑟奖得主Dawn Song:区块链能保密和保护隐私?图样图森破!315 后,等待失业的程序员大数据背后的无奈与焦虑:“128元连衣裙”划分矮穷挫与白富美?京东强推 995 工作制,中国式变态加班何时休?教训!学 Python 没找对路到底有多惨?
                         ❤点击“阅读原文”,查看历史精彩文章。
Auto_z