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

我就是我 2022-03-10 06:56 168阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 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 ###

**周末不需要打卡~**

补充：最近打卡人数太多，前期小吴并未很严格的审核留言，目前已经兑换了上千的奖励，小吴已经破产啦。所以今后打卡留言一定要符合主题要求才能移入精选算打卡成功，见谅见谅，笔芯：）当然，如果你想随意留言，去掉开头打卡二字就行了，哈哈哈。周末愉快：）

[640_wx_fmt_jpeg]: /images/20220310/c255beddc913483ba87a7fae8bb4edce.png