Web Analytics
yangyang

码农兼一个普普通通小青年

3-way partitioning


浅谈算法和数据结构: 四 快速排序

上篇文章介绍了时间复杂度为O(nlgn)的合并排序,本篇文章介绍时间复杂度同样为O(nlgn)但是排序速度比合并排序更快的快速排序(Quick Sort)。 快速排序是20世纪科技领域的十大算法之一 ,他由C. A. R. Hoare于1960年提出的一种划分交换排序。 快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中,对数组,列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。 本文首先介绍快速排序的思路,算法的实现、分析、优化及改进,最后分析了.NET 中列表排序的内部实现。 一 原理 快速排序的基本思想如下: 对数组进行随机化。 从数列中取出一个数作为中轴数(pivot)。 将比这个数大的数放到它的右边,小于或等于它的数放到它的左边。 再对左右区间重复第三步,直到各区间只有一个数。 如上图所 …

Quick Sort Median of three partitioning 3-way partitioning

  • 1