排序算法（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作为'基准'。（基准值可以任意选择，但是选择中间的值比较容易理解）

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

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

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

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

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。