文章目錄

• 1 快速排序
• 2 堆排序
• 3.冒泡排序
• 4.選擇排序
• 5.插入排序

1 快速排序

• 時(shí)間復(fù)雜度 O(nlogn)
• 不穩(wěn)定
• 在大多數(shù)情況下都是適用的，尤其在數(shù)據(jù)量大的時(shí)候性能優(yōu)越性更加明顯

def quicksort(start, end, nums):if start >= end:return flag = nums[start]r_ptr = endl_ptr = startwhile (l_ptr < r_ptr):while (l_ptr < r_ptr and nums[r_ptr] >= flag):r_ptr -= 1if (l_ptr < r_ptr):nums[l_ptr] = nums[r_ptr]l_ptr += 1while (l_ptr < r_ptr and nums[l_ptr] < flag):l_ptr += 1if (l_ptr < r_ptr):nums[r_ptr] = nums[l_ptr]r_ptr -= 1nums[l_ptr] = flagquicksort(start, l_ptr - 1, nums)quicksort(l_ptr + 1, end, nums)

2 堆排序

• 時(shí)間復(fù)雜度 O(nlogn)
• 把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過(guò)程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束
• 不穩(wěn)定
• 建立堆和調(diào)整堆的過(guò)程中會(huì)產(chǎn)生比較大的開(kāi)銷，在元素少的時(shí)候并不適用

class MinHeap:def __init__(self):self.array = [-1]def insert_node(self, val):self.array.append(val)index = len(self.array) - 1while (index // 2 != 0):father = index // 2if self.array[father] > self.array[index]:temp = self.array[index]self.array[index] = self.array[father]self.array[father] = tempindex = fathercontinue# 未發(fā)生交換，完成插入breakdef delete_node(self):res = self.array[1]self.array[1] = self.array[-1]self.array = self.array[:-1]index = 1length = len(self.array)while (True):# 具有兩個(gè)子節(jié)點(diǎn)if 2*index+1 <= length-1:left = self.array[index*2]right = self.array[index*2+1]if left < right:if self.array[index] > left:temp = self.array[index]self.array[index] = self.array[index*2]self.array[index*2] = tempindex = index * 2continueelse:breakelse:if self.array[index] > right:temp = self.array[index]self.array[index] = self.array[index*2+1]self.array[index*2+1] = tempindex = index * 2 + 1continueelse:break# 一個(gè)子節(jié)點(diǎn)elif 2*index <= length-1:if self.array[index] > self.array[index*2]:temp = self.array[index]self.array[index] = self.array[index*2]self.array[index*2] = tempindex = index * 2continueelse:break# 沒(méi)有子節(jié)點(diǎn)else:breakreturn res

3.冒泡排序

• 時(shí)間復(fù)雜度O(n2)
• 在相鄰元素相等時(shí)，它們并不會(huì)交換位置，所以冒泡排序是穩(wěn)定排序

def bubble(self, array, length):for i in range(length - 1, -1, -1): # 外層循環(huán)：每次需要排序的長(zhǎng)度for j in range(i): # 內(nèi)層循環(huán)：從第一個(gè)元素到第i個(gè)元素if array[j] > array[j + 1]:pre, post = array[j + 1], array[j]array[j + 1], array[j] = post, prereturn array

4.選擇排序

• 時(shí)間復(fù)雜度O(n2)
• 和冒泡排序有一定的相似度，可以認(rèn)為選擇排序是冒泡排序的一種改進(jìn)
• 是不穩(wěn)定的排序算法

def select(self, array, length):for i in range(length - 1): # 外層循環(huán)的i代表本次循環(huán)需要填的位置min_val = array[i]min_idx = ifor j in range(i + 1, length):if min_val > array[j]:min_val = array[j]min_idx = jarray[min_idx] = array[i]array[i] = min_valreturn array

5.插入排序

• 時(shí)間復(fù)雜度O(n2)
• 把待排序的數(shù)組分成已排序和未排序兩部分，初始的時(shí)候把第一個(gè)元素認(rèn)為是已排好序的。從第二個(gè)元素開(kāi)始，在已排好序的子數(shù)組中尋找到該元素合適的位置并插入該位置

def insert(self, array, length):for i in range(1, length): # 外層循環(huán)的i代表當(dāng)前要處理的位置，i之前已經(jīng)全部有序val = array[i]ptr = iwhile (ptr > 0 and array[ptr - 1] > val): # 內(nèi)層循環(huán)尋找插入位置array[ptr] = array[ptr - 1]ptr -= 1array[ptr] = valreturn array

總結(jié)

以上是生活随笔為你收集整理的算法 - 排序算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。