快速排序算法实现

速排序可以说是使用最广的排序算法了，主要的特点是基于原地排序(不需要使用辅助数组，节省空间);其实对于长度为N的数组使用快速排序时间复杂度为 NlogN;在前几篇也一起讨论了其他的排序算法，都没能够把这两个特点结合起来。

快速排序思路

快速排序也是一种分治的排序算法，把数组划分为两个子数组，然后递归对子数组进行排序，最终保证整个数组有序。

算法思路：

1. 随机选择一个切分元素，通常选择的是数组的第一个元素
2. 从数组的左边开始扫描找出大于等于切分元素的值，从数组的右边开始扫描找出小于等于切分元素的值，交换这两个值
3. 循环这个过程直到左右两个指针相遇，这样就排定了一个元素，保证了切分元素左边的值都是小于它的值，右边的元素都是大于它的值
4. 递归这个过程，最终保证整个数组有序

算法实现

根据快速排序算法的思路，我们可以写出第一版实现：对一个长度为N的数组，最糟糕的情况下需要递归N-1次，所以时间复杂度是O(n2)，为了避免这种情况出现，我们来看下算法如何改进

算法改进

• 保证随机性 为了避免最糟糕的情况出现，有两个办法，第一是在排序数组之前先随机打乱数组;第二是在partition方法中随机取切分元素，而不是固定取第一个，简单实现：

（编辑：滨州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!