排序算法-leetcode

一、冒泡排序O(n2)

记忆口诀:双层循环比较交换

核心代码:

def bubbleSort(arr):
    #双层循环,比较交换
    for i in range(1,len(arr)):
        for j in range(0,len(arr)-i):
            if arr[j]>arr[j+1]:
                arr[j],arr[j+1]=arr[j+1],arr[j]
    return arr

 

二、插入排序O(n2)

记忆口诀:外层循环始标值,内层while向前插

核心代码:

def insertionSort(arr):
    #外层循环始标值,内层while向前插
    for i in range(len(arr)):
        preIndex=i-1
        current = arr[i]
        while preIndex>=0 and arr[preIndex]>current:
            arr[preIndex+1]=arr[preIndex]
            preIndex-=1
        arr[preIndex+1]=current
    return arr

 

三、归并排序O(nlogn)   分治思想

记忆口诀:归中二分天下,并中三顾while

核心代码:

def mergeSort(arr):
    #归中二分天下,并中三顾while
    import math
    if len(arr)<2:return arr
    middle = math.floor(len(arr)/2)
    left = arr[0:middle]
    right = arr[middle:]
    return merge(mergeSort(left),mergeSort(right))

def merge(left,right):
    result=[]
    while left and right:
        if left[0]>right[0]:
            result.append(right.pop(0))
        else:
            result.append(left.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

 

四、快速排序O(nlogn)  分治思想  (全班同学按高矮排序)

记忆口诀:找基准双递归,快慢指针交换

核心代码:

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
2

发表评论

电子邮件地址不会被公开。 必填项已用*标注

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

排序算法-leetcode
嘿!有什么能帮到您的吗?
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close