【数据结构与算法】【LeetCode】【排序】常用排序算法

# 采用左闭右闭
def quick_sort(nums,lo,hi):#nums:List[int] ,lo:int,hi:int
    if lo+1>=hi:
        return
    first=lo
    last = hi-1
    pivot = nums[first]
    while first<last:
        while first<last and nums[last]>=pivot:
            last=last-1
        nums[first]=nums[last]
        while first<last and nums[first]<=pivot:
            first=first+1
        nums[last]=nums[first]
    nums[first]=pivot
    quick_sort(nums,lo,first)
    quick_sort(nums,first+1,hi)

nums=[5,4,3,1,6,5]
quick_sort(nums,0,len(nums))
nums

def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1
 
    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)
 
    return c
 
def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists)//2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)
 
if __name__ == '__main__':
    a = [14, 2, 34, 43, 21, 19]
    print (merge_sort(a))

def insert_sort(arr):
    """插入排序"""
    # 第一层for表示循环插入的遍数
    for i in range(1, len(arr)):
        # 设置当前需要插入的元素
        current = arr[i]
        # 与当前元素比较的比较元素
        pre_index = i - 1
        while pre_index >= 0 and arr[pre_index] > current:
            # 当比较元素大于当前元素则把比较元素后移
            arr[pre_index + 1] = arr[pre_index]
            # 往前选择下一个比较元素
            pre_index -= 1
        # 当比较元素小于当前元素，则将当前元素插入在 其后面
        arr[pre_index + 1] = current
    return arr

insert_sort([11, 2,1,4,5,3,9])

def bubble_sort(nums):# nums：List[int]
    n = len(nums)
    for i in range(1,n):
        swapped = False
        for j in range(1,n-i+1):
            if nums[j]<nums[j-1]:
                
                nums[j],nums[j-1]=nums[j-1],nums[j] # 两者值交换
                swapped= True
        if not swapped:
            break
nums=[2,1,4,3,6,5]
bubble_sort(nums)
print(nums)

def selection_sort(nums):
    n = len(nums)
    for i in range(n):
        pos = i
        for j in range(i+1,n):
            if nums[j]<nums[pos]:
                pos=j
        nums[pos],nums[i]=nums[i],nums[pos]
nums=[3,1,2,5,4,6]
selection_sort(nums)
nums