前言

原理就不在這里說了,好多大神肯定比我這個(gè)初學(xué)者講的好很多,推薦去B站看視頻講解,跟著手敲代碼

為什么選這三個(gè)排序呢?

首先快排是必須掌握的

看看快排在最壞的情況下(O(n2)),且不使用輔助空間,與冒泡(O(n2))的比較

由于快排是不穩(wěn)定的排序算法,且平均時(shí)間復(fù)雜度為O(nlogn),那找一個(gè)時(shí)間復(fù)雜度為O(nlogn)且穩(wěn)定排序算法,那么就非歸并排序莫屬了.

一、快速排序,歸并排序,冒泡排序比較

時(shí)間復(fù)雜度

空間復(fù)雜度

穩(wěn)定性

平均

最好

最壞

冒泡排序

O(n2)

O(n)

O(n2)

O(1)

穩(wěn)定

O(nlogn)

O(nlogn)

O(n2)

O(1)或O(n)

不穩(wěn)定

歸并排序

O(nlogn)

O(nlogn)

O(nlogn)

O(n)

穩(wěn)定

二、源碼

引入庫,并生成1000個(gè)隨機(jī)數(shù),然后深拷貝若干份.

import random

from copy import deepcopy

arr0 = [random.randint(1, 100) for _ in range(1000)]

# arr0 = [_ for _ in range(1000, 0, -1)]

# print(arr0)

for i in range(1, 11):

exec(f'arr{i} = deepcopy(arr0)')

1.冒泡

def bubble_sort(arr):

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

for j in range(len(arr) - 1 - i):

if arr[j] >= arr[j + 1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

return arr

2.歸并

def merge_sort(arr):

length = len(arr)

if length <= 1:

return arr

mid = length // 2

# 以下標(biāo)mid為分界點(diǎn),將arr的[:mid]給left,[mid:]給right

left = merge_sort(arr[:mid])

right = merge_sort(arr[mid:])

lp = 0

rp = 0

res = []

while lp < len(left) and rp < len(right):

if left[lp] <= right[rp]:

res.append(left[lp])

lp += 1

else:

res.append(right[rp])

rp += 1

# 這里要用extend. left,right切片后的值為一個(gè)list

res.extend(left[lp:])

res.extend(right[rp:])

return res

3.快排

# 一句話快排

qs = lambda arr: arr if len(arr) <= 1 else qs([it for it in arr[1:] if it <= arr[0]]) + [arr[0]] +

qs([it for it in arr[1:] if it > arr[0]])

# 空間復(fù)雜度O(1)的快排

def quick_sort_O1(arr, left, right):

if left >= right:

return

base = arr[left]

lp = left

rp = right

while lp < rp:

while lp < rp and arr[rp] >= base:

rp -= 1

arr[lp] = arr[rp]

while lp < rp and arr[lp] < base:

lp += 1

arr[rp] = arr[lp]

arr[lp] = base

quick_sort_O1(arr, left, lp - 1)

quick_sort_O1(arr, lp + 1, right)

return arr

# 空間復(fù)雜度O(n)的快排

def quick_sort_On(arr: list):

if len(arr) <= 1:

return arr

left = []

right = []

base = arr.pop(0)

for it in arr:

if it <= base:

left.append(it)

else:

right.append(it)

return quick_sort_On(left) + [base] + quick_sort_On(right)

# 空間復(fù)雜度O(n)的快排,引入隨機(jī)處理,嘗試規(guī)避快排的最壞風(fēng)險(xiǎn)

def quick_sort_On_random(arr: list):

if len(arr) <= 1:

return arr

left = []

right = []

base = arr.pop()

while arr:

tmp = arr.pop()

if tmp <= base:

left.append(tmp)

else:

right.append(tmp)

return quick_sort_On(left) + [base] + quick_sort_On(right)

三、創(chuàng)建長度為1000的list,在jupyter?notebook上運(yùn)行,觀察結(jié)果

1.隨機(jī)無序數(shù)組結(jié)果

空間換時(shí)間的做法明顯讓快排效率提高了一個(gè)數(shù)量級(jí)~

2.反序數(shù)組結(jié)果

將arr0重新賦值如下:

arr0 = [_ for _ in range(1000, 0, -1)]

3.正序數(shù)組結(jié)果

將arr0重新賦值如下:

arr0 = [_ for _ in range(1000)]

4.內(nèi)置函數(shù)–遙遙領(lǐng)先

**內(nèi)置函數(shù)那么快,學(xué)啥快排(捂臉)…

隨機(jī)無序數(shù)組

反序數(shù)組

正序結(jié)果

總結(jié)

先不總結(jié)了,大致情況就如上吧.希望大家看完后給些意見和建議.

不知道有什么地方?jīng)]考慮進(jìn)去,本來只是為了規(guī)避快排最壞情況的風(fēng)險(xiǎn)而實(shí)現(xiàn)的quick_sort_On_random,意外發(fā)現(xiàn)每次都是最快的???

總結(jié)

以上是生活随笔為你收集整理的python实现冒泡排序算法的非递归版本_python排序算法速度比较:快速排序,归并排序,冒泡排序...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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