快速排序 |
您所在的位置：网站首页 › 快速排序算法的优点 › 快速排序 |
快速排序
|
说明：这篇文章正如标题所说，主要看分析 如果嫌弃文章太长，可以直接通过最后面的小结来选看 快速排序 算法思想 快速排序可能是现实应用中最多的一种，但是没有一种排序算法能适应所有的情况，在最糟糕的情况下，快速排序性能就比较差了。但是对于大多数情况下，对于大量的随机数据的排序，快速排序算法的效率还是非常高的。（前提是将快速排序算法实现的小细节实现到位，快速排序的特点是自己编写是容易写错） 它的基本思想是：假设待排序的序列L[1....n]，首先选取一个主元pivot，然后将待排序的元素分割成两部分，左边的部分L[1,k-1]小于pivot，右边的部分L[k + 1]大于pivot（其实这是一个很重要的问题：是严格小于还是小于等于，是严格大于还是大于等于)考虑如何具体的实现，后面会说明怎样考虑）。pivot就是放在最终正确的位置k上,这就是一趟排序的过程。然后递归的对两个子序列重复上述的过程，直到只有一个元素或者为空（这两种情况都是有可能发生的，例如考虑{1，2,3，4，5}选取元素3之后，划分为两个子集{1,2}，{4,5}继续选取主元2之后划分成{1}和空集，选取主元4之后，划分成{5}和空集） 如图所示: 挑选一个主元，将原来的元素分成两部分。再递归的解决做部分和右部分。最后结果伪码描述：  需要注意的是，主元的选取关乎子集的划分情况进而影响算法的时间复杂度，因此先考虑时间复杂度
Q：主元怎么选？元素怎么分？ 首先考虑一下什么是快速排序算法的最好情况？ 每次主元正好取到中间，会将元素一分为二。 关于时间复杂度的分析？分析博文 简单说一下就是： 最好的情况下：主元的选取正好能够将划分成左右子集个数相等。 //时间复杂度分析 T（n）≤2T（n/2） +O(n)，T（1）=0 T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+O(2n) T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+O(3n) …… T（n）≤nT（1）+O(（log2n）×n)= O(nlogn)最差的情况是：主元的选取将子集划分成空集和个数为N-1的子集 //时间复杂度分析 T(n) = O(n) + T(n-1) //其中的O(n)指的是，主元选取之后遍历元素来划分子集。 = O(n) + O(n-1) + T(n-2) = O(n) + O(n-1) + ... +O(1) = O(n^2)然后考虑主元的选择和子集的划分 主元选择： 这里只说明了三种情况（你也可以自己通过其他的方法选取主元，尽量能够将子集等分为主，时间复杂度低） 1.选取A[0] 2.随机选取 3.选取3点的中位数第一种情况，选取最左边的元素。 考虑：数组是完全有序的（好像数据结构书中就是取最左端的元素）  （在调用完Median3之后） i->left+1和j->right-2存放指针，主元6‘藏在右边(right-1)’ 首先比较i指针指向的元素和主元的大小，发现8>6错误（因为左边存放的是小于主元的元素），此时i就指向这个位置错误的元素， 然后考虑j指针指向的元素7>6,正确，j–左移，j指向2，于是位置错误，此时j就指向这个位置错误的元素 两边发现i和j指向的元素的位置都错误的时候，交换i和j指向的元素交换，然后进行下一轮的比较。 
i右移，找到错误位置的元素， j左移，找到错误位置的元素， 元素交换 …
|
刚开始有N个元素，先选主元A[0]，扫描一遍全体以完成子集的划分。时间复杂度为O(N) 然后有N-1个元素，先选主元A[1]，扫描一遍全体，完成自己的划分，时间复杂度为O(N-1) … 这种情况下整个算法的时间复杂度是O(N^2)级别，对于排序算法来说非常糟糕。 数组本身就是有序的，还需要花费O(N-1)级别的时间。 第二种情况，随机取？但是rand()函数也存在一定的开销 第三种情况，取头、中、尾的中位数。 
3步的if语句，保证了头、中、尾的次序 此时直接就将中位数返回吗？ 并不是。子集划分的时候center在中间，并不需要考虑left和right两个元素。因此交换swap（center，right-1）， 此时只需要考虑left+1和right-2之间的元素
在这里的时候，5和9交换之后，i++寻找错误位置的元素，i->0正确，i->3正确，会继续i++，此时i ->9发现位置发生错误停下移动，进而移动j，寻找位置错误的元素。
考虑j，j–,左移，此时j->3,发现位置错误停下移动，这个时候应该结束了，是程序的边界i【本文地址】
今日新闻 |
推荐新闻 |