python插入排序3（快速排序 python3）

本文目錄一覽：

• 1、python幾種經典排序方法的實現
• 2、python中有哪些簡單的算法？
• 3、面試必會八大排序算法（Python）

python幾種經典排序方法的實現

class SortMethod:

”’

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序，時間複雜度為O(n^2)。是穩定的排序方法。

插入算法把要排序的數組分成兩部分：

第一部分包含了這個數組的所有元素，但將最後一個元素除外（讓數組多一個空間才有插入的位置）

第二部分就只包含這一個元素（即待插入元素）。

在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。

”’

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

”’

希爾排序 (Shell Sort) 是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 DL．Shell 於 1959 年提出而得名。

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。

”’

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

”’

冒泡排序重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

”’

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

temp = lists[j]

lists[j] = lists[i]

lists[i] = temp

return lists

”’

快速排序

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列

”’

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

”’

直接選擇排序

第 1 趟，在待排序記錄 r[1] ~ r[n] 中選出最小的記錄，將它與 r[1] 交換；

第 2 趟，在待排序記錄 r[2] ~ r[n] 中選出最小的記錄，將它與 r[2] 交換；

以此類推，第 i 趟在待排序記錄 r[i] ~ r[n] 中選出最小的記錄，將它與 r[i] 交換，使有序序列不斷增長直到全部排序完畢。

”’

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

temp = lists[min]

lists[min] = lists[i]

lists[i] = temp

return lists

”’

堆排序 (Heapsort) 是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。

可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即 A[PARENT[i]] = A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

”’

# 調整堆

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)

# 創建堆

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)

”’

歸併排序是建立在歸併操作上的一種有效的排序算法,該算法是採用分治法 （Divide and Conquer） 的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。

歸併過程為：

比較 a[i] 和 a[j] 的大小，若 a[i]≤a[j]，則將第一個有序表中的元素 a[i] 複製到 r[k] 中，並令 i 和 k 分別加上 1；

否則將第二個有序表中的元素 a[j] 複製到 r[k] 中，並令 j 和 k 分別加上 1，如此循環下去，直到其中一個有序表取完，然後再將另一個有序表中剩餘的元素複製到 r 中從下標 k 到下標 t 的單元。歸併排序的算法我們通常用遞歸實現，先把待排序區間 [s,t] 以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸併操作合併成有序的區間 [s,t]。

”’

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)

”’

基數排序 （radix sort） 屬於“分配式排序” （distribution sort），又稱“桶子法” （bucket sort） 或 bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬於穩定性的排序。

其時間複雜度為 O (nlog(r)m)，其中 r 為所採取的基數，而 m 為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。

”’

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

———————

作者：CRazyDOgen

來源：CSDN

原文：

版權聲明：本文為博主原創文章，轉載請附上博文鏈接！

python中有哪些簡單的算法？

你好：

跟你詳細說一下python的常用8大算法：

1、插入排序

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用於少量數據的排序，時間複雜度為O(n^2)。是穩定的排序方法。插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但將最後一個元素除外(讓數組多一個空間才有插入的位置)，而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後，再將這個最後元素插入到已排好序的第一部分中。

2、希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因DL．Shell於1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

3、冒泡排序

它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

4、快速排序

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

5、直接選擇排序

基本思想：第1趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄r[i] ~ r[n]中選出最小的記錄，將它與r[i]交換，使有序序列不斷增長直到全部排序完畢。

6、堆排序

堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值，即A[PARENT[i]] = A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

7、歸併排序

歸併排序是建立在歸併操作上的一種有效的排序算法,該算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為二路歸併。

歸併過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]複製到r[k]中，並令i和k分別加上1；否則將第二個有序表中的元素a[j]複製到r[k]中，並令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然後再將另一個有序表中剩餘的元素複製到r中從下標k到下標t的單元。歸併排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸併操作合併成有序的區間[s,t]。

8、基數排序

基數排序(radix sort)屬於“分配式排序”(distribution sort)，又稱“桶子法”(bucket sort)或bin sort，顧名思義，它是透過鍵值的部分資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m)，其中r為所採取的基數，而m為堆數，在某些時候，基數排序法的效率高於其它的穩定性排序法。

面試必會八大排序算法（Python）

一、插入排序

介紹

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

算法適用於少量數據的排序，時間複雜度為O(n^2)。

插入排算法是穩定的排序方法。

步驟

①從第一個元素開始，該元素可以認為已經被排序

②取出下一個元素，在已經排序的元素序列中從後向前掃描

③如果該元素（已排序）大於新元素，將該元素移到下一位置

④重複步驟3，直到找到已排序的元素小於或者等於新元素的位置

⑤將新元素插入到該位置中

⑥重複步驟2

排序演示

算法實現

二、冒泡排序

介紹

冒泡排序（Bubble Sort）是一種簡單的排序算法，時間複雜度為O(n^2)。

它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

原理

循環遍歷列表，每次循環找出循環最大的元素排在後面；

需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。

步驟

①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

③針對所有的元素重複以上的步驟，除了最後一個。

④持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

算法實現：

三、快速排序

介紹

快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填數 + 分治法。

首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現步驟

①從數列中挑出一個元素，稱為 “基準”（pivot）；

②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；

③對所有兩個小數列重複第二步，直至各區間只有一個數。

排序演示

算法實現

四、希爾排序

介紹

希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法，時間複雜度為：O(1.3n)。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；

·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。

基本思想

①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入算法排序；

②隨着增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法被終止。

排序演示

算法實現

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡單直觀的排序算法，時間複雜度為Ο(n2)。

基本思想

選擇排序的基本思想：比較 + 交換。

第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；

第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；

以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。

排序演示

選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

算法實現

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。

利用數組的特點快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹。

大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] =A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

排序演示

算法實現

七、歸併排序

介紹

歸併排序（Merge sort）是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想

歸併排序算法是將兩個（或兩個以上）有序表合併成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列。

算法思想

自上而下遞歸法（假如序列共有n個元素）

① 將序列每相鄰兩個數字進行歸併操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；

② 將上述序列再次歸併，形成 floor(n/4)個序列，每個序列包含四個元素；

③ 重複步驟②，直到所有元素排序完畢。

自下而上迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列；

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置；

④ 重複步驟③直到某一指針達到序列尾；

⑤ 將另一序列剩下的所有元素直接複製到合併序列尾。

排序演示

算法實現

八、基數排序

介紹

基數排序（Radix Sort）屬於“分配式排序”，又稱為“桶子法”。

基數排序法是屬於穩定性的排序，其時間複雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。

在某些時候，基數排序法的效率高於其他的穩定性排序法。

基本思想

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序按照優先從高位或低位來排序有兩種實現方案：

MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。

LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重複，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。

排序效果

算法實現

九、總結

各種排序的穩定性、時間複雜度、空間複雜度的總結：

平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；

從時間複雜度來說：

線性對數階O(nlog₂n)排序：快速排序、堆排序和歸併排序；

O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；

線性階O(n)排序：基數排序，此外還有桶、箱排序。