DDR爱好者之家

python实现经典排序算法的示例代码
站长资源 2024/11/24 佚名
68 1538
DDR爱好者之家 Design By 杰米

以下排序算法最终结果都默认为升序排列，实现简单，没有考虑特殊情况，实现仅表达了算法的基本思想。

冒泡排序

内层循环中相邻的元素被依次比较，内层循环第一次结束后会将最大的元素移到序列最右边，第二次结束后会将次大的元素移到最大元素的左边，每次内层循环结束都会将一个元素排好序。

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

选择排序

每次内层循环都会得到一个当前最小的元素，并将其放到合适的位置。内层循环第一次结束后会将最小的元素交换到序列首位，第二次结束后会将第二小的元素交换到序列第二位，每次内层循环结束后都会将一个元素放在正确的顺序位置。

def selection_sort(arr):
  length = len(arr)
  for i in range(length):
    min_index = i
    for j in range(i + 1, length):
      if arr[j] < arr[min_index]:
        min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
  return arr

插入排序

类比玩扑克牌时理牌的思想，从第一个元素开始，假设它是已经排好序的。然后开始处理第二个元素，如果比第一个元素小，则将其放到第一个元素左边，否则放在其右边，那么现在前两个元素以及排好序了，之后再依次处理剩余的元素。

def insertion_sort(arr):
  length = len(arr)
  for i in range(1, length):
    pre = i - 1
    current_value = arr[i]
    while pre >= 0 and arr[pre] > current_value:
      arr[pre + 1] = arr[pre]
      pre -= 1
    arr[pre+1] = current_value
  return arr

希尔排序

希尔排序就是将插入排序的改进版本。插入排序中每次逐步比较元素，而希尔排序中则是从一个较大的步数开始比较，最后减小到一步。

def shell_sort(arr):
  length = len(arr)
  gap = length // 2
  while gap > 0:
    for i in range(gap, length):
      pre = i - gap
      current_value = arr[i]
      while pre >= 0 and arr[pre] > current_value:
        arr[pre + gap] = arr[pre]
        pre -= gap
      arr[pre + gap] = current_value
    gap = gap // 2
  return arr

归并排序

先将序列前半部分排好序，再将序列后半部分排好序，之后再将这两部分合并得到最终的序列，具体实现为递归地将序列分为两部分，分别排序后再合并。

def merge(left, right):
  result = []
  while len(left) > 0 and len(right) > 0:
    if left[0] < right[0]:
      result.append(left.pop(0))
    else:
      result.append(right.pop(0))
  if len(left) > 0:
    result.extend(left[:])
  if len(right) > 0:
    result.extend(right[:])
  return result


def merge_sort(arr):
  if len(arr) < 2:
    return arr
  middle = len(arr) // 2
  return merge(merge_sort(arr[:middle]), merge_sort(arr[middle:]))

快速排序

取一个元素，将比它小的元素都移到它左侧，将比它大的元素都移到它右侧，并递归地处理它左侧的序列和右侧的序列。

def partition(arr, left=None, right=None):
  pivot = left
  index = pivot + 1
  for i in range(index, right + 1):
    if arr[i] < arr[pivot]:
      arr[i], arr[index] = arr[index], arr[i]
      index += 1
  arr[pivot], arr[index - 1] = arr[index - 1], arr[pivot]
  return index - 1


def quick_sort(arr, left=None, right=None):
  left = 0 if left is None else left
  right = len(arr) - 1 if right is None else right
  if left < right:
    partition_index = partition(arr, left, right)
    quick_sort(arr, left, partition_index - 1)
    quick_sort(arr, partition_index + 1, right)
  return arr

堆排序

首先构建一个最大堆，最大堆的性质是父节点的值总是大于其左右子节点的值，那么此时根节点的值是最大的，则将其移到序列的最右边。之后将堆中当前最后一个叶节点移到根节点上，因为这可能会不符合最大堆的性质，所以会进行调整，将它与其左右子节点中最大的值进行交换，则相当于将叶节点向下移动，交换过后如果还是不符合性质，则继续进行交换，直到符合性质后，此时的根节点的值就是当前堆中的最大值，将其取出放入序列中正确的位置后继续上述流程处理剩下的节点。

global length2


def heapify(arr, i):
  left = 2 * i + 1
  right = 2 * i + 2
  largest = i
  if left < length2 and arr[left] > arr[largest]:
    largest = left
  if right < length2 and arr[right] > arr[largest]:
    largest = right
  if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, largest)


def build_max_heap(arr):
  for i in range(len(arr) // 2, -1, -1):
    heapify(arr, i)


def heap_sort(arr):
  global length2
  length2 = len(arr)
  build_max_heap(arr)
  for i in range(len(arr) - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    length2 -= 1
    heapify(arr, 0)
  return arr

计数排序

将序列中的元素按照其值放入相应的桶中，之后再按照桶的顺序取出即可，计数排序不需要比较操作。

def counting_sort(arr):
  max_value = max(arr)
  buckets = [0] * (max_value + 1)
  index = 0
  length = len(arr)
  for i in range(length):
    buckets[arr[i]] += 1
  for j in range(max_value + 1):
    while buckets[j] > 0:
      arr[index] = j
      index += 1
      buckets[j] -= 1
  return arr

桶排序

类别计数排序，构造很多桶，但每个桶中能放入值在特定范围内的元素，将序列中的元素按照要求放入各个桶中，再将每个桶中的元素进行排序，最后按照桶的顺序和各个桶中元素的顺序得到最终序列。

def bucket_sort(arr):
  bucket_size = 5
  max_value = max(arr)
  min_value = min(arr)
  bucket_num = (max_value - min_value) // bucket_size + 1
  buckets = {i: [] for i in range(bucket_num)}
  for i in range(len(arr)):
    buckets[(arr[i] - min_value) // bucket_size].append(arr[i])
  result = []
  for i in range(bucket_num):
    insertion_sort(buckets[i])
    result.extend(buckets[i])
  return result

基数排序

按照元素值的特定位进行排序，从低位到高位分别进行排序。

def radix_sort(arr):
  max_value = max(arr)
  max_digit = len(str(max_value))
  dev = 1
  mod = 10
  result = arr[:]
  for i in range(max_digit):
    buckets = {i: [] for i in range(mod)}
    for k in range(len(result)):
      key = (result[k] % mod) // dev
      buckets[key].append(result[k])
    result = []
    for j in range(mod):
      result.extend(buckets[j])
    dev *= 10
    mod *= 10
  return result

上述代码放在 这里

参考

  • https://www.cnblogs.com/onepixel/p/7674659.html
  • 算法导论
  • 菜鸟教程
DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米