五種排序演算法python語言實現

1.冒泡排序

思想： 依次循環遍歷，沒什麼好說的，循環就完事了。每個數據都需要排列，i表示當前位置元素，第j個元素需要對比元素個數，n-1-i表示每行需要對比的最多次數，冒泡排序時間複雜度為O(n2)

def bubbleSort(list,n):

if n <= 1:

return list

for i in range(n): #表示行

flag = False #表示是否有數據交換

for j in range(n-1-i): #表示每行的下標

if list[j] > list[j+1]:

list[j],list[j+1] = list[j+1],list[j]

flag = True

if flag == False:

break

return list

list = [8,1,9,3,4,2,6,7]

n = len(list)

f = bubbleSort(list,n)

運行結果：

2.插入排序

思想：插入排序的工作方式就像許多人排列手中撲克牌一樣。一般都是右手去拿桌子上的牌面向下的牌，然後從牌堆上拿走一張牌並將它插入左手中正確的位置. 為了找到這張牌的正確位置，一般都是將它與已在手中的每張牌進行比較,拿在左手中的牌總是排序好的. 時間複雜度為O(n2)

def insertSort(list,n):

if n <= 1:

return list

for i in range(1,n): #未排序區間

value = list[i]

for j in range(i,-1,-1): #排序過程

if value < list[j-1]: #如果value小於它前面的數。

list[j] = list[j-1] #就和它前面的數字換位置

else: #若沒有，表示當前value為已排序區間最大值

break

list[j] = value

return list

list1 = [1,9,4,23,11,56,8,43,6,7]

print(list1)

n = len(list1)

a = insertSort(list1,n)

print(a)

運行結果：

3.選擇排序：

思想：原理同插入排序。也分已拍區間和未拍區間，選擇排序會從每次未排序的區間中找到最小元素，將其放到已排序區間末尾 選擇排序剛開始沒有已排序，找到最小元素，放到開始。或者末尾.時間複雜度為O(n2)

def selectionSort(list):

if len(list) <= 1:

return list

for i in range(len(list)-1):

min_index = i #記錄最小位置

for j in range(i+1,len(list)):

if list[j] < list[min_index]:

min_index = j

if min_index != i:

list[i],list[min_index] = list[min_index],list[i]

return list

list1 = [1,9,4,23,11,56,8,43,6,7]

print(list1)

a = selectionSort(list1)

print(a)

運行結果：

4.歸併排序：

思想：如果要排序一個數組，我們先把數組從中間分成前後兩部分，然後對前後兩部分分別排序，再將排好序的兩部分合併在一起，這樣整個數組就都有序了。歸併排序使用了二分法，歸根到底的思想還是分而治之。拿到一個長數組，將其不停的分為左邊和右邊兩份，然後以此遞歸分下去。 然後再將她們按照兩個有序數組的樣子合併起來。.時間複雜度為O(nlogn)

def merge(a, b): #接受兩個列表

c = [] #定義了一個新列表

h = j = 0 #兩個變數

while j < len(a) and h < len(b): #當j<列表a的長度。當h小於列表b的長度

if a[j] < b[h]: #如果a的j小於b的h，c添加a[j]，j再+1

c.append(a[j])

j += 1

else:

c.append(b[h]) #反言之c添加b[h]，h+1

h += 1

if j == len(a): #當j到a的末尾了

for i in b[h:]: #列表c添加列表b從h位到末尾的值

c.append(i)

else:

for i in a[j:]: #反之列表c添加列表a從j位到末尾的值

c.append(i)

return c

def merge_sort(lists):

if len(lists) <= 1:

return lists

middle = len(lists)//2 #將列表分成兩份，放到merge中

left = merge_sort(lists[:middle])

right = merge_sort(lists[middle:])

return merge(left, right)

if __name__ == "__main__":

a = [14, 2, 34, 43, 21, 19]

print(a)

print (merge_sort(a))

運行結果：

5.快速排序：

思想：

1．先從數列中取出一個數作為基準數。

2．分區過程，將比這個數大的數全放到它的右邊，小於或等於它的數全放到它的左邊。

3．再對左右區間重複第二步，直到各區間只有一個數。 時間複雜度：O(nlgn)

import random

def getrandata(num):

a = []

i = 0

while i <num:

a.append(random.randint(0,100))

i += 1

return a

def quicksort(num_list):

lenth = len(num_list)

if lenth <= 1:

return num_list

temp = random.randint(0,lenth-1)# 隨便取的一個數，作為列表索引

tempval = num_list[temp]

left = []

right = []

for i in range(0,lenth):

if num_list[i] > tempval:

right.append(num_list[i])

else:

left.append(num_list[i])

return quicksort(left)+quicksort(right)

if __name__ == "__main__":

a = getrandata(10)

print(a)

b = quicksort(a)

print(b)

運行結果：

希望能給後來學習的人一點啟示。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！