3. 排序算法代码-python

1.冒泡排序

'''冒泡排序'''

"""
def BubbleSort(nums):
    listLength = len(nums)
    while listLength > 0:
        for i in range(listLength - 1):
            if nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        listLength -= 1
    return nums
"""

def BubbleSort(nums):
    for i in range(len(nums)):
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 16,1]
print(BubbleSort(nums))

2.快速排序

'''快速排序'''

def QuickSort(nums, start, end):
    if start < end:
        i, j = start, end
        base = nums[i]
        while i < j:
            while i < j and nums[j] >= base:
                j -= 1
            nums[i] = nums[j]
            while i < j and nums[i] <= base:
                i += 1
            nums[j] = nums[i]
        nums[i] = base
        QuickSort(nums, start, i - 1)
        QuickSort(nums, i+1, end)

nums = [9,4,10,8,13,2,15,7]
QuickSort(nums, 0, len(nums)-1)
print(nums)

3.插入排序


'''插入排序'''

def InsertSort(nums):
    for i in range(len(nums)-1):
        if nums[i] > nums[i+1]:
            while i>=0 and nums[i] > nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
                i -= 1
    return nums
nums = [9,4,10,8,13,2,15,7]
print(InsertSort(nums))

4.希尔排序

'''希尔排序'''
#①第一层循环 gap折半 直到gap=1
#②二层三层循环直接插入排序
def ShellSort(nums):
    gap = len(nums) // 2
    while gap >= 1:
        for i in range(gap, len(nums)):
            for j in range(i-gap, -1, -gap):
                if nums[j] > nums[j+gap]:
                    nums[j], nums[j+gap] = nums[j+gap], nums[j]
        gap = gap // 2
    return nums
nums = [9,4,10,8,13,2,15,7]
print(ShellSort(nums))

5.选择排序

'''选择排序'''
def SelectSort(nums):

    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[j] < nums[i]:
                nums[j], nums[i] = nums[i], nums[j]
    return nums
nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 1,16]
print(SelectSort(nums))

6.堆排序

最大堆总是将其中的最大值存放在树的根节点。
而对于最小堆，根节点中的元素总是树中的最小值
应用场景
比如求10亿个数中的最大的前10个数，时时构建只有10个元素的小顶堆，如果比堆顶小，则不处理；如果比堆顶大，则替换堆顶，然后依次下沉到适当的位置。
比如求10亿个数中的最小的前10个数，时时构建只有10个元素的大顶堆，如果比堆顶大，则不处理；如果比堆顶小，则替换堆顶，然后依次下沉到适当的位置。
一般升序采用大顶堆，降序采用小顶堆

'''构造大顶堆'''
def HeapBuild(nums):
    l = len(nums) - 1
    # 构造大顶堆，从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点
    for i in range(len(nums)//2 - 1, -1, -1):
        HeapSort(nums, i, l)

    # 上面的循环完成了大顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆
    for j in range(l, -1, -1):
        nums[0], nums[j] = nums[j], nums[0]
        HeapSort(nums, 0, j-1)
    return nums

def HeapSort(nums, i, l):
    left, right = 2 * i + 1, 2 * i + 2  # 左右子节点的下标
    index = i
    # 构造大顶推
    if left <= l and nums[i] < nums[left]:
        index = left

    if right <= l and nums[left] < nums[right] and nums[i] < nums[right]:
        index = right

    if index != i:
        nums[i], nums[index] = nums[index], nums[i]
        HeapSort(nums, index, l)

nums = [17, 13, 40 , 22, 31, 14, 33, 56, 24, 19 ,10, 41, 51, 42, 26]
print('使用大顶堆排序：', HeapBuild(nums))

'''构造小顶堆'''
def SmallHeapBuild(nums):
    l = len(nums) - 1
    # 从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点
    for i in range(len(nums)//2 - 1, -1, -1):
        SmallHeapSort(nums, i, l) # 小顶堆构造函数

    # 上面的循环完成了小顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆
    # 使用小顶堆进行降序，nums[0]是最小的，放到最后
    for j in range(l, -1 ,-1):
        nums[0], nums[j] = nums[j], nums[0]
        SmallHeapSort(nums, 0, j-1)
    return nums

def SmallHeapSort(nums, i, l):
    left, right = 2 * i + 1, 2 * i + 2  # 左右子节点的下标
    index = i
    # 构建小顶堆
    if left <= l and nums[i] > nums[left]:
        index = left

    if right <= l and nums[left] > nums[right] and nums[i] > nums[right]:
        index = right

    if index != i:
        nums[i], nums[index] = nums[index], nums[i]
        SmallHeapSort(nums, index, l)

nums = [17, 13, 40 , 22, 31, 14, 33, 56, 24, 19 ,10, 41, 51, 42, 26]
print('使用小顶堆倒排序', SmallHeapBuild(nums))

7.归并排序


def MergeBuild(nums):
    if len(nums) == 1:
        return nums
    mid = len(nums) // 2

    left = nums[:mid]
    right = nums[mid:]

    l1 = MergeBuild(left)
    l2 = MergeBuild(right)

    return MergeSort(l1, l2)

def MergeSort(left, right):
    res = []
    while len(left) and len(right):
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    res += left
    res += right
    return res

if __name__ == '__main__':
    nums = [5, 2, 8, 4, 7, 4, 3, 9, 2, 0, 1,16]
    res = MergeBuild(nums)
    print(res)

8. 二分查找

'''二分查找'''
def BinarySearch(target, nums):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return 'target in nums'
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return 'target not in nums'
nums = [2, 4, 7, 8, 9, 10, 13, 15, 19]
print(BinarySearch(13, nums))
print(BinarySearch(20, nums))