酷应用

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

百家作者：AI100 2019-03-18 14:48:56

作者 |?程序员小吴

来源 | 五分钟学算法（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