2022年 11月 5日

用Python实现快速排序和冒泡排序，代码+详细解析

1、冒泡排序

        冒泡排序:每一次相邻的两个数做比较,大的往后移动一位,每次循环都会把最大的值(升序)或最小的值(降序)放在末端 。

  1. # a = [7, 8, 5, 45, 91, 1, -10, 0]
  2. a = [-1, 5.5, 2.56, 5.56, -9, 0, 0, 98, 56, -1.256]
  3. # a = [6, 1, 9, 2, 15, 11]
  4.  
  5. #遍历列表a
  6. for i in range(len(a)):
  7.     for n in range(0,len(a)-1-i):
  8.         # 将列表前后两个数进行比较，大的放后面小的放前面
  9.         # len(a)-1-i 剔除比对完的顶端数（最大/最小）,同时可以防止n+1超出下标界限
  10.         if a[n] > a[n+1]:
  11.             a[n], a[n+1] = a[n+1], a[n]
  12. print(a)
  13.  
  14. 输出结果：
  15. [-9, -1.256, -1, 0, 0, 2.56, 5.5, 5.56, 56, 98]

2、快速排序

        快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

         步骤为： 

        1.挑选基准值：从数列中挑出一个元素，称为”基准”（pivot）。

        2.分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成。

        3.递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

  1. import random
  2.  
  3.  
  4. def quick_sort(lists, i, j):
  5.     if i >= j:
  6.         return lists
  7.     # 定义一个基准数
  8.     pivot = lists[i]
  9.     low = i
  10.     high = j
  11.     while i < j:
  12.         # 向右找到比pivot小的数字
  13.         while i < j and lists[j] >= pivot:
  14.             # 指针向左移动
  15.             j -= 1
  16.         # 找到了让比pivot小的数字，在pivot的右边
  17.         lists[i] = lists[j]
  18.         # 向左找到比pivot大的数字
  19.         while i < j and lists[i] <= pivot:
  20.             # 指针向右移动
  21.             i += 1
  22.         # 找到了让比pivot大的数字，在pivot的左边
  23.         lists[j] = lists[i]
  24.     # 将pivot加回到列表内，使现在的lists[j] = pivot
  25.     lists[j] = pivot
  26.     # 处理比pivot小的数字，右边
  27.     quick_sort(lists, low, i - 1)
  28.     # 处理比pivot大的数字
  29.     quick_sort(lists, i + 1, high)
  30.     return lists
  31.  
  32.  
  33. if __name__ == "__main__":
  34.     lists = [random.randint(-100, 100) for i in range(10)]
  35.     print("排序前的序列为：")
  36.     for i in lists:
  37.         print(i, end=" ")
  38.     print("\n排序后的序列为：")
  39.     for i in quick_sort(lists, 0, len(lists) - 1):
  40.         print(i, end=" ")
  41.  
  42. 输出结果：
  43. 排序前的序列为：
  44. 92 -30 -92 -64 65 46 60 0 -61 93 
  45. 排序后的序列为：
  46. -92 -64 -61 -30 0 46 60 65 92 93 
  1. import random
  2. def quick_sort(data):
  3.     """快速排序"""
  4.     if len(data) >= 2:  # 递归入口及出口
  5.         mid = data[len(data) // 2]  # 选取基准值，也可以选取第一个或最后一个元素
  6.         left, right = [], []  # 定义基准值左右两侧的列表
  7.         data.remove(mid)  # 从原始数组中移除基准值
  8.         for num in data:
  9.             if num >= mid:
  10.                 right.append(num)
  11.             else:
  12.                 left.append(num)
  13.         return quick_sort(left) + [mid] + quick_sort(right)
  14.     else:
  15.         return data
  16.  
  17. print(quick_sort([random.randint(0, 100) for i in range(10)]))