[LeetCode]排序算法代码及其变种解析

Thursday. June 21, 2018 - 6 mins

常用排序算法

整理常用排序算法的目的在于不断加深对于基础算法的理解，最好可以达到理解算法思想的情况下，默写的程度。排序算法在面试中考察的很常见，手撕代码更是（快手面试的时候我就被手撕堆排序的算法搞崩了）。深入理解每个排序算法的稳定度，时间复杂度，计算开销对于算法优化也有帮助。先总结比较排序算法，之后会对非比较排序算法进行一个归纳。

比较排序算法

冒泡排序
选择排序
插入排序
归并排序
堆排序
快速排序
希尔排序

冒泡排序

算法复杂度是O(n^2)。最基础的排序算法。冒泡排序的思想: 每次比较两个相邻的元素, 如果他们的顺序错误就把他们交换位置。排序是稳定的。最好情况为O(n),最坏情况为O(n^2)。Python代码。

def bubbleSort(nums):
    for i in range(len(nums)-1):
        for j in range(len(nums)-i-1):
            if nums[j]>nums[j+1]:
                nums[j],nums[j+1] = nums[j+1],nums[j]
nums1 = [23,17,88,17,92,6]                
bubbleSort(nums1)
print nums1

选择排序

算法复杂度是O(n^2)。算法思想在于每次选择序列中最小的元素，与第一个进行交换，之后再剩余的序列中再次选择出最小的元素，与剩余序列的第一个交换，以此类推，完成选择排序。选择排序是不稳定的。最好和最坏的情况都是O(n^2)。

def chooseSort(nums):
    for i in range(len(nums)-1):
        minIndex = i
        for j in range(i+1,len(nums)):
            if nums[j]<nums[minIndex]:
                minIndex = j
        nums[i],nums[minIndex] = nums[minIndex],nums[i]
    
nums1 = [23,17,88,17,92,6]  
chooseSort(nums1)
print nums1

插入排序

算法复杂度是O(n^2)。类似于抓扑克牌，算法通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。最好情况为O(n),最坏情况为O(n^2)。稳定排序。

def insertSort(nums):
    for i in range(1,len(nums)):
        value = nums[i]
        j = i-1
        while nums[j]>value and j>=0:
            nums[j+1] = nums[j]
            j-=1
        nums[j+1] = value

归并排序

算法复杂度是O(nlogn)。在快手面试时候遇到了一个归并排序问题，写的跟屎一样。归并排序有递归和非递归版本，算法运用分治法，将大问题分割成小问题进行解决，小问题的答案merge再还原原始问题。最好和最坏情况都是O(nlogn)。需要额外辅助空间O(n)。算法是稳定的。先写一般递归的，比较好理解。后续补出非递归版本。

def merge(left,right):
    result = []
    while (len(left)>0 and len(right)>0):
        if left[0]<=right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    
    result += left
    result += right
    
    return result      
    
def mergeSort(nums):
    if len(nums)==1:
        return nums
    mid = len(nums)//2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left,right)
    
nums1 = [23,17,88,17,92,6]  
nums1 = mergeSort(nums1)
print nums1

快速排序

算法的时间复杂度是O(nlogn)。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。快速排序也是不稳定的算法。同样有递归和非递归版本。实际上，递归的算法开销会更高一点，但是确实是好写-。- 反正面试我一般写递归的。

快速排序也使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为：

从序列中挑出一个元素，作为”基准”(pivot).
把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

def quickSort(nums,left,right):
    if left<right:
        pivot = partition(nums,left,right)
        quickSort(nums,left,pivot-1)
        quickSort(nums,pivot+1,right)
    
def partition(nums,low,high):
    flag = nums[low]
    while low<high:
        while low<high and nums[high]>=flag:
            high -=1
        nums[low] = nums[high]
        while low<high and nums[low]<=flag:
            low +=1
        nums[high] = nums[low]   
    nums[low] = flag
    return low
                
nums1 = [23,17,88,17,92,6] 
quickSort(nums1,0,len(nums1)-1)
print nums1

堆排序

算法的时间复杂度是O(nlogn)。最好和最坏的情况都是O(nlogn)。无需额外的内存空间。算法是不稳定的。堆排序算法基于堆的特性，生成大顶堆和小顶堆。其满足完全二叉树的性质，以大顶堆为例，其子节点的键值都小于他的父节点。

算法描述

建立初始堆，初始堆中调整所有非叶子节点，若是大于其父节点，就替换掉。
将堆顶与未排序的最后一次替换，继续调整。调整结束，堆顶又为最大值。这样每次，已排序序列增加一个，未排序序列减少一个。借用别人的话，将当前无序序列中的第一个元素（反映在数中是根节点b），与无序序列中的最后一个元素交换（假设为c），b进入有序序列，到达最终位置。无序序列元素减少1个，有序序列元素增加1个，此时只有节点c可能不满足堆的定义，对其进行调整。
重复2 的过程，直到无序序列的元素剩下一个时排序结束。

父节点的子节点的位置为：lchild:i*2+1,rchild:i*2+2

def adjust_heap(nums,i,size):
    #左右孩子所在的节点位置
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    maxIndex = i 
    #如果其在非叶子节点
    if i < size // 2:
        if lchild < size and nums[lchild] > nums[maxIndex]:
            maxIndex = lchild
        if rchild < size and nums[rchild] > nums[maxIndex]:
            maxIndex = rchild
        #如果存在左右节点大于其父节点，则替换
        if maxIndex != i:
            nums[maxIndex], nums[i] = nums[i], nums[maxIndex]
            adjust_heap(nums, maxIndex, size) #继续调整
    
def build_heap(nums,size):
    #从堆的第一个非叶子节点开始，从右向左，从下到上，对每个节点进行调整，最终建立大根堆
    for i in range(0, size//2,)[::-1]:
        adjust_heap(nums, i, size)
        
def heapSort(nums):
    size = len(nums)
    build_heap(nums,size)
    for i in range(0,size,)[::-1]:
        nums[0], nums[i] = nums[i], nums[0]
        adjust_heap(nums, 0, i)
    
nums1 = [23,17,88,17,92,6]  
heapSort(nums1)
print nums1

希尔排序

算法的时间复杂度为为O(n^1.3)。希尔排序又称为缩小增量排序，在我的理解就是一个多级的直接插入排序。算法的步骤，就是不断从step大的到step小的值，然后在每个step下使用直接插入排序。算法是不稳定的。

def shellSort(nums):
    step=len(nums)//2
    while step>0:
        for i in range(step,len(nums)):            #在索引为step到len（L）上，比较L[i]和L[i-step]的大小
            while(i >= step and nums[i] < nums[i-step]):      #每一个step利用插入排序
                nums[i],nums[i-step] = nums[i-step],nums[i]
                i -= step
        step //= 2
    
    
nums1 = [23,17,88,17,92,6]  
shellSort(nums1)
print nums1