快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程(递归)，直到所有元素都排列在相应位置上为止。

        在动态图中，key称为基准值，默认把基准值定义在数组的首元素上，其次为了加快遍历的速度，需要用到两个变量分别去对应数组的首尾部分，L处在数列的首部，它需要从左往右寻找比Keyi位置的值大的，遇到后就停下来，没遇到就一直走；R处在数列的尾部，它需要从右往左去寻找比keyi位置的值小的，也是遇到后就停下来，没遇到就一直走。

        当L与R都遇到停下来后开始互换位置，然后继续遍历，直到L==R时，双方都不会再走了，因为它们走到了同一个位置，这个位置被称为它俩的相遇点，之后便需要将keyi位置的值与相遇点的值互换位置，这样keyi位置的值就放到了中间，成为了数组的中心——基准值，它意味着将数组分为两个子序列，左序列全是小于Keyi的值，右序列全是大于Keyi的值，这样便可以利用递归，一层一层再对左右两个子序列进行相同的步骤——将一个大的无序序列转化为多个小的序列，从而进行排序，最终排列为完全有序的序列。

 

        

方法1：Hoare版本——快排递归

        首先就是通过遍历将Key位置的值换到数组序列的中间部分，然后以Key为基准值，将序列递归分割，该方法的图解就像二叉树一样，所用的时间杂度为O(N*logN)，递归的层度为logN层。

        这种快排方法对于无序杂乱的序列来说，效率非常高，而对于接近有序和完全有序的数组序列，使用它效率就很低，它的时间复杂度会从O(N*logN)退化到O(N^2)，快排的效率就相当于冒泡排序，所以需要对Hoare方法进行相应的优化，使得快排对于任何类型的序列都能达到极高的效率！

        

        三数取中的思路：当我们知道数组的首部元素和尾部元素后，便可求出这个序列中间位置的数，我们只需要在首中尾这三个数中，挑出一个不是最大，也不是最小的中值，进行快速排序，便可加快提高快速排序效率。

        为什么要取中值？假设待待排序的数列是一组高度有序的数列，显然数列首部很可能是极小值，数组的尾部是极大值，若选取一个排在中间的值，即使在最坏的情况下，right从右往左走，left从左往右走，right与left只需要走到中间位置便可以相遇，而这个数也正好是整个序列的均值。大大提高了快排效率。使用三数取中法消除了预排输入不好的情况，并且减少了快排大约14%的比较次数。

        

        小区间优化主要是针对快速排序的递归版本，其思想是如果某一趟区间的长度小于某一长度则不需要继续进行递归快排，而是使用其他排序将该区间的元素排序好。

    以上就是本篇文章【快速排序之——Hoare方法一实现】的全部内容了，欢迎阅览 ！ 文章地址：http://w.yusign.com/news/2570.html 
     资讯      企业新闻      行情      企业黄页      同类资讯      首页      网站地图      返回首页 述古往 http://w.yusign.com/mobile/ , 查看更多