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 -= 1return 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 numsnums = [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, endbase = nums[i]while i < j:while i < j and nums[j] >= base:j -= 1nums[i] = nums[j]while i < j and nums[i] <= base:i += 1nums[j] = nums[i]nums[i] = baseQuickSort(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 -= 1return nums
nums = [9,4,10,8,13,2,15,7]
print(InsertSort(nums))

4.希爾排序

'''希爾排序'''
#①第一層循環 gap折半 直到gap=1
#②二層三層循環直接插入排序
def ShellSort(nums):gap = len(nums) // 2while 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 // 2return 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 numsdef HeapSort(nums, i, l):left, right = 2 * i + 1, 2 * i + 2  # 左右子節點的下標index = i# 構造大頂推if left <= l and nums[i] < nums[left]:index = leftif right <= l and nums[left] < nums[right] and nums[i] < nums[right]:index = rightif 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 numsdef SmallHeapSort(nums, i, l):left, right = 2 * i + 1, 2 * i + 2  # 左右子節點的下標index = i# 構建小頂堆if left <= l and nums[i] > nums[left]:index = leftif right <= l and nums[left] > nums[right] and nums[i] > nums[right]:index = rightif 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 numsmid = len(nums) // 2left = 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 += leftres += rightreturn resif __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 = 0high = len(nums)-1while low <= high:mid = (low + high) // 2if nums[mid] == target:return 'target in nums'elif nums[mid] < target:low = mid + 1else:high = mid - 1return 'target not in nums'
nums = [2, 4, 7, 8, 9, 10, 13, 15, 19]
print(BinarySearch(13, nums))
print(BinarySearch(20, nums))