首页 > 脚本中心 > Python > 关于Python八大排序实现方法(冒泡排序、快速排序等)

关于Python八大排序实现方法(冒泡排序、快速排序等)

福牛 3月 28, 2023 40 0

1.基数排序

基数排序的基本思想是先将数字按照个位数上数字的大小进行排序，排序之后再将已经排过序的数字再按照十位数上数字的大小进行排序，依次推类

  1. # 统计这个列表中数字最大的数字有几位
  2. def radix_sort_nums(nums):
  3.      max = nums[0]
  4.      for i in nums:
  5.          if max < i:
  6.              max = i
  7.      times = 0
  8.      while max > 0:
  9.          max = int(max/10)
  10.          times += 1
  11.      return times
  12.  
  13. # 每个数字各个位置的数字大小，比如（123,1）则是3，（123,2）则是2
  14. def get_num(num,n):
  15.      return (int(num/(10**(n–1)))) % 10
  16.  
  17. # 主程序
  18. def radix_sort(nums):
  19.      count = 10*[None] # 定义的数组，用于存放当前位数的元素个数
  20.      bucket = len(nums)*[None] # 用于暂时存放排序结果
  21.      # 分别从个位/十位/百位开始循环
  22.      for pos in range(1, radix_sort_nums(nums)+1):
  23.          # 每次排序完都要清空各个位数存放的数据统计
  24.          for i in range(10):
  25.              count[i] = 0
  26.  
  27.          for i in range(len(nums)):
  28.              # 获得0到9每个位数的个数
  29.              j = get_num(nums[i], pos)
  30.              count[j] = count[j]+1
  31.          # 获得相对应位数的边界值
  32.          for i in range(1, 10):
  33.              count[i] = count[i] + count[i–1]
  34.  
  35.          for i in range(len(nums)-1, –1, –1):
  36.              # 求出相应位数的数字
  37.              j = get_num(nums[i], pos)
  38.              #将元素按相应位数的上数字的大小排序
  39.              bucket[count[j]-1] = nums[i]
  40.              #让相应位数上数字相等的元素不会放在同一位置而被替代
  41.              count[j] = count[j]-1
  42.  
  43.          # 将暂时存储在bucket的元素数据返回到nums中
  44.          for i in range(0, len(nums)):
  45.              nums[i] = bucket[i]
  46.      return nums
  47.  
  48. print(radix_sort([45, 32, 8, 33, 12, 22, 19, 97]))

2.归并排序

归并排序其实是将原数列分为很多个小数列将其排序，在小数列排序完之后，再将各个小数列进行排序，最后得到一个全部有序的数列

-1

  1. # 归并排序
  2.  
  3. # 这个函数主要目的是为了实现合并并排序
  4. def mergearray(nums, first, mid, last, temp):
  5.      # i, j分别是第一个组数的第一个位置，第二组数的第一个位置
  6.      i, j, k = first, mid+1, 0
  7.      # 当俩边数组都存在数的时候，依次比较对应位置的大小
  8.      while i <= mid and j <= last:
  9.          if nums[i] <= nums[j]:
  10.              temp[k] = nums[i]
  11.              i = i+1
  12.              k = k+1
  13.          else:
  14.              temp[k] = nums[j]
  15.              j = j+1
  16.              k = k+1
  17.      # 第一组数还有多的数的情况
  18.      while i <= mid:
  19.          temp[k] = nums[i]
  20.          i = i+1
  21.          k = k+1
  22.      # 第二组数还有多的情况
  23.      while (j <= last):
  24.          temp[k] = nums[j]
  25.          j = j+1
  26.          k = k+1
  27.      # 将排列过的数组赋予nums（开始的时候只是部分有序，随着递归最后变成全部有序）
  28.      for i in range(k):
  29.          nums[first+i] = temp[i]
  30.  
  31. # 分组，利用递归
  32. def merge_sort(nums,first,last,temp):
  33.      if first < last:
  34.          mid = int((first + last) / 2)
  35.          # 分出第一组数
  36.          merge_sort(nums, first, mid, temp)
  37.          # 分出第二组数
  38.          merge_sort(nums, mid+1, last, temp)
  39.          # 合并并排序
  40.          mergearray(nums, first, mid, last, temp)
  41.  
  42. def merge_sort_array(nums):
  43.      # 创建一个和想要排序数列相同数量的空列表
  44.      temp = len(nums)*[None]
  45.      # 利用递归进行排序
  46.      merge_sort(nums, 0, len(nums)-1, temp)
  47.  
  48.  
  49. print(merge_sort_array([45, 32, 8, 33, 12, 22, 19, 97]))

3.堆排序

堆排序利用了二叉树的结构，使子节点的值一直小于根节点

  1. def big_endian(arr, start, end):
  2.      root = start
  3.      child = root * 2 + 1 # 左孩子
  4.      while child <= end:
  5.          # 孩子比最后一个节点还大，也就意味着最后一个叶子节点了，就得跳出去一次循环，已经调整完毕
  6.          if child + 1 <= end and arr[child] < arr[child + 1]:
  7.              # 为了始终让其跟子元素的较大值比较，如果右边大就左换右，左边大的话就默认
  8.              child += 1
  9.          if arr[root] < arr[child]:
  10.              # 父节点小于子节点直接交换位置，同时坐标也得换，这样下次循环可以准确判断：是否为最底层，
  11.              # 是不是调整完毕
  12.              arr[root], arr[child] = arr[child], arr[root]
  13.              root = child
  14.              child = root * 2 + 1
  15.          else:
  16.              break
  17.  
  18.  
  19. def heap_sort(nums): # 无序区大根堆排序
  20.      first = len(nums) // 2 – 1
  21.      for start in range(first, –1, –1):
  22.          # 从下到上，从左到右对每个节点进行调整，循环得到非叶子节点
  23.          big_endian(nums, start, len(nums) – 1) # 去调整所有的节点
  24.      for end in range(len(nums) – 1, 0, –1):
  25.          nums[0], nums[end] = nums[end], nums[0] # 顶部尾部互换位置
  26.          big_endian(nums, 0, end – 1) # 重新调整子节点的顺序，从顶开始调整
  27.      return nums
  28.  
  29. print(heap_sort([3, 1, 4, 9, 6, 7, 5, 8, 2, 10]))

4.简单选择排序

简单选择排序的方法则是将所选值与剩下值中比他小的值进行比较

比如选取第一个值，往后找到比他小的值就与其对调，对调后的值再接下去进行比较，直至找到最小的值，随后再第二个值……直至循环到倒数第二个值.

-2

  1. def select_sort(nums):
  2.      # 遍历所有的值
  3.      for i in range(len(nums)):
  4.          # 当前位置初始值
  5.          min = nums[i]
  6.          # 与比他后面的值进行比较，小则互换
  7.          for j in range(i+1, len(nums)):
  8.              if nums[j] < min:
  9.                  nums[j], min = min, nums[j]
  10.          # 将值返回数列
  11.          nums[i] = min
  12.      return nums
  13.  
  14. print(select_sort([45, 32, 8, 33, 12, 22, 19, 97]))

5.直接插入排序

首先遍历所有元素，随后从第一个数开始将数列从后往前遍历，如果后面的数小于前面的数，则互换位置，依次推类，直到遍历完成

  1. # 直接插入排序
  2. def insert_sort(nums):
  3.      for i in range(len(nums)-1):
  4.  
  5.          for j in range(i, –1, –1):
  6.  
  7.              if nums[j] > nums[j+1]:
  8.                  nums[j], nums[j + 1] = nums[j + 1], nums[j]
  9.  
  10.      return nums
  11.  
  12. print(insert_sort([45, 32, 8, 33, 12, 22, 19, 97]))

6.希尔排序

希尔排序其实就相当于对直接插入排序的升级版，每次都选取一半的长度，随后利用直接插入法进行排序，从而更快的获得结果

-3

  1. def insert_shell(nums):
  2.      # 初始化l值，此处利用序列长度的一半为其赋值
  3.      l = int(len(nums)/2)
  4.      # 第一层循环：依次改变l值对列表进行分组
  5.      while l >= 1:
  6.      # 下面：利用直接插入排序的思想对分组数据进行排序
  7.          for i in range(len(nums) – 1):
  8.  
  9.              for j in range(i, –1, –1):
  10.  
  11.                  if nums[j] > nums[j + 1]:
  12.                      nums[j], nums[j + 1] = nums[j + 1], nums[j]
  13.      # while循环条件折半
  14.          l = int(l/2)
  15.      return nums

7.快速排序

快速排序首先得选取一个基准值，这个代码用第一个数作为基准值，将比基准值小的值放到左边，比基准值大的值放到右边，随后再将左边后右边按照上述方法进行排序，直到完全正确为止

  1. # 实现快速排序方法的函数
  2. def quick_sort_num(nums,start,end):
  3.      if start < end:
  4.      # 定义基准值为第一个数
  5.          i, j, pivot = start, end, nums[start]
  6.          while i < j:
  7.          # 将基准数右边的数中比基准数小的放到左边
  8.              while i < j and nums[j] >= pivot:
  9.                  j = j–1
  10.              if i < j:
  11.                  nums[i] = nums[j]
  12.                  i = i+1
  13.              # 将基准数左边的数中比基准数大的数放到右边
  14.              while i < j and nums[i] < pivot:
  15.                  i = i+1
  16.              if i < j:
  17.                  nums[j] = nums[i]
  18.                  j = j–1
  19.          nums[i] = pivot
  20.          # 分别将基准数左边的数列和右边的数列进行递归
  21.          quick_sort_num(nums, start, i–1)
  22.          quick_sort_num(nums, i+1, end)
  23.      return nums
  24.  
  25. # 快速排序主体函数
  26. def quick_sort(nums):
  27.      start = 0
  28.      end = len(nums)-1
  29.      nums = quick_sort_num(nums, start, end)
  30.      return nums
  31.  
  32. print(quick_sort([45, 32, 8, 33, 12, 22, 19, 97]))

8.冒泡排序

冒泡排序是最简单的排序，依次将左右俩个元素进行比较，每次比较完最后的一个数必定是最大的，依次推类，直到全部元素都比较玩

  1. def bubble_sort(nums):
  2.      # 交换的轮数
  3.      for i in range(len(nums) – 1):
  4.      # 每一轮交换
  5.          for j in range(len(nums) – i – 1):
  6.          # 比较值，并根据大小进行互换
  7.              if nums[j] > nums[j + 1]:
  8.                  nums[j], nums[j + 1] = nums[j + 1], nums[j]
  9.  
  10.      return nums
  11.  
  12. print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))

9.时间测试

我们先创建一个列表，列表中有10000条数据，随后用相同的数据进行测试

  1. import random
  2. lis = []
  3. for i in range(10000):
  4.      i = random.randint(0,500)
  5.      lis.append(i)
  6.  
  7. print(lis)

创出来的数据就不进行展示了。。

随后我们进行测试：

  1. 冒泡排序法：11.535502672195435
  2.  
  3. 直接插入排序法：12.057243585586548
  4.  
  5. 希尔排序法：86.3020749092102（大概是我的方法不大好吧，我差点以为他排不出来了）
  6.  
  7. 基数排序法：0.051932334899902344（老大哥就是牛皮）
  8.  
  9. 归并排序法：0.08577108383178711（233）
  10.  
  11. 快速排序：0.04795527458190918
  12.  
  13. 堆排序：0.09175491333007812

根据自己的测试，基数排序，归并排序，快速排序，和堆排序速度很快，感觉随着代码量的增长时间增长很慢，其余的几个则不尽如人意了

到此这篇关于关于python八大排序实现方法(冒泡排序、快速排序等)的文章就介绍到这了,更多相关Python八大排序实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

标签

相关推荐

发表评论