数据结构与算法-排序/二分查找

算法中基础中的基础，排序/二分查找

排序

1.快排QuickSort

def quicksort(nums):
    return QS(nums,0,len(nums)-1)

def QS(nums,left,right):
    if left >= right:
        return nums
    key = nums[left]
    lp = left 
    rp = right
    while lp < rp:
        while nums[rp] >= key and lp<rp:
            rp -= 1
        while nums[lp] <= key and lp<rp:
            lp += 1
        nums[rp],nums[lp] = nums[lp],nums[rp] # 碰到左右需要交换的元素时交换

    nums[left],nums[lp] = nums[lp],nums[left] # 此时lp = rp，与key元素交换，key在中间
    QS(nums,left,lp-1)
    QS(nums,lp+1,right)
    return nums

if __name__ == '__main__':
    lst = [5,4,6,2,7,3,8]
    print(quicksort(lst))

---

归并排序

def merge_sort(lst):
    if len(lst) <=1:
        return lst
    else:
        middle = len(lst)//2
        left = lst[:middle]
        right = lst[middle:]
        merge_sort(left)
        merge_sort(right)
        i,j,k = 0,0,0
        while i < len(left) and j< len(right):
            if left[i] <= right[j]:
                lst[k] = left[i]
                i = i + 1
            else:
                lst[k] = right[j]
                j = j + 1
            k = k + 1
        while i < len(left):
            lst[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            lst[k] = right[j]
            j += 1
            k += 1
        return lst

---

堆排序

def shiftdown(lst,i,n):
    h = 2 * i + 1
    while h <= n:
        if h + 1 <= n and lst[h+1] > lst[h]:
            h = h + 1
        if lst[h] > lst[i]:
            lst[i],lst[h] = lst[h],lst[i]
        else:
            break
        i = h
        h = 2 * i + 1


def heapSort(lst):
    length = len(lst)
    for j in range(length//2 - 1,-1,-1):
        shiftdown(lst,j,length-1)
    print('lst_tmp',lst)
    for i in range(length-1,0,-1):
        lst[0],lst[i] = lst[i],lst[0]
        shiftdown(lst,0,i-1)
    print('sorted lst',lst)

---

1. 二分查找

#coding=utf-8


def bi_search(nums,target):
    left = 0
    right = len(nums) - 1
   
    res = []
    while left <= right:
        mid =  (left + right) // 2 #left + (right - left) //2 
        #print(left,right)
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            right = mid -1 
        elif  nums[mid] < target:
            left = mid + 1
    
    return None
    

---