17 April 2013

冒泡排序是通过遍历整个链表,进行两两比较、交换操作的排序方法。然而,该方法在每一趟遍历过程中,只是简单的在两个相邻的元素中操作,如果能对每一次的比较结果进行利用,有可能提高排序效率。

快速排序就是这样的一种排序方法。同样是利用比较交换的思想,只是每次比较的元素选取不同:冒泡排序是通过比较相邻的两个元素,而快速排序是列表中元素与枢轴(Pivot)进行比较,大的元素交换到枢轴后面,小的元素交换到枢轴前面。这样就利用到了每一次的比较结果。

如果一个队列中只有三个元素,分别是2、3、1,如果以2为枢轴,3比2大,1比2小,那么只需要将最小的1放在枢轴2的位置上,最大的3放到最小的1的位置上,2放在最大的3的位置上。

快速排序一般步骤:

  • 选取枢轴,一般选取队列的第一个元素作为枢轴pivotkey;
  • 分别从队列的首和尾进行遍历。从首部找到第一个大于枢轴的元素为止,位置记为i,从尾部找到第一个小于枢轴的元素为止,位置记为j;
  • 交换操作是这三个元素进行交换。和前面提到的三个元素交换方法相类似,最小的元素j放在枢轴pivotkey上,最大的元素i放在最小的元素j的位置上,枢轴pivotkey放在最大的位置i上;
  • 从两端想中间遍历,一趟遍历直到交汇为止,即i==j;
  • 每一趟结束后,都会将当前队列分割成两个子队列,对两个子队列分别进行1~4步操作。直到子队列大小为1时,排序结束。

快速排序特性:

  • 快速排序每一趟排序结束,都会有一个元素(即枢轴Pivot)在最终位置上,其前面的元素都比它小,后面的元素都比它大;
  • 一趟排序结束,会产生两个子队列,分别对这两个子队列进行排序。这是分治的思想,分而治之;
  • 如果待排序队列基本有序,例如正序或者逆序,此时枢轴为队列中最大(小)的值,所以从两个开始遍历的操作只能找到一个队列中最小(大)的值来进行交换,此时快速排序变退化成了冒泡排序。例如队列1、2、3和2、3、1,前者虽然不需要交换操作,但是需要两趟遍历,第一趟确定1的位置,第二趟确实2和3的位置,后者只需要一次交换操作就可以完成排序;
  • 排序的效率和初始化队列排序情况与枢轴的选取有关。枢轴越接近队列的中间值越好,队列越混乱越好;
  • 快速排序通过使用分治的思想,减少了排序趟数,冒泡排序数量级是O(n),而快速排序数量级是O(log_{2} n),所以时间复杂度是O(nlog_{} n);
  • 排序的过程中只是交换的时候需要申请临时空间,空间复杂度是O(1);
  • 快速排序不稳定。

快速排序实例:

  • {49, 38, 65, 97, 76, 13, 27, 49} 初始序列;
  • {27, 38, , 97, 76, 13, 65, 49} 将49作为枢轴,并将其保存在临时空间内,从38开始遍历,找到第一个大于49的元素65,然后从49开始遍历,找到第一个小于49的元素27。将这3个元素进行交换,枢轴的位置存放最小的元素27,最小元素13的位置存放最大元素65,最大元素位置存放枢轴49。继续遍历,找到最小元素13,最大元素97。一趟排序结束;
  • {27, 38, 13}, 49, {76, 97, 65, 49} 一趟排序结果;
  • {13}, 27, {38}, 49, {49, 65}, 76, {97} 对两个子序列分别进行快速排序;
  • 13, 27, 38, 49, 49, 65, 76, 97 最终结果。

原文链接:快速排序(QUICK SORT),转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;