Tag Archives: 排序

算法技术手册 – 排序 – 计数排序

如果已知被排序的n个元素,值范围固定在在 "[0,k)"内],那么计数排序是最好的选择,它具有线性复杂度。

这个约束有些过强,有些时候,可以将不满足这个条件的转化一下:
比如 [-k, k)映射]到[0, 2k)等]。
再比如1/p的小树映射到p k-p等等。

下面上算法,主要走两遍:
首先建立k个桶
(1)扫描n个元素,增加对应桶中的计数
(2)从小到大扫描k个桶,计数非零则减一,然后顺序、依次输出。

源代码:
#include <stdio.h>[......]

继续阅读

算法技术手册 - 排序 - 堆排序

堆排序依赖于上午写道的构建堆和调整堆。

基本思想:
(1)首先执行BuildHeap(以最大堆为例),则arr[0]已经是最大元素了,如果我们要按照从小到大排序,那么它应该被放在arr[n-1]上,于是,我们swap arr[0]和arr[n-1]。
(2)类似的,我们让i从n-1到0,依次执行调整堆,AdjustHeap(i,n),每次调整完成后,堆顶部一定是最大元素,正好把他换到i-2上。
上述的思路和选择排序是不是非常相似!

改进:
调整堆实际用到了递归方法,而其实它是[......]

继续阅读

算法技术手册 – 排序 – 选择排序

选择排序,思想非常简单,分为selectMax和selectSort两个部分。

selectMax:
每次选择区间内最大的数,返回其Index
selectSort
1、从右到左依次扫描i(除idx=0,因为选到最后,最小的一定在最左边),规定区间为[0, i]
2、调用selectMax,获得最大的maxIndex。
3、这个i位置应该是第i大的数的位置,也就是maxIndex的数的位置,因此,如果i!=maxIndex,swap之。

算法复杂度,不管是最坏、平均还是最好[......]

继续阅读

算法技术手册 – 排序 – 划分

划分是求Kth、快速排序等的基础。

目标:一个数组array,给定一个pivotIndex,要求将array[pivotIndex]的对象至于storeIndex位置,使得[left,storeIndex)的元素都小于array[pivotIndex],而使得大于[storeIndex,right]的元素都大于等于array[pivotIndex]。

算法步骤:
1、交换array[pivotIndex]和array[right],记前者为pivot
2、用store表示pivo[......]

继续阅读

算法技术手册 - 排序 - 插入排序

插入排序:

类似洗牌,将从1~N的数字分别插入到合适的位置,当然对于数组来说,需要做相应的移动。基础的方法是依次挪动,较为快捷的方法是memmove。

需要说明的是,按照Linux的man手册,memmove是支持内存overlap的,即可以部分重叠,函数内部会处理好其他的事情,因此类似书上的先移动到buffer,再从buffer移动到另一个位置是没必要的!
#include <stdio.h>
#include <string.h>

typedef[......]

继续阅读