欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實現(xiàn)八大排序算法

 更新時間:2016年08月13日 09:09:08   投稿:lijiao  
這篇文章主要介紹了Python實現(xiàn)八大排序算法,如何用Python實現(xiàn)八大排序算法,感興趣的小伙伴們可以參考一下

如何用Python實現(xiàn)八大排序算法

1、插入排序
描述
插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個新的、個數(shù)加一的有序數(shù)據(jù),算法適用于少量數(shù)據(jù)的排序,時間復(fù)雜度為 O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分:第一部分包含了這個數(shù)組的所有元素,但將最后一個元素除外(讓數(shù)組多一個空間才有插 入的位置),而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成后,再將這個最后元素插入到已排好序的第一部分中。
代碼實現(xiàn)

 def insert_sort(lists): 
  # 插入排序 
  count = len(lists) 
  for i in range(1, count): 
    key = lists[i] 
    j = i - 1 
    while j >= 0: 
      if lists[j] > key: 
        lists[j + 1] = lists[j] 
        lists[j] = key 
      j -= 1 
  return lists 

2、希爾排序
描述 
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序,是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。該方法因DL.Shell于 1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組,對每組使用直接插入排序算法排序;隨著增量逐漸減少,每組包含的關(guān)鍵詞越來越多,當增量減至1時,整個文件恰被分 成一組,算法便終止。 
代碼實現(xiàn)

 def shell_sort(lists): 
  # 希爾排序 
  count = len(lists) 
  step = 2 
  group = count / step 
  while group > 0: 
    for i in range(0, group): 
      j = i + group 
      while j < count: 
        k = j - group 
        key = lists[j] 
        while k >= 0: 
          if lists[k] > key: 
            lists[k + group] = lists[k] 
            lists[k] = key 
          k -= group 
        j += group 
    group /= step 
  return lists 

3、冒泡排序
描述 
它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成。
代碼實現(xiàn)

 def bubble_sort(lists): 
  # 冒泡排序 
  count = len(lists) 
  for i in range(0, count): 
    for j in range(i + 1, count): 
      if lists[i] > lists[j]: 
        lists[i], lists[j] = lists[j], lists[i] 
  return lists 

4、快速排序
描述 
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數(shù)據(jù)變成有序序列。 
代碼實現(xiàn)

 def quick_sort(lists, left, right): 
  # 快速排序 
  if left >= right: 
    return lists 
  key = lists[left] 
  low = left 
  high = right 
  while left < right: 
    while left < right and lists[right] >= key: 
      right -= 1 
    lists[left] = lists[right] 
    while left < right and lists[left] <= key: 
      left += 1 
    lists[right] = lists[left] 
  lists[right] = key 
  quick_sort(lists, low, left - 1) 
  quick_sort(lists, left + 1, high) 
  return lists 

5、直接選擇排序
描述 
基本思想:第1趟,在待排序記錄r1 ~ r[n]中選出最小的記錄,將它與r1交換;第2趟,在待排序記錄r2 ~ r[n]中選出最小的記錄,將它與r2交換;以此類推,第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄,將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。
代碼實現(xiàn)

 def select_sort(lists): 
  # 選擇排序 
  count = len(lists) 
  for i in range(0, count): 
    min = i 
    for j in range(i + 1, count): 
      if lists[min] > lists[j]: 
        min = j 
    lists[min], lists[i] = lists[i], lists[min] 
  return lists 

6、堆排序
描述 
堆排序(Heapsort)是指利用堆積樹(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法,它是選擇排序的一種??梢岳脭?shù)組的特點快速定位指定索引的元 素。堆分為大根堆和小根堆,是完全二叉樹。大根堆的要求是每個節(jié)點的值都不大于其父節(jié)點的值,即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中,需要使用的就是大根堆,因為根據(jù)大根堆的要求可知,最大的值一定在堆頂。 
代碼實現(xiàn)

 # 調(diào)整堆 
def adjust_heap(lists, i, size): 
  lchild = 2 * i + 1 
  rchild = 2 * i + 2 
  max = i 
  if i < size / 2: 
    if lchild < size and lists[lchild] > lists[max]: 
      max = lchild 
    if rchild < size and lists[rchild] > lists[max]: 
      max = rchild 
    if max != i: 
      lists[max], lists[i] = lists[i], lists[max] 
      adjust_heap(lists, max, size) 
 
# 創(chuàng)建堆 
def build_heap(lists, size): 
  for i in range(0, (size/2))[::-1]: 
    adjust_heap(lists, i, size) 
 
# 堆排序 
def heap_sort(lists): 
  size = len(lists) 
  build_heap(lists, size) 
  for i in range(0, size)[::-1]: 
    lists[0], lists[i] = lists[i], lists[0] 
    adjust_heap(lists, 0, i) 

7、歸并排序
描述 
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應(yīng)用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一 個有序表,稱為二路歸并。 
歸并過程為:比較a[i]和a[j]的大小,若a[i]≤a[j],則將第一個有序表中的元素a[i]復(fù)制到r[k]中,并令i和k分別加上1;否 則將第二個有序表中的元素a[j]復(fù)制到r[k]中,并令j和k分別加上1,如此循環(huán)下去,直到其中一個有序表取完,然后再將另一個有序表中剩余的元素復(fù) 制到r中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現(xiàn),先把待排序區(qū)間[s,t]以中點二分,接著把左邊子區(qū)間排序,再把右邊子區(qū)間排序, 最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。 
代碼實現(xiàn)

 def merge(left, right): 
  i, j = 0, 0 
  result = [] 
  while i < len(left) and j < len(right): 
    if left[i] <= right[j]: 
      result.append(left[i]) 
      i += 1 
    else: 
      result.append(right[j]) 
      j += 1 
  result += left[i:] 
  result += right[j:] 
  return result 
 
def merge_sort(lists): 
  # 歸并排序 
  if len(lists) <= 1: 
    return lists 
  num = len(lists) / 2 
  left = merge_sort(lists[:num]) 
  right = merge_sort(lists[num:]) 
  return merge(left, right) 

8、基數(shù)排序
描述 
基數(shù)排序(radix sort)屬于“分配式排序”(distribution sort),又稱“桶子法”(bucket sort)或bin sort,顧名思義,它是透過鍵值的部份資訊,將要排序的元素分配至某些“桶”中,藉以達到排序的作用,基數(shù)排序法是屬于穩(wěn)定性的排序,其時間復(fù)雜度為O (nlog(r)m),其中r為所采取的基數(shù),而m為堆數(shù),在某些時候,基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
代碼實現(xiàn)

 import math 
def radix_sort(lists, radix=10): 
  k = int(math.ceil(math.log(max(lists), radix))) 
  bucket = [[] for i in range(radix)] 
  for i in range(1, k+1): 
    for j in lists: 
      bucket[j/(radix**(i-1)) % (radix**i)].append(j) 
    del lists[:] 
    for z in bucket: 
      lists += z 
      del z[:] 
  return lists

以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • PyQt使用QPropertyAnimation開發(fā)簡單動畫

    PyQt使用QPropertyAnimation開發(fā)簡單動畫

    這篇文章主要介紹了PyQt使用QPropertyAnimation開發(fā)簡單動畫,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-04-04
  • 舉例講解Python設(shè)計模式編程的代理模式與抽象工廠模式

    舉例講解Python設(shè)計模式編程的代理模式與抽象工廠模式

    這篇文章主要介紹了Python編程的代理模式與抽象工廠模式,文中舉了兩個簡單的小例子來說明這兩種設(shè)計模式的思路在Python編程中的體現(xiàn),需要的朋友可以參考下
    2016-01-01
  • 基于Python中的turtle繪畫星星和星空

    基于Python中的turtle繪畫星星和星空

    這篇文章主要介紹了基于Python中的turtle繪畫星星和星空,turtle?是?Python?中自帶的繪圖模塊,下文章關(guān)于turtle繪畫星星和星空的詳細內(nèi)容,需要的朋友可以參考一下,可以當作學習小練習
    2022-03-03
  • PyQt5+serial模塊實現(xiàn)一個串口小工具

    PyQt5+serial模塊實現(xiàn)一個串口小工具

    這篇文章主要為大家詳細介紹了如何利用PyQt5和serial模塊實現(xiàn)一個簡單的串口小工具,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下
    2023-01-01
  • Python樹的重建實現(xiàn)示例

    Python樹的重建實現(xiàn)示例

    樹的重建是一種從給定的遍歷序列中恢復(fù)原樹結(jié)構(gòu)的算法,本文就來介紹一下Python樹的重建實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下
    2023-11-11
  • python 中os模塊os.path.exists()的用法說明

    python 中os模塊os.path.exists()的用法說明

    這篇文章主要介紹了python 中os模塊os.path.exists()的用法說明,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-03-03
  • OpenCV-Python實現(xiàn)油畫效果的實例

    OpenCV-Python實現(xiàn)油畫效果的實例

    OpenCV是功能強大的計算機視覺庫,本文主要使用OpenCV來實現(xiàn)圖片的油畫效果,需要的朋友們下面隨著小編來一起學習學習吧
    2021-06-06
  • python+PyQT實現(xiàn)系統(tǒng)桌面時鐘

    python+PyQT實現(xiàn)系統(tǒng)桌面時鐘

    這篇文章主要為大家詳細介紹了python+PyQT實現(xiàn)系統(tǒng)桌面時鐘,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-11-11
  • TOPI如何使TVM代碼不那么樣板化

    TOPI如何使TVM代碼不那么樣板化

    這篇文章主要為大家介紹了TOPI如何使TVM代碼不那么樣板化實現(xiàn)過程詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-04-04
  • Python動態(tài)賦值的陷阱知識點總結(jié)

    Python動態(tài)賦值的陷阱知識點總結(jié)

    在本文中我們給大家整理了關(guān)于Python動態(tài)賦值的陷阱的相關(guān)知識點內(nèi)容,需要的朋友們學習下。
    2019-03-03

最新評論