快速排序的实现

Create at 2015 01 304 min read技术算法

快速排序是一种经常用到的排序方法,它的时间复杂度为 O(nlogn)。因为大多数情况下速度都比一般的排序方法快,用的比较多,自己就琢磨着实现了一下。

原理

快速排序用到了分治法的原理:   从数组中随机取出一个数字,将这个数组分为两个部分。将取出的数字作为基准数,小于基准数的放到它的左边,大于基准数的放到它的右边。这样基准数左边的都是比它小的,右边的都是比它大的。然后再对基准数的左边和右边重复前面的过程,直到每个部分的数组长度为 1。最后再将这些分开的数组组合起来就成功了。步骤如下:

  1. 从数组中随机抽取一个数组作为基准数,将数组中的每个数字与基准数比较,小于基准数的放到基准数左边,大于基准数的放到基准数右边。
  2. 对上面结束后的左右两个部分重复步骤 1。
  3. 当所有部分的长度为 1 时停止。

实现

下面是自己熟悉的语言的实现(用第一个数作为基准数,并且采用递归的方法):

Python 版本

Read more