python实现经典排序算法的示例代码

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

冒泡排序

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

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

上述代码放在 这里

参考

到此这篇关于python实现经典排序算法的示例代码的文章就介绍到这了,更多相关python 经典排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • python 实现堆排序算法代码

    复制代码 代码如下: #!/usr/bin/python import sys def left_child(node): return node * 2 + 1 def right_child(node): return node * 2 + 2 def parent(node): if (node % 2): return (i - 1) / 2 else: return (i - 2) / 2 def max_heapify(array, i, heap_size): l = left_c

  • python简单实现基数排序算法

    本文实例讲述了python简单实现基数排序算法.分享给大家供大家参考.具体实现方法如下: from random import randint def main(): A = [randint(1, 99999999) for _ in xrange(9999)] for k in xrange(8): S = [ [] for _ in xrange(10)] for j in A: S[j / (10 ** k) % 10].append(j) A = [a for b in S for a

  • 基于python的七种经典排序算法(推荐)

    一.排序的基本概念和分类 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作.排序算法,就是如何使得记录按照要求排列的方法. 排序的稳定性: 经过某种排序后,如果两个记录序号同等,且两者在原无序记录中的先后秩序依然保持不变,则称所使用的排序方法是稳定的,反之是不稳定的. 内排序和外排序 内排序:排序过程中,待排序的所有记录全部放在内存中 外排序:排序过程中,使用到了外部存储. 通常讨论的都是内排序. 影响内排序算法性能的三个因素: 时间复杂度:即时间性能,高效

  • Python编程中归并排序算法的实现步骤详解

    基本思想:归并排序是一种典型的分治思想,把一个无序列表一分为二,对每个子序列再一分为二,继续下去,直到无法再进行划分为止.然后,就开始合并的过程,对每个子序列和另外一个子序列的元素进行比较,依次把小元素放入结果序列中进行合并,最终完成归并排序. 归并操作过程: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针达到序列尾

  • python 实现插入排序算法

    复制代码 代码如下: #!/usr/bin/python def insert_sort(array): for i in range(1, len(array)): key = array[i] j = i - 1 while j >= 0 and key < array[j]: array[j + 1] = array[j] j-=1 array[j + 1] = key if __name__ == "__main__": array = [2, 4, 32, 64,

  • python实现的各种排序算法代码

    复制代码 代码如下: # -*- coding: utf-8 -*-# 测试各种排序算法# link:www.jb51.net# date:2013/2/2 #选择排序def select_sort(sort_array):    for i, elem in enumerate(sort_array):        for j, elem in enumerate(sort_array[i:]):            if sort_array[i] > sort_array[j + i]

  • 八大排序算法的Python实现

    Python实现八大排序算法,具体内容如下 1.插入排序 描述 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法.插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 代码实现 def inser

  • python实现冒泡排序算法的两种方法

    什么是冒泡排序? 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端,故名冒泡排序. 以上是百度词条对冒泡排序的官方解释. 但是我要说一下我的个人理解,我觉得冒泡排序的核心思想是:每次比较两个数,如果他们顺序错误(大于或者小于),那么就把

  • python冒泡排序算法的实现代码

    1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

  • Python实现的直接插入排序算法示例

    本文实例讲述了Python实现的直接插入排序算法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- '''直接插入的python实现 时间复杂度O(n**2) 空间复杂度O(1) 稳定 思想:先将前两个元素排序,第三个元素插入前面已排好序列, 后面的元素依次插入之前已经排好序的序列 ''' author = 'Leo Howell' L = [89,67,56,45,34,23,1] def direct_insert_sort(numbers): for i in

随机推荐