计算机基础常见的排序有几种,几种基础的数学算法（二）- 排序

怼烎@ 2022-08-30 13:56 208阅读 0赞

几种基础的数学算法(二)- 排序

说起排序算法，估计所有小伙伴参加面试都或多或少接触过。我们先来了解几个概念。

时间复杂度：算法完成排序的总的操作次数；

空间复杂度：算法在运行时所需存储空间大小；

稳定的算法：一个序列中，如果 a 原本在 b 前面，且 a = b，排序之后在新的有序序列中 a 仍然在 b 的前面。

不稳定的算法：一个序列中，如果 a 原本在b的前面，且 a = b，排序之后在新的有序序列中 a 可能会出现在 b 的后面。

排序算法对比

![adfecd46f8e0f56ff26d864d4bb24f52.png][]

排序算法的文章很多，这里给大家推荐个链接："如果天空不死"的博客

简单介绍五种排序方法

冒泡排序

无序序列 Rn 中排序一趟只确认一个排序位置，最多经过 n 趟排序。

冒泡排序在一趟中每次比较两个相邻的元素，如果不符合排序要求，则交换两个元素，直到一趟排序结束。

![caa3991ce30a27f4533f02600f066cbd.png][]

![5ebcfba5aae2ea9cbfef516de7c21732.png][]

![420c15dd491fde340f62ebd508ead421.png][]

def swap(arr: list, i: int, j: int):

tmp = arr\[i\]

arr\[i\] = arr\[j\]

arr\[j\] = tmp

\# 冒泡排序

\# 递增排序

def bubble\_inc(arr: list):

print("source array = " + str(arr))

arr\_len = len(arr)

if arr\_len == 0:

return

for i in range(0, arr\_len):

for j in range(0, arr\_len - i - 1):

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

swap(arr, j, j + 1)

print("bubble increase array = " + str(arr))

\# 冒泡排序

\# 递排序

def bubble\_dec(arr: list):

print("source array = " + str(arr))

arr\_len = len(arr)

if arr\_len == 0:

return

for i in range(0, arr\_len):

for j in range(0, arr\_len - i - 1):

if arr\[j\] < arr\[j + 1\]:

swap(arr, j, j + 1)

print("bubble decrease array = " + str(arr))

array = \[3, 2, 6, 1, 4\]

bubble\_inc(array)

bubble\_dec(array)

运行结果

source array = \[2, 1, 6, 4, 3\]

bubble increase array = \[1, 2, 3, 4, 6\]

source array = \[1, 2, 3, 4, 6\]

bubble decrease array = \[6, 4, 3, 2, 1\]

插入排序

简单来说，插入排序就是将未排序的元素插入到已排序的序列中。

序列 Rn，1...k 的元素有序，k+1...n 的元素无序，将 k+1 位置的元素插入到前 k 个有序序列中，直到所有无序元素排序完成。

![f223820dc52cdd4f58b2c5cc79817062.png][]

\# 插入排序

\# 递增序列

def insert\_inc(arr: list):

print("source array = " + str(arr))

arr\_len = len(arr)

for i in range(1, arr\_len):

pre\_idx = i - 1

tmp = arr\[i\]

while pre\_idx >= 0 and arr\[pre\_idx\] > tmp:

arr\[pre\_idx + 1\] = arr\[pre\_idx\]

pre\_idx -= 1

arr\[pre\_idx + 1\] = tmp

print("insert increase array = " + str(arr))

\# 插入排序

\# 递减序列

def insert\_dec(arr: list):

print("source array = " + str(arr))

arr\_len = len(arr)

for i in range(1, arr\_len):

pre\_idx = i - 1

tmp = arr\[i\]

while pre\_idx >= 0 and arr\[pre\_idx\] < tmp:

arr\[pre\_idx + 1\] = arr\[pre\_idx\]

pre\_idx -= 1

arr\[pre\_idx + 1\] = tmp

print("insert decrease array = " + str(arr))

array = \[3, 2, 6, 1, 4\]

insert\_inc(array)

insert\_dec(array)

运行结果

source array = \[3, 2, 6, 1, 4\]

insert increase array = \[1, 2, 3, 4, 6\]

source array = \[1, 2, 3, 4, 6\]

insert decrease array = \[6, 4, 3, 2, 1\]

归并排序

归并排序采用的算法思想是“分治”，将一个无序序列分为 2 个子序列，再将子序列分别采用归并排序；最后合并两个有序的子序列 。

长度为 n 的序列，分割为长度为 n/2 的两个子序列；

对分割的两个子序列进行归并排序；

将两个通过归并排序而有序的子序列合并成一个有序序列；

![2e61a649abf7ad289d77734f2595e58d.png][]

def do\_merge(left: list, right: list):

result = \[\]

while len(left) > 0 and len(right) > 0:

if left\[0\] <= right\[0\]:

result.append(left.pop(0))

else:

result.append(right.pop(0))

while len(left) > 0:

result.append(left.pop(0))

while len(right) > 0:

result.append(right.pop(0))

return result

def merge(arr: list):

arr\_len = len(arr)

if arr\_len < 2:

return arr

mid\_index = arr\_len // 2

left\_arr = arr\[0:mid\_index\]

right\_arr = arr\[mid\_index:\]

result = do\_merge(merge(left\_arr), merge(right\_arr))

return result

array = \[3, 2, 6, 1, 4\]

\# 归并排序

\# 递增序列

print("merge increase array = " + str(merge(array)))

运行结果

merge increase array = \[1, 2, 3, 4, 6\]

快速排序

快速排序也是采用“分治”的思想，通过选取无序序列的基数，分为小于基数的序列和不小于基数的序列；然后继续可以对两个子序列排序，从而得到最终的有序序列。

![4dadb302c28412479a79054bddbb7141.png][] 上述例子中，基数从序列位置 0 开始获取

def swap(arr: list, i: int, j: int):

tmp = arr\[i\]

arr\[i\] = arr\[j\]

arr\[j\] = tmp

def do\_quick(arr: list, left: int, right: int):

pivot = left

start = pivot + 1

index = start

for i in range(start, right + 1):

if arr\[i\] < arr\[pivot\]:

swap(arr, i, index)

index += 1

swap(arr, pivot, index - 1)

return index - 1

def quick(arr, left, right):

if left < right:

index = do\_quick(arr, left, right)

quick(arr, left, index - 1)

quick(arr, index + 1, right)

return arr

array = \[3, 2, 6, 1, 4\]

print("quick increase array = " + str(quick(array, 0, len(array) - 1)))

运行结果

quick increase array = \[1, 2, 3, 4, 6\]

基数排序

基数排序可以认为是分层递进排序，分层就是排序的优先层级，递进就是每次分层排序都是有效的。 下面的例子中无序序列中的数字先按个位大小排序，形成一个新的无序序列，再对新的无序序列按十位进行排序，依次直到所有位数的排序完成

![6c09d35490c62bde9685414bac813086.png][] 按十位排序后，排序已经结束

def radix(arr: list, max\_num: int):

mod = 10

dev = 1

counter = \[\[\] for i in range(0, 10)\]

for i in range(0, max\_num):

for j in range(0, len(arr)):

idx = (arr\[j\] % mod) // dev

if len(counter) <= idx:

counter\[idx\] = \[\]

counter\[idx\].append(arr\[j\])

pos = 0

for j in range(0, len(counter)):

while len(counter\[j\]) > 0:

arr\[pos\] = counter\[j\].pop(0)

pos += 1

mod \*= 10

dev \*= 10

return arr

array = \[23, 12, 36, 5, 89\]

print("radix increase array = " + str(radix(array, 6)))

运行结果

radix increase array = \[5, 12, 23, 36, 89\]

到这里，介绍了五种常见的排序算法，其余的排序算法小伙伴们可以通过上述推荐的博文去加以了解。共勉，进步！！！

[adfecd46f8e0f56ff26d864d4bb24f52.png]: /images/20220829/229fd94d94cb403e833eecb93639812e.png
[caa3991ce30a27f4533f02600f066cbd.png]: /images/20220829/429e2cd63ee741fa8963bef9bc68f2e8.png
[5ebcfba5aae2ea9cbfef516de7c21732.png]: /images/20220829/fe0d364c58ba477c9c5dd4ee0256df17.png
[420c15dd491fde340f62ebd508ead421.png]: /images/20220829/ca770c8a9f9749c4a841a2fc4bab01cc.png
[f223820dc52cdd4f58b2c5cc79817062.png]: /images/20220829/de5da854d094480d9e6d68894a74ee6a.png
[2e61a649abf7ad289d77734f2595e58d.png]: /images/20220829/913d25487f204a6e996dd89276b34385.png
[4dadb302c28412479a79054bddbb7141.png]: /images/20220829/a0bd0bd366b54fe8b9ca233e847b165a.png
[6c09d35490c62bde9685414bac813086.png]: /images/20220829/f7af28151d694458aef9a839ba867c3e.png