Tag Archives: 算法技术手册

算法技术手册 - 排序 - 求第K大的数

借助刚才的划分算法，我们可以比较容易的求出第K大的数，平均性能为O(N)，最坏可能是O(N^2)。

注意关于idx的选择，随机的话效果会比选left、right和median好，如果数据不是很特殊的化。
#include <stdio.h>

typedef int TYPE;

int cmp(TYPE a, TYPE b)
{
return a - b;
}

void swap(TYPE* a, TYPE* b)
{
TYPE tm[......]

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

划分是求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[......]