排序算法(Sorting alorithm)是计算机科学最古老、最基本的课题之一。要想成为合格的程序员,就必须理解和掌握各种排序算法。

目前,最常见的排序算法大概有七八种,其中'快速排序'(QuickSort)使用得最广泛、速度也较快。它是图灵奖得主C.A.R.Hoare于1960年提出来的。

快速排序效率为O(N*logN),在几种排序方法中效率较高,因此经常被采用,再加上快速排序思想。在很多公司笔试面试,如腾讯、阿里、百度等知名IT公司,以及各种考试。

原理

快速排序是一种划分交换排序,采用了分治的策略(通常称为分治法),基本思想是:

1. 数据集中,选取一个元素作为'基准'(pivot)。

2. 所有小于'基准'的元素,都移到'基准'的左边;所有大于'基准'的元素,都移到'基准'的右边。

3. 对'基准'左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

分析

简单举例来说,现在有一个数据集{87, 34, 33, 45, 17, 90, 50, 87},怎么对其排序呢?

第一步,选择中间的元素45作为'基准'。(基准值可以任意选择,但是选择中间的值比较容易理解)

三分钟!Go读懂经典算法(快速排序)

第二步,按照顺序,将每个元素与'基准'进行比较,形成两个子集,一个'小于45', 另一个'大于等于45'。

三分钟!Go读懂经典算法(快速排序)

第三步,对两个子集不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

三分钟!Go读懂经典算法(快速排序)

三分钟!Go读懂经典算法(快速排序)

三分钟!Go读懂经典算法(快速排序)

三分钟!Go读懂经典算法(快速排序)

Golang代码实现

三分钟!Go读懂经典算法(快速排序)

总结

快速排序实现方式已经很多,但最最重要的还是理解递归的思想,然后合理设计递归函数。

谢谢!!欢迎大家讨论交流排序算法的精妙之处。