冒泡、选择、插入、归并、快速排序代码

import random

# 随机生成包含10个元素的数组
random.seed(10)
alist = [random.randint(1, 100) for _ in range(10)]

1. 冒泡排序

   '''
   冒泡排序
   每轮相邻的两个元素，两两相比，此轮最大的元素，像泡泡一样移动到队列尾部。
   每次j和j+1位置比较，胜者冒出去
   '''
   
   
   def bubble_sort(arr):
       n = len(arr)
       for i in range(n):
           # 前面i轮，已经有i个元素排序完毕，遍历最大数n要-i
           # 要让j和j+1(可能越界)比较，所以n-i还要再-1
           for j in range(n - i - 1):
               if arr[j] > arr[j + 1]:
                   arr[j], arr[j + 1] = arr[j + 1], arr[j]
       return arr
   
   
   print('冒泡排序')
   print(alist)
   print(bubble_sort(alist.copy()))
   

2. 选择排序

   '''
   选择排序
   每轮在剩余未排序元素中选择最小的，放在位置i, 连续进行n轮，完成排序。
   第i轮选择第i小的元素，放在位置i
   每轮j和i比较，争夺位置i
   '''
   
   
   def select_sort(arr):
       n = len(arr)
       for i in range(n):
           # 前面i-1个位置已经排序完毕，现在和位置i和它之后的元素（位置j）比，选最小的放在位置i.
           for j in range(i + 1, n):
               if arr[j] < arr[i]:
                   arr[i], arr[j] = arr[j], arr[i]
       return arr
   
   
   print('选择排序')
   print(alist)
   print(select_sort(alist.copy()))
   

3. 插入排序

   '''
   插入排序
   每次从未排序的数列中取一个元素，插入到已排序序列的正确位置，进行n次完成排序。
   队列分为已排序和未排序，如何插入合适位置？和待插入元素之前的元素对比，待插入元素比前面的元素小，则前面的元素依次向后移动一个位置，挪出一个合适的位置出来。
   '''
   
   
   def insert_sort(arr):
       n = len(arr)
       for i in range(1, n):
           # 取出待插入元素
           key = arr[i]
           j = i - 1
           # 检测待插入元素比前面的元素小
           while j >= 0 and key < arr[j]:
               # 前面的元素依次向后移动，因为待插入元素已经取出，所以’腾出了‘一个位置
               arr[j + 1] = arr[j]
               j -= 1
           # 将待插入的元素放入合适的位置
           # j-1之后回去判断那个位置已经不比key大了或者j小于0了，j得再加个1
           arr[j + 1] = key
       return arr
   
   print('插入排序')
   print(alist)
   print(insert_sort(alist.copy()))
   

4. 归并排序

   '''
   归并排序
   把原数组拆成两份，再对拆出来的数组继续拆分，拆分到不能拆为止，再把所有拆出来的小数组两两组合成一个新的排好序的数组。
   涉及递归思想，不断重复同一过程
   '''
   
   # 把两个排好序的数组组合成一个新的排好序的数组
   def merge(left, right):
       if not left or not right:
           return left or right
       arr = []
       while left and right:
           if left[0] < right[0]:
               arr.append(left.pop(0))
           else:
               arr.append(right.pop(0))
       arr += left or right
       return arr
   
   
   def merge_sort(arr):
       # 拆分到只剩一个元素，就停止并把这个数组返回
       # 递归要有终点和返回
       if len(arr) <= 1:
           return arr
       # 取原数组的中心
       mid = len(arr) // 2
       # 把数组分成左右两部分，分别对这两部分进行归并排序
       # 调用自身的过程
       left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
       # 排好序了再组合起来
       res = merge(left, right)
       return res
   
   
   print('归并排序')
   print(alist)
   print(merge_sort(alist.copy()))
   

5. 快速排序

   '''
   快速排序
   每次只把一个元素放入正确的位置，使它前面的元素都比它小（小于等于），它后面的元素都比它大（大于等于）
   对它左边的数组，右边的数组，重复这一过程，最终将所有元素放入正确位置。
   '''
   def quick_sort(arr, start, end):
       # 如果左右边都是一个元素，证明所有元素排序完毕
       if start >= end:
           return
   
       # 待排序数组，左边和右边的位置
       low, high = start, end
       # 每一轮暂且取最左边的元素作为pivot， 本轮将pivot放入正确位置。
       # 此刻最左边low位置已经空出来，因为arr[low]存在pivot里面了。
       pivot = arr[low]
       # low ---->    pivot    <----- high
       # 从两边向中间移动low, high两个指针
       while low < high:
           # 右边的元素如果都比pivot大，就不用移动该元素，high指针向前，继续向前比较
           while arr[high] >= pivot and low < high:
               high -= 1
           # 找到右边比pivot小的元素，把这个元素放在pivot的左边。刚才low这个位置已经空出来了，可以放在low那个位置
           # 赋值后，high这个位置也空出来了
           arr[low] = arr[high]
   
           # 左边的元素如果比pivot小，就不用移动该元素，low指针向后，继续向后比较
           while arr[low] <= pivot and low < high:
               low += 1
           # 找到左边比pivot大的元素，放在pivot右边，刚才空出来的high这个位置。
           arr[high] = arr[low]
       # 左边都比pivot小， 右边都比pivot大，这个时候high=low, 把pivot放入low的位置
       arr[low] = pivot
       # 递归调用这个过程，对pivot左边的数组，pivot右边的数组继续执行这个操作
       quick_sort(arr, start, low - 1)
       quick_sort(arr, low + 1, end)
   
   
   print('快速排序')
   arr = alist.copy()
   print(arr)
   quick_sort(arr, 0, len(arr) - 1)
   print(arr)