标签:分区

快速排序QuickSort

发表于3年前(Dec 24, 2014 10:16:45 AM)  阅读 454  评论 0

分类: Java 算法 排序

标签: quicksort 分区 快速排序

快速排序(QuickSort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列—–摘自百度百科。

快速排序的核心算法是分区,如何将一个数组分成两个子数组,前面的数组所有元素都小于等于后面数组的所有元素,关键字夹在两个数组中间。实现见partition方法,这里关键字取的是数组最后一个元素,实际上取任何元素都行。

快速排序的时间复杂度为O(nlogn),是原地排序。