原理

快速排序体现的是一种分治的思想，它的核心思想是化整为零。每次在待排序列A[p…r]中去一个标杆，然后我们将这个序列划分为两部分，使得A[p…q…r]满足q左边的元素都小于或等于q，q右边的元素都大于q。然后我们在对A[p…q]和A[q…r]实行相同的操作，重复下去最终会得到排好序的序列。

实现

语言描述的或许不是很清晰，而且大部分人应该都知道快速排序的原理，可能与本文所说的有出入，但是大致都差不多。

所以我们要实现快速排序首先需要实现一个子函数partition(A,p,r)，这个函数的作用是将数组A中的p到r的元素进行一个划分，一边划分为大于A[r]的，一边小于等于A[r]。

在实现了子函数partition(A,p,r)之后，我们就可以写出递归版本的快速排序了。

java 完整代码

C/C++版本

其实这个版本是基于C写的，没有涉及c++的迭代器，模板等。还是很简单的，就为了代码的复用性用的是空指针传参数，其他的没啥亮点。相对于java版本的多了一个 int (*comp) 这个函数用来规定比较的方法，通过传入不同的比较函数可以实现对不同数据类型的按规则排序，比如降序我就不用再写一个新的方法了，只需要始兴县一个intLess()。然后注意到这里用了一点点优化，因为快速排序如果按照我们之前的思路实现的话会出现一个问题，如果partition()函数每次划分完毕后的序列大小不一致，那么我们的递归树会很深，这样会消耗很多时间，所以为了让时间递归树的深度相对降低一点我们做一点小技巧，每次不再取key = A[r]，而是key = A[rand(p,r)]。

以上就是这篇文章的全部内容，学习更多Java基础知识快戳视频链接开始吧