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

作者 |程序员小吴

来源 | 五分钟学算法（ID: CXYxiaowu）

1. 归并排序

1.1 算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

1.2 动画视频演示

1.3 参考代码

defmergeSort(arr):

importmath

if(len(arr)<2):

returnarr

middle=math.floor(len(arr)/2)

left,right=arr[0:middle],arr[middle:]

returnmerge(mergeSort(left),mergeSort(right))

defmerge(left,right):

result=[]

whileleftandright:

ifleft[0]<=right[0]:

result.append(left.pop(0));

else:

result.append(right.pop(0));

whileleft:

result.append(left.pop(0));

whileright:

result.append(right.pop(0));

returnresult

2. 快速排序

2.1 算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

2.2 动画视频演示

2.3 参考代码

defquickSort(arr,left=None,right=None):

left=0ifnotisinstance(left,(int,float))elseleft

right=len(arr)-1ifnotisinstance(right,(int,float))elseright

ifleft<right:

partitionIndex=partition(arr,left,right)

quickSort(arr,left,partitionIndex-1)

quickSort(arr,partitionIndex+1,right)

returnarr

defpartition(arr,left,right):

pivot=left

index=pivot+1

i=index

whilei<=right:

ifarr[i]<arr[pivot]:

swap(arr,i,index)

index+=1

i+=1

swap(arr,pivot,index-1)

returnindex-1

defswap(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 参考代码

defbuildMaxHeap(arr):

importmath

foriinrange(math.floor(len(arr)/2),-1,-1):

heapify(arr,i)

defheapify(arr,i):

left=2*i+1

right=2*i+2

largest=i

ifleft<arrLenandarr[left]>arr[largest]:

largest=left

ifright<arrLenandarr[right]>arr[largest]:

largest=right

iflargest!=i:

swap(arr,i,largest)

heapify(arr,largest)

defswap(arr,i,j):

arr[i],arr[j]=arr[j],arr[i]

defheapSort(arr):

globalarrLen

arrLen=len(arr)

buildMaxHeap(arr)

foriinrange(len(arr)-1,0,-1):

swap(arr,0,i)

arrLen-=1

heapify(arr,0)

returnarr

（本文为 AI科技大本营转载文章，转载请联系原作者）

在线分享会

◆

3月21日晚8点

◆

近年来，聊天机器人技术及产品得到了快速的发展，本课程将全面阐述聊天机器人的技术框架及工程实现细节，并对于聊天机器人的下一代范式：虚拟生命，进行了详细的剖析，同时，聚焦知识图谱在实现认知智能过程中的重要作用，给出了知识图谱的落地实践。

推荐阅读：

Pig变飞机？AI为什么这么蠢 | Adversarial Attack

3.15曝光：40亿AI骚扰电话和11家合谋者

如何从零开始用PyTorch实现Chatbot？（附完整代码）

杨超越第一，Python第二

麦克阿瑟奖得主Dawn Song：区块链能保密和保护隐私？图样图森破！

315 后，等待失业的程序员

大数据背后的无奈与焦虑：“128元连衣裙”划分矮穷挫与白富美？

京东强推 995 工作制，中国式变态加班何时休？

教训！学 Python 没找对路到底有多惨？

❤点击“阅读原文”，查看历史精彩文章。

如果觉得《算法面试经常需要你手写的三个排序算法（Python语言）》对你有帮助，请点赞、收藏，并留下你的观点哦！