快捷導(dǎo)航

python實(shí)現(xiàn)經(jīng)典排序算法的示例代碼

更新時(shí)間：2021年02月07日 08:37:28 作者：Xlgd

這篇文章主要介紹了python實(shí)現(xiàn)經(jīng)典排序算法的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

以下排序算法最終結(jié)果都默認(rèn)為升序排列，實(shí)現(xiàn)簡(jiǎn)單，沒有考慮特殊情況，實(shí)現(xiàn)僅表達(dá)了算法的基本思想。

冒泡排序

內(nèi)層循環(huán)中相鄰的元素被依次比較，內(nèi)層循環(huán)第一次結(jié)束后會(huì)將最大的元素移到序列最右邊，第二次結(jié)束后會(huì)將次大的元素移到最大元素的左邊，每次內(nèi)層循環(huán)結(jié)束都會(huì)將一個(gè)元素排好序。

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

選擇排序

每次內(nèi)層循環(huán)都會(huì)得到一個(gè)當(dāng)前最小的元素，并將其放到合適的位置。內(nèi)層循環(huán)第一次結(jié)束后會(huì)將最小的元素交換到序列首位，第二次結(jié)束后會(huì)將第二小的元素交換到序列第二位，每次內(nèi)層循環(huán)結(jié)束后都會(huì)將一個(gè)元素放在正確的順序位置。

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

插入排序

類比玩撲克牌時(shí)理牌的思想，從第一個(gè)元素開始，假設(shè)它是已經(jīng)排好序的。然后開始處理第二個(gè)元素，如果比第一個(gè)元素小，則將其放到第一個(gè)元素左邊，否則放在其右邊，那么現(xiàn)在前兩個(gè)元素以及排好序了，之后再依次處理剩余的元素。

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

希爾排序

希爾排序就是將插入排序的改進(jìn)版本。插入排序中每次逐步比較元素，而希爾排序中則是從一個(gè)較大的步數(shù)開始比較，最后減小到一步。

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

歸并排序

先將序列前半部分排好序，再將序列后半部分排好序，之后再將這兩部分合并得到最終的序列，具體實(shí)現(xiàn)為遞歸地將序列分為兩部分，分別排序后再合并。

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:]))

快速排序

取一個(gè)元素，將比它小的元素都移到它左側(cè)，將比它大的元素都移到它右側(cè)，并遞歸地處理它左側(cè)的序列和右側(cè)的序列。

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

堆排序

首先構(gòu)建一個(gè)最大堆，最大堆的性質(zhì)是父節(jié)點(diǎn)的值總是大于其左右子節(jié)點(diǎn)的值，那么此時(shí)根節(jié)點(diǎn)的值是最大的，則將其移到序列的最右邊。之后將堆中當(dāng)前最后一個(gè)葉節(jié)點(diǎn)移到根節(jié)點(diǎn)上，因?yàn)檫@可能會(huì)不符合最大堆的性質(zhì)，所以會(huì)進(jìn)行調(diào)整，將它與其左右子節(jié)點(diǎn)中最大的值進(jìn)行交換，則相當(dāng)于將葉節(jié)點(diǎn)向下移動(dòng)，交換過后如果還是不符合性質(zhì)，則繼續(xù)進(jìn)行交換，直到符合性質(zhì)后，此時(shí)的根節(jié)點(diǎn)的值就是當(dāng)前堆中的最大值，將其取出放入序列中正確的位置后繼續(xù)上述流程處理剩下的節(jié)點(diǎn)。

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

計(jì)數(shù)排序

將序列中的元素按照其值放入相應(yīng)的桶中，之后再按照桶的順序取出即可，計(jì)數(shù)排序不需要比較操作。

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

桶排序

類別計(jì)數(shù)排序，構(gòu)造很多桶，但每個(gè)桶中能放入值在特定范圍內(nèi)的元素，將序列中的元素按照要求放入各個(gè)桶中，再將每個(gè)桶中的元素進(jìn)行排序，最后按照桶的順序和各個(gè)桶中元素的順序得到最終序列。

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

基數(shù)排序

按照元素值的特定位進(jìn)行排序，從低位到高位分別進(jìn)行排序。

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

上述代碼放在這里