python之八大排序方法

来源:http://www.cnblogs.com/MrFiona/archive/2016/10/19/5978491.html
-Advertisement-
Play Games

一、插入排序 1 #-*- coding:utf-8 -*- 2 ''' 3 描述 4 插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據,演算法適用於少量數據的排序,時間複雜度為O(n^2)。 5 是穩定的排序方法。插入演算法把要排序的數組分成兩部分:第 ...


一、插入排序

 1 #-*- coding:utf-8 -*-
 2 '''
 3 描述
 4 插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據,演算法適用於少量數據的排序,時間複雜度為O(n^2)。
 5 是穩定的排序方法。插入演算法把要排序的數組分成兩部分:第一部分包含了這個數組的所有元素,但將最後一個元素除外(讓數組多一個空間才有插入的位置),
 6 而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後,再將這個最後元素插入到已排好序的第一部分中
 7 '''
 8 def insert_sort(lists):
 9     count = len(lists)
10     for i in range(1, count):
11         key = lists[i]
12         j = i - 1
13         while j >= 0:
14             if lists[j] > key:
15                 lists[j + 1] = lists[j]
16                 lists[j] = key
17             j -= 1
18     return lists
19 
20 lst1 = raw_input().split()
21 lst = [int(i) for i in lst1]
22 #lst = input()
23 insert_sort(lst)
24 for i in range(len(lst)):
25     print lst[i],
View Code

 

二、希爾排序

 1 #-*- coding:utf8 -*-
 2 '''
 3 描述
 4 希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序,是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。
 5 該方法因DL.Shell於1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組,對每組使用直接插入排序演算法排序;隨著增量逐漸減少,
 6 每組包含的關鍵詞越來越多,當增量減至1時,整個文件恰被分成一組,演算法便終止。
 7 '''
 8 def shell_sort(lists):
 9     count = len(lists)
10     step = 2
11     group = count / step
12     while group > 0:
13         for i in range(group):
14             j = i + group
15             while j < count:
16                 k = j - group
17                 key = lists[j]
18                 while k >= 0:
19                     if lists[k] > key:
20                         lists[k + group] = lists[k]
21                         lists[k] = key
22                     k -= group
23                 j += group
24         group /= step
25     return lists
26 
27 lst1 = raw_input().split()
28 lst = [int(i) for i in lst1]
29 #lst = input()
30 shell_sort(lst)
31 for i in range(len(lst)):
32     print lst[i],
View Code

 

三、冒泡排序

 1 #-*- coding:utf8 -*-
 2 '''
 3 描述
 4 它重覆地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。
 5 走訪數列的工作是重覆地進行直到沒有再需要交換,也就是說該數列已經排序完成。
 6 '''
 7 def bubble_sort(lists):
 8     count = len(lists)
 9     for i in range(count):
10         for j in range(i + 1, count):
11             if lists[i] > lists[j]:
12                 lists[i], lists[j] = lists[j], lists[i]
13     return lists
14 
15 lst1 = raw_input().split()
16 lst = [int(i) for i in lst1]
17 #lst = input()
18 bubble_sort(lst)
19 for i in range(len(lst)):
20     print lst[i],
View Code

 

四、直接選擇排序

 1 #-*- coding:utf8 -*-
 2 '''
 3 描述
 4 基本思想:第1趟,在待排序記錄r1 ~ r[n]中選出最小的記錄,將它與r1交換;第2趟,在待排序記錄r2 ~ r[n]中選出最小的記錄,將它與r2交換;
 5 以此類推,第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄,將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。
 6 '''
 7 def select_sort(lists):
 8     count = len(lists)
 9     for i in range(count):
10         min = i
11         for j in range(i + 1, count):
12             if lists[min] > lists[j]:
13                 min = j
14         lists[min], lists[i] = lists[i], lists[min]
15     return lists
16 
17 lst1 = raw_input().split()
18 lst = [int(i) for i in lst1]
19 #lst = input()
20 select_sort(lst)
21 for i in range(len(lst)):
22     print lst[i],
View Code

 

五、快速排序

 1 #-*- coding:utf8 -*-
 2 '''
 3 描述(利用遞歸,效率較低,較難理解)
 4 通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,
 5 然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。
 6 '''
 7 def quick_sort(lists, left, right):
 8     if left >= right:
 9         return lists
10     key = lists[left]
11     low = left
12     high = right
13     while left < right:
14         while left < right and lists[right] >= key:
15             right -= 1
16         lists[left] = lists[right]
17         while left < right and lists[left] <= key:
18             left += 1
19         lists[right] = lists[left]
20     lists[right] = key
21     quick_sort(lists, low, left - 1)
22     quick_sort(lists, left + 1, high)
23     return lists
24 
25 lst1 = raw_input().split()
26 lst = [int(i) for i in lst1]
27 #lst = input()
28 quick_sort(lst,0,len(lst)-1)
29 for i in range(len(lst)):
30     print lst[i],
View Code

 

六、堆排序

 1 #-*- coding:utf8 -*-
 2 '''
 3 描述(較難理解)
 4 堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序演算法,它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。
 5 堆分為大根堆和小根堆,是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值,即A[PARENT[i]] >= A[i]。
 6 在數組的非降序排序中,需要使用的就是大根堆,因為根據大根堆的要求可知,最大的值一定在堆頂。
 7 '''
 8 # 調整堆
 9 def adjust_heap(lists, i, size):
10     lchild = 2 * i + 1
11     rchild = 2 * i + 2
12     max = i
13     if i < size / 2:
14         if lchild < size and lists[lchild] > lists[max]:
15             max = lchild
16         if rchild < size and lists[rchild] > lists[max]:
17             max = rchild
18         if max != i:
19             lists[max], lists[i] = lists[i], lists[max]
20             adjust_heap(lists, max, size)
21 
22 # 創建堆
23 def build_heap(lists, size):
24     for i in range(0, (size/2))[::-1]:
25         adjust_heap(lists, i, size)
26 
27 # 堆排序
28 def heap_sort(lists):
29     size = len(lists)
30     build_heap(lists, size)
31     for i in range(0, size)[::-1]:
32         lists[0], lists[i] = lists[i], lists[0]
33         adjust_heap(lists, 0, i)
34 
35 lst1 = raw_input().split()
36 lst = [int(i) for i in lst1]
37 #lst = input()
38 heap_sort(lst)
39 for i in range(len(lst)):
40     print lst[i],
View Code

 

七、歸併排序

 1 #-*- coding:utf8 -*-
 2 '''
 3 描述(利用遞歸)
 4 歸併排序是建立在歸併操作上的一種有效的排序演算法,該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併,得到完全有序的序列;
 5 即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合併成一個有序表,稱為二路歸併。
 6 歸併過程為:比較a[i]和a[j]的大小,若a[i]≤a[j],則將第一個有序表中的元素a[i]複製到r[k]中,並令i和k分別加上1;否則將第二個有序表中的元素a[j]複製到r[k]中,
 7 並令j和k分別加上1,如此迴圈下去,直到其中一個有序表取完,然後再將另一個有序表中剩餘的元素複製到r中從下標k到下標t的單元。歸併排序的演算法我們通常用遞歸實現,
 8 先把待排序區間[s,t]以中點二分,接著把左邊子區間排序,再把右邊子區間排序,最後把左區間和右區間用一次歸併操作合併成有序的區間[s,t]。
 9 '''
10 def merge(left, right):
11     #合併過程
12     i, j = 0, 0
13     result = []
14     while i < len(left) and j < len(right):
15         if left[i] <= right[j]:
16             result.append(left[i])
17             i += 1
18         else:
19             result.append(right[j])
20             j += 1
21     result.extend(left[i:])
22     result.extend(right[j:])
23     return result
24 
25 def merge_sort(lists):
26     if len(lists) <= 1:
27         return lists
28     mid = len(lists) / 2
29     left = merge_sort(lists[:mid])
30     right = merge_sort(lists[mid:])
31     return merge(left, right)
32 
33 lst1 = raw_input().split()
34 lst = [int(i) for i in lst1]
35 #lst = input()
36 tt = merge_sort(lst)
37 for i in range(len(tt)):
38     print tt[i],
View Code

 

八、基數排序

 1 #-*- coding:utf8 -*-
 2 '''
 3 描述(表示沒接觸過,第一次聽說)
 4 基數排序(radix sort)屬於“分配式排序”(distribution sort),又稱“桶子法”(bucket sort)或bin sort,顧名思義,它是透過鍵值的部份資訊,
 5 將要排序的元素分配至某些“桶”中,藉以達到排序的作用,基數排序法是屬於穩定性的排序,其時間複雜度為O (nlog(r)m),
 6 其中r為所採取的基數,而m為堆數,在某些時候,基數排序法的效率高於其它的穩定性排序法。
 7 '''
 8 import math
 9 def radix_sort(lists, radix=10):
10     k = int(math.ceil(math.log(max(lists), radix)))
11     bucket = [[] for i in range(radix)]
12     for i in range(1, k+1):
13         for j in lists:
14             bucket[j/(radix**(i-1)) % (radix**i)].append(j)
15         del lists[:]
16         for z in bucket:
17             lists += z
18             del z[:]
19     return lists
20 
21 lst1 = raw_input().split()
22 lst = [int(i) for i in lst1]
23 #lst = input()
24 radix_sort(lst)
25 for i in range(len(lst)):
26     print lst[i],
View Code

下麵附一下各個排序演算法的時間複雜度以及穩定性比較:

 

平均速度最快的排序演算法是? 排序方法        平均情況        最好情況        最壞情況        輔助空間        穩定性 冒泡排序        O(n^2)         O(n)             O(n^2)           O(1)           穩定 選擇排序        O(n^2)         O(n^2)         O(n^2)           O(1)          不穩定 插入排序        O(n^2)         O(n)             O(n^2)           O(1)           穩定 希爾排序O(n*log(n))~O(n^2) O(n^1.3)     O(n^2)           O(1)          不穩定 堆排序         O(n*log(n))    O(n*log(n))    O(n*log(n))     O(1)           不穩定 歸併排序      O(n*log(n))    O(n*log(n))    O(n*log(n))     O(n)             穩定 快速排序      O(n*log(n))    O(n*log(n))    O(n^2)           O(1)           不穩定   冒泡排序經過優化以後,最好時間複雜度可以達到O(n)。設置一個標誌位,如果有一趟比較中沒有發生任何交換,可提前結束,因此在正序情況下,時間複雜度為O(n)。選擇排序在最壞和最好情況下,都必須在剩餘的序列中選擇最小(大)的數,與已排好序的序列後一個位置元素做交換,依次最好和最壞時間複雜度均為O(n^2)。插入排序是在把已排好序的序列的後一個元素插入到前面已排好序(需要選擇合適的位置)的序列中,在正序情況下時間複雜度為O(n)。堆是完全二叉樹,因此樹的深度一定是log(n)+1,最好和最壞時間複雜度均為O(n*log(n))。歸併排序是將大數組分為兩個小數組,依次遞歸,相當於二叉樹,深度為log(n)+1,因此最好和最壞時間複雜度都是O(n*log(n))。快速排序在正序或逆序情況下,每次劃分只得到比上一次劃分少一個記錄的子序列,用遞歸樹畫出來,是一棵斜樹,此時需要n-1次遞歸,且第i次劃分要經過n-i次關鍵字比較才能找到第i個記錄,因此時間複雜度是\sum_{i=1}^{n-1}(n-i)=n(n-1)/2,即O(n^2)。
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 首先,說明一下多線程的應用場景:當python處理多個任務時,這些任務本質是非同步的,需要有多個併發事務,各個事務的運行順序可以是不確定的、隨機的、不可預測的。計算密集型的任務可以順序執行分隔成的多個子任務,也可以用多線程的方式處理。但I/O密集型的任務就不好以單線程方式處理了,如果不用多線程,只能用 ...
  • 在現實生活中,記錄日誌非常重要。銀行轉賬時會有轉賬記錄;飛機飛行過程中,會有黑盒子(飛行數據記錄器)記錄飛行過程中的一切。如果有出現什麼問題,人們可以通過日誌數據來搞清楚到底發生了什麼。對於系統開發、調試以及運行,記錄日誌都是同樣的重要。如果沒有日誌記錄,程式崩潰時你幾乎就沒辦法弄明白到底發生了什麼 ...
  • 內置對象:不需要預先聲明就可以在腳本代碼和表達式中隨意使用,有以下特點 1.由JSP規範提供,不用編寫者實例化 2.提供Web容器實現和管理 3.所有JSP頁面均可用 4.只有在腳本元素的表達式或者代碼中才可使用(<%=使用內置對象%>或<%使用內置對象%>) 輸入輸出對象:request,resp ...
  • JavaWeb_day01 HTTP協議 HTTP(HyperText Transfer Protocol)超文本傳輸協議,是TCP/IP的應用層協議,用於定義WEB瀏覽器與WEB伺服器之間交換數據的過程以及數據本身的格式. Http協議版本號 : HTTP/1.0 HTTP/1.1 交互步驟 : ...
  • JList想添加元素,可以執行將所有元素在JList初始化時加入的靜態操作,也可以利用“列表模型”DefaultListModel處理所有列表修改細節的動態操作。 ...
  • Java Labmda表達式的一個重要用法是簡化某些匿名內部類(Anonymous Classes)的寫法。實際上Lambda表達式並不僅僅是匿名內部類的語法糖,JVM內部是通過invokedynamic指令來實現Lambda表達式的。本篇我們首先感受一下使用Lambda表達式帶來的便利之處。 ...
  • 筆者在一家互聯網公司做JavaEE開發,公司開發了移動端的產品,唯獨沒有PC端的產品,於是領導將任務分配給筆者。 使用Java開發PC客戶端,我的第一反應是使用swing API。但是,產品的需求是客戶端內嵌一個瀏覽器引擎,能夠渲染網頁內容。於是,筆者通過百度無意間發現和瞭解到JavaFX。 經過編 ...
  • 一、 hibernate是什麼 (一)hibernate 是一個orm框架,orm (object relation mapping) 對象關係映射框架 o object -> 業務層(只對對象操作) r relation-> 關係資料庫 m mapping 對象關係映射文件 Hibernate有六 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...