快速排序算法的简单理解

快速排序算法的简单理解

快速排序算法的简单理解

本文用的编程语言为python,简单阐释了作者对快速排序算法的学习心得,尽量用通俗易懂的方式向读者表达。如果文章中有什么纰漏与错误,请读者指正。

在了解快速排序之前,我们先来了解一下递归

递归

递归调用自己的函数

先来看一个函数

def countdown(i):
	print(i)
	countdown(i-1)

这是一个不断递减的函数,如果调用这个函数,它会无限循环下去。这可不是一件好事。我们应该给予它一些限制,告诉它什么时候停止调用自己,什么时候调用自己。我们把这种限制分别叫做基线条件递归条件。任何一个递归函数都有这两个条件。

接下来我们改进一下上面的函数

def countdown(i):
	print(i)
	if i > 0:	# 递归条件
		countdown(i-1)
	else:      # 基线条件
		return 

修改过后的递减函数,它只会打印非负数,这样就可以避免递归函数的无限调用。

为了加深理解,我们用图解的方式详细分析另一个递归函数---计算一个数组的和

没错,一个很简单的函数,在很多编程语言里都会内置求和函数,例如python的求和函数就是sum(),但今天我们从递归的角度去想一下如何实现它。

之前说了,任何一个递归函数都有基线条件与递归条件。 那怎么去找它的基线条件呢?一个数组最简单的状态是什么?空的数组或者只包含一个元素的数组。

只包含一个元素的数组的和,就是它自己,那么两个元素呢?三个元素呢?甚至n个元素呢? 下面的图解帮助我们更好地理解,输入一个数组,当数组的个数等于1时停止调用,返回

示例代码

def sum(arr):
	if len(arr) == 1:
		return arr[0]
	else:
		return arr[0] + sum(arr[1:])

理解了上述思想后,我们再来看一下快速排序算法。

在生活中随处可见无序的数字串,如身份证号码、电话号码等等

假如现在我们有一个无序的数组

我们随便取一个数,比如取第一个数3,然后将比3小的放在3的左边,比3大的放在3的右边,以此类推,如下图所示

这就实现了快速排序。是不是感觉和之前计算和有些像,这里同样也用到了递归的思想。

快速排序

def quicksort(arr):
	if len(arr) < 2:
		return arr
	else:
		min = [x for x in arr[1:] if x < arr[0]]
		max = [x for x in arr[1:] if x >= arr[0]]
		return quicksort(min) + [arr[0]] + quicksort(max)

对一个数组进行快速排序,先任取一个数,将比它小的放左边,比它大的放右边。然后再对比它小的数组和比它大的数组进行快速排序,不断递归,直到数组只剩下一个数,这时候满足设置的基线条件,返回上一层的调用后,将左边右边的数组进行拼接,最后就得到了一个排序好的数组。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×