从扑克牌的角度理解排序算法(一)

credit by Josh Appel

快速排序

快速排序用到了“分而治之”的思想,即先解决小问题,然后再将小问题挨个合并,这种思想在归并排序中也有体现。

想象我们手中有一手未排序的扑克牌,如何用快速排序的方法对它排序呢?首先,需要选择一张牌作为基准(pivot),选择的方式有多种,为了方便起见,就拿第一张作为基准牌。基准牌的作用是用来切割扑克牌,我们约定比它小的全部放在它左边(less),比它大的全部放在它右边(more)。经过第一次的切割之后,基准牌的左边都是比它小的,右边都是比它大的,但是左右两边依然是无序的。

然后仍旧递归地对左边和右边重复以上的操作,直到左边和右边的长度都小于等于1,此时排序结束,返回 left + pivot_list + right。

常见的快速排序递归版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quick_sort(list):

less = []
more = []
pivot_list = []

if len(list) <= 1:
return list

else:
pivot = list[0]
for item in list:
if item < pivot:
less.append(item)
elif item > pivot:
more.append(item)
else:
pivot_list.append(pivot)
# 对左边和右边分别递归
less = quick_sort(less)
more = quick_sort(more)
return less + pivot_list + more

另外一个版本的快速排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)

def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i+1]
return i + 1

---------------------

本文来自 lookupheaven 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/razor87/article/details/71155518?utm_source=copy

冒泡排序

想象你手中有一副牌,从最左边第一张牌开始,将第一张牌与第二张牌比较大小,如果第一张牌大,那么交换两者的位置,否则,保持两者不动。然后到第二张牌与第三张牌比较,第三张与第四张比较,以此类推。经过第一轮相邻比较,我们找出了手中最大的一张牌,然后继续对剩下的牌重复上面的步骤。

之所以称之为冒泡排序,经过一轮一轮的比较,越小的数字会逐渐“浮现”到数组的顶端。下面的冒泡排序的实现:

1
2
3
4
5
6
def bubble_sort(array):
for i in range(len(array)-1, 0, -1):
for j in range(i):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return array

插入排序

想象自己打扑克牌时理牌的过程,开始手上没有一张牌,摸到一张牌array[0]放在手上,再摸一张牌,与手上的牌array[0]比较,小的放后面,大的放前面。

插入排序

1
2
3
4
5
6
7
8
9
def insert_sort(array):
for i in range(1, len(array)):
new_card = array[i]
j = i - 1
while j >= 0 and new_card < array[j]:
array[j+1] = array[j]
j -= 1
array[j+1] = new_card
return array

[Python-算法]python实现冒泡,插入,选择排序 - CSDN博客

选择排序

我在观察大人打扑克牌的时候发现,我小舅舅在摸牌时并不会像其他人用“插入排序”,他的策略是在所有牌摸完之前不给牌排序。等到所有的牌都到手后,他开始使用“选择排序”。

首先从第一张牌开始,假定第一张牌是最小的,然后将所有的牌与第一张牌比较,找到真正最小的牌并跟第一张牌交换,每次循环找出一个最小值。由此看来,冒泡排序和选择排序差不多,但是两者的复杂度还是有区别的,在最坏的情况,冒泡排序需要 $O(n^{2})$次交换,而插入排序只要最多$O(n)$交换。

下面是选择排序的实现:

1
2
3
4
5
6
7
8
def select_sort(array):
for i in range(0, len(array)-1):
min = i
for j in range(i+1, len(array)):
if array[j] < array[min]:
min = j
array[min] = array[j]
return array

归并排序

同快速排序,归并排序也用到了“分而治之”的思想,归并排序的过程是一分一合,“分”指的是先把子序列变成有序,“治”指的是合并各对有序的子序列,使其变成一个整体,它是将两个排好序的数组合并为一个数组的过程。

归并排序

下面是归并排序的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Recursively implementation of Merge Sort
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result += left
if right:
result += right
return result

def merge_sort(L):
if len(L) <= 1:
# When D&C to 1 element, just return it
return L
mid = len(L) // 2
left = L[:mid]
right = L[mid:]

left = merge_sort(left)
right = merge_sort(right)
# conquer sub-problem recursively
return merge(left, right)
# return the answer of sub-problem

if __name__ == "__main__":
test = [1, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0]
print("original:", test)
print("Sorted:", merge_sort(test))

图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园

觉得还不错?赞助一下~
0%