Category Archives: Algorithm

快速排序(1)

快速排序

快速排序(以下简称快排)是一种排序算法,有C.A.R.Hoare所发展的,就如同他的名字一样,它的特点就是快。以平均效能来说,排序n个项目有O(n log n)次比较。在最差的效能下它需要O(n^2)次比较,所以它是一种不稳定排序法。

思路:

快排使用的分治(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。令其中一个子序列的元素小于另一个子序列,在对两个子序列采取同样递归操作。

(顺序排列)步骤为:

  1. 在数列中挑出一个元素作为"基准"(pivot)。
  2. 将比基准小的移到基准前面,比基准大的移到基准后面(相同的可以不必理会)。
  3. 递归(recursive)地对两个子序列排序。

Read more »

计数排序法

计数排序一般用于类似统计数组中元素出现次数。

条件:数组中的元素范围必须确定,如0~k。

基本思路:以被计数数组的元素值作为计数数组的索引(数组下标)对计数数组自增。

例题:统计输入的50个数据中出现最多的元素,元素范围在0~99。

Read more »