排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

我們通常所說的排序算法往往指的是內部排序算法，即數據記錄在內存中進行排序。

建議收藏，想要各類學習資料的看到最后！

內部排序的分類：

• 一種是比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有： 冒泡排序，選擇排序，快速排序，插入排序，希爾排序，歸并排序，堆排序等。
• 另一種是非比較排序，時間復雜度可以達到O(n)，主要有： 計數排序，基數排序，桶排序等。

常見排序算法的一些特性：

冒泡排序

通過上面的動圖也可以看出來，冒泡通過兩重循環遍歷每一個數后將最大的’冒’出去

冒泡是相鄰元素之間的比較，每次把最大的’冒’出去時間復雜度：O(n^2)

選擇排序

選擇排序相比冒泡排序不穩定，時間復雜度也是。

選擇排序沒趟都會產生最小值，它不是相鄰元素的比較而是在該元素設置一個索引i。

然后與數組的其他元素依次比較(除了上一個索引值)，直到找到小于該元素(索引j)時交換兩元素，

接著繼續從i索引(此時已經不是原來的數值)值與索引j+1值比較。重復上述比較過程：

冒泡是相鄰元素比較，選擇不是相鄰元素比較 把最小的選出來

快速排序

(1) 從數列中挑出一個基準值。

(2) 將所有比基準值小的擺放在基準前面，所有比基準值大的擺在基準的后面(相同的數可以到任一邊)；在這個分區退出之后，該基準就處于最終它應該在的地方。

(3) 遞歸地把”基準值前面的子數列”和”基準值后面的子數列”進行排序。

快速排序的時間復雜度在最壞情況下是O(N2)，平均的時間復雜度是O(N*lgN)。

假設有如下數組，將兩個哨兵設在左右端，最左端的值為基準

1.右邊向左運動，直到找到一個比基準小的數

2.左邊向右運動，直到找到一個比基準大的數

.交換兩個數

4

如果兩個哨兵不想遇，則繼續上述步驟

5

遇之后和基準交換

樣

‘6’就永遠在它最終應該待的地方了 ，對6的前一半和后一半進行上述完整操作即可(遞歸)

參考文獻：

http://developer.51cto.com/art/201403/430986.htm

插入排序

初始時

a[0]自成1個有序區，無序區為a[1..n-1]。令i=1

將a[i]并入當前的有序區a[0…i-1]中形成a[0…i]的有序區間。

i++并重復第二步直到i==n-1。排序完成。

直接插入排序的時間復雜度是O(N^2)

希爾排序

是插

排序的一種更高效的改進版本。希爾排序是非穩定排序算法。分組的插入排序

注：

如果索引i，j大于步長gap時，應該一直往前迭代

如代碼中的： j-=gap第一次交換數據后，看它是后面的數否還小于前面的數

如2 3 1 5 9 6這個序列以1位步長的話

一次交換后2 1 3 5 9 6此時j指向第二個數，i指向第三個數

所以交換后應該用j-gap往前查看是否前面的更小

歸并排序

分

法的一種，上圖可以清晰的描述排序過程

先拆分(遞歸)，后合并

效率為 O(n log n)

'''冒泡排序重復走訪過排序的序列，一次比較兩個元素，如果他們的順序錯誤就將他們進行交換，一次冒上來的是最小的，其次是第二小。時間復雜度：(n^2)空間復雜度:O1)穩定性：穩定''def BubbleSort(data): for i in range(len(data)): for j in range(len(data)-i-1): if data[j]>data[j+1]: data[j+1] , data[j] = data[j] , data[j+1]'''選擇排序擇排序相比冒泡排不穩定，時間復雜度也是。選擇排序沒趟都會產生最小值，它不是相鄰元素的比較而是在該元素設置一個索引i。然后與數組的其他元素依次比較(除了上一個索引值)，直到找到小于該元素(索引j)時交換兩元素，接著繼續從i索引(此時已經不是原來的數值)值與索引j+1值比較。重復上述比較過程……簡單的原理圖如下：冒泡是相鄰元素比較，擇不是相鄰元素比較'''def SelectionSort(data): for i in range(len(data)): for j in range(i+1,len(data)): if data[j]= right: return lists key =left low = left high = right while left < right: while left < right and lists[right] >= lists[key]:#如果右邊比基準小，停下 right -= 1 while left < right and lists[left] <= lists[key]:#如果左邊比基準大，停下 left += 1 lists[right],lists[left]=lists[left],lists[right]#交換現在的左右值 lists[right] ,lists[key]=lists[key],lists[right] #left和right匯合后和基準交換 print_data(ata)#交換過程 QuickSort(lists, low, left - 1) QuickSort(lists, left + 1, high) return lists'''直接插入排序1. 初始a[0]自成1個有序，無序區為a[1..n-1]。令i=12. 將a[i]并入當前的有序區a[0…i-1]中形成a[0…i]的有序區間。3. i++并重復第二步直到i==n-1。排序完成。直接插入排序的時間復雜度是O(N2)假設被排序的數列中有N個數。遍歷一趟的時間復雜度是O(N)，需要遍歷多少次呢？N-1！因此，直接插入排序的時間復雜度是O(N2)。'''def InsertionSort(data): for i in range(1,len(data)): key=data[i] j=i-1 while j>=0: if data[j]>key: data[j+1]=data[j] data[j]=key j-=1'''希爾排序是插入排序的一種更高效的改進版本。希爾序是非穩定排序算法。分組的插入排序j-=gap第一次交換數據后，看它是后面的否還小于前面的數如2 3 1 5 9 6這個序列以1位步長話一次交換后2 1 3 5 9 6此時j指向第二個數，i指向第三個數 所以交換后應該用j-gap往前查看是否前面的更小'''def ShellSort(data): gap=int(len(data)/2) #排序的分組 while gap>0: for i in range(gap,len(data)): j=i-gap while data[j]>data[i] and j >=0: data[j],data[i]=data[i],data[j] j-=gap i-=gap gap=int(gap/2)'''歸并排序先拆分，后合并'''de MergeSortls): if len(ls)<2: return ls mid = len(ls) >> 1 #相當于除2取整 left = MergeSort(ls[:mid]) right = MergeSort(ls[md:]) return merge(left,right)def merge(left, right): result = [] i, j = 0, 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: reslt.append(right[j]) j += 1 result += left[i:] result += right[j:] return result'''打印函數'''def print_data(data: for i in data: print(i,end=' ') print() '''測試代碼'''data=[5,9,7,2,3,1,6BubbleSort(data)print_data(data)data=[5,9,7,2,3,1,6]SelectionSort(data)print_data(data)data=[5,9,7,2,3,1,6]QuickSort(data,0,6)print_data(data)data=[5,9,7,2,3,1,6]InsertionSort(data)print_data(data)data=[5,9,7,2,3,1,6]ShellSort(data)print_data(data)data=[5,9,7,2,3,1,6]data=MergeSort(data)print_data(data)

“我自己是一名從事了多年開發的Python老程序員，辭職目前在做自己的Python私人定制課程，今年年初我花了一個月整理了一份最適合2019年學習的Python學習干貨，從最基礎的到各種框架都有整理，送給每一位喜歡Python小伙伴，想要獲取的可以關注我的頭條號并在后臺私信我：01，即可免費獲取。"

總結

以上是生活随笔為你收集整理的python 按条件选择行和列数据_小白学数据结构-排序算法Python（冒泡、选择、快速、希尔等等）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。