sift算法代码
❶ 排序法都有哪些
一、插入排序(InsertionSort)
1.基本思想：
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2.排序过程：
【示例】：
[初始关键字][49]38659776132749
J=2(38)[3849]659776132749
J=3(65)[384965]9776132749
J=4(97)[38496597]76132749
J=5(76)[3849657697]132749
J=6(13)[133849657697]2749
J=7(27)[13273849657697]49
J=8(49)[1327384949657697]
- ProcereInsertSort(VarR:FileType);
- //对R[1..N]按递增序进行插入排序,R[0]是监视哨//
- Begin
- forI:=2ToNDo//依次插入R[2],...,R[n]//
- begin
- R[0]:=R;J:=I-1;
- WhileR[0]<R[J]Do//查找R的插入位置//
- begin
- R[J+1]:=R[J];//将大于R的元素后移//
- J:=J-1
- end
- R[J+1]:=R[0];//插入R//
- end
- End;//InsertSort//
1.基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2.排序过程：
【示例】：
初始关键字[4938659776132749]
第一趟排序后13［38659776492749]
第二趟排序后1327［659776493849]
第三趟排序后132738[9776496549]
第四趟排序后13273849[49976576]
第五趟排序后1327384949[979776]
第六趟排序后132738494976[7697]
第七趟排序后13273849497676[97]
最后排序结果1327384949767697
- ProcereSelectSort(VarR:FileType);//对R[1..N]进行直接选择排序//
- Begin
- forI:=1ToN-1Do//做N-1趟选择排序//
- begin
- K:=I;
- ForJ:=I+1ToNDo//在当前无序区R[I..N]中选最小的元素R[K]//
- begin
- IfR[J]<R[K]ThenK:=J
- end;
- IfK<>IThen//交换R和R[K]//
- beginTemp:=R;R:=R[K];R[K]:=Temp;end;
- end
- End;//SelectSort//
1.基本思想：
两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。
2.排序过程：
设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
【示例】：
4913131313131313
3849272727272727
6538493838383838
9765384949494949
7697654949494949
1376976565656565
2727769776767676
4949497697979797
- ProcereBubbleSort(VarR:FileType)//从下往上扫描的起泡排序//
- Begin
- ForI:=1ToN-1Do//做N-1趟排序//
- begin
- NoSwap:=True;//置未排序的标志//
- ForJ:=N-1DownTo1Do//从底部往上扫描//
- begin
- IfR[J+1]<R[J]Then//交换元素//
- begin
- Temp:=R[J+1];R[J+1:=R[J];R[J]:=Temp;
- NoSwap:=False
- end;
- end;
- IfNoSwapThenReturn//本趟排序中未发生交换，则终止算法//
- end
- End;//BubbleSort//
1.基本思想：
在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
2.排序过程：
【示例】：
初始关键字[4938659776132749］
第一次交换后
［2738659776134949］
第二次交换后
［2738499776136549］
J向左扫描，位置不变，第三次交换后
［2738139776496549］
I向右扫描，位置不变，第四次交换后
［2738134976976549］
J向左扫描
［2738134976976549］
（一次划分过程）
初始关键字
［4938659776132749］
一趟排序之后
［273813］49［76976549］
二趟排序之后
［13］27［38］49［4965］76［97］
三趟排序之后1327384949［65］7697
最后的排序结果1327384949657697
各趟排序之后的状态
- ProcereParttion(VarR:FileType;L,H:Integer;VarI:Integer);
- //对无序区R[1,H]做划分，I给以出本次划分后已被定位的基准元素的位置//
- Begin
- I:=1;J:=H;X:=R;//初始化，X为基准//
- Repeat
- While(R[J]>=X)And(I<J)Do
- begin
- J:=J-1//从右向左扫描，查找第1个小于X的元素//
- IfI<JThen//已找到R[J]〈X//
- begin
- R:=R[J];//相当于交换R和R[J]//
- I:=I+1
- end;
- While(R<=X)And(I<J)Do
- I:=I+1//从左向右扫描，查找第1个大于X的元素///
- end;
- IfI<JThen//已找到R>X//
- begin R[J]:=R;//相当于交换R和R[J]//
- J:=J-1
- end
- UntilI=J;
- R:=X//基准X已被最终定位//
- End;//Parttion//
- ProcereQuickSort(VarR:FileType;S,T:Integer);//对R[S..T]快速排序//
- Begin
- IfS<TThen//当R[S..T]为空或只有一个元素是无需排序//
- begin
- Partion(R,S,T,I);//对R[S..T]做划分//
- QuickSort(R,S,I-1);//递归处理左区间R[S,I-1]//
- QuickSort(R,I+1,T);//递归处理右区间R[I+1..T]//
- end;
- End;//QuickSort//
1.基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2.堆的定义:N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
Ki≤K2iKi≤K2i+1(1≤I≤[N/2])
堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
3.排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆
- ProcereSift(VarR:FileType;I,M:Integer);
- //在数组R[I..M]中调用R，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1<=M时)均是堆//
- Begin
- X:=R;J:=2*I;//若J<=M,R[J]是R的左孩子//
- WhileJ<=MDo//若当前被调整结点R有左孩子R[J]//
- begin
- If(J<M)AndR[J].Key<R[J+1].KeyThen
- J:=J+1//令J指向关键字较大的右孩子//
- //J指向R的左、右孩子中关键字较大者//
- IfX.Key<R[J].KeyThen//孩子结点关键字较大//
- begin
- R:=R[J];//将R[J]换到双亲位置上//
- I:=J;J:=2*I//继续以R[J]为当前被调整结点往下层调整//
- end;
- Else
- Exit//调整完毕，退出循环//
- end
- R:=X;//将最初被调整的结点放入正确位置//
- End;//Sift//
- ProcereHeapSort(VarR:FileType);//对R[1..N]进行堆排序//
- Begin
- ForI:=NDivDownto1Do//建立初始堆//
- Sift(R,I,N)
- ForI:=NDownto2do//进行N-1趟排序//
- begin
- T:=R[1];R[1]:=R;R:=T;//将当前堆顶记录和堆中最后一个记录交换//
- Sift(R,1,I-1)//将R[1..I-1]重成堆//
- end
- End;//HeapSort//
1.选取排序方法需要考虑的因素：
(1)待排序的元素数目n；
(2)元素本身信息量的大小；
(3)关键字的结构及其分布情况；
(4)语言工具的条件，辅助空间的大小等。
2.小结：
(1)若n较小(n<=50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
这句话很重要它告诉我们自己写的算法是有改进到最优当然没有必要一直追求最优
(5)当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。
❷ java面试题 很急 谢谢
2, 归并排序(merge sort)体现了分治的思想，即将一个待排序数组分为两部分，对这两个部分进行归并排序，排序后，再对两个已经排序好的数组进行合并。这种思想可以用递归方式很容易实现。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
实现代码如下：
#include <stdio.h>
#include "common.h"
void merge(int data[], int p, int q, int r)
{
int i, j, k, n1, n2;
n1 = q - p + 1;
n2 = r - q;
int L[n1];
int R[n2];
for(i = 0, k = p; i < n1; i++, k++)
L[i] = data[k];
for(i = 0, k = q + 1; i < n2; i++, k++)
R[i] = data[k];
for(k = p, i = 0, j = 0; i < n1 && j < n2; k++)
{
if(L[i] > R[j])
{
data[k] = L[i];
i++;
}
else
{
data[k] = R[j];
j++;
}
}
if(i < n1)
{
for(j = i; j < n1; j++, k++)
data[k] = L[j];
}
if(j < n2)
{
for(i = j; i < n2; i++, k++)
data[k] = R[i];
}
}
void merge_sort(int data[], int p, int r)
{
if(p < r)
{
int q = (p + r) / 2;
merge_sort(data, p, q);
merge_sort(data, q + 1, r);
merge(data, p, q, r);
}
}
void test_merge_sort()
{
int data[] = {44, 12, 145, -123, -1, 0, 121};
printf("-------------------------------merge sort----------------------------\n");
out_int_array(data, 7);
merge_sort(data, 0, 6);
out_int_array(data, 7);
}
int main()
{
test_merge_sort();
return 0;
}
4.对于有n个结点的线性表（e0，e1，…，en-1），将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序。排序时参照的数据项称为排序码，通常选择结点的键值作为排序码。
若线性表中排序码相等的结点经某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。
在排序过程中，线性表的全部结点都在内存，并在内存中调整它们在线性表中的存储顺序，称为内排序。在排序过程中，线性表只有部分结点被调入内存，并借助内存调整结点在外存中的存放顺序的排序方法成为外排序。
下面通过一个表格简单介绍几种常见的内排序方法，以及比较一下它们之间的性能特点。
排序方法
简介
平均时间
最坏情况
辅助存储
是否稳定
简单排序
选择排序
反复从还未排好序的那部分线性表中选出键值最小的结点，并按从线性表中选出的顺序排列结点，重新组成线性表。直至未排序的那部分为空，则重新形成的线性表是一个有序的线性表。
O( )
O( )
O(1)
不稳定
直接插入排序
假设线性表的前面I个结点序列e0，e1，…，en-1是已排序的。对结点在这有序结点ei序列中找插入位置，并将ei插入，而使i+1个结点序列e0，e1，…，ei也变成排序的。依次对i=1，2，…，n-1分别执行这样的插入步骤，最终实现线性表的排序。
O( )
O( )
O(1)
稳定
冒泡排序
对当前还未排好序的范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让键值大的结点往下沉，键值小的结点往上冒。即，每当两相邻比较后发现它们的排列顺序与排序要求相反时，就将它们互换。
O( )
O( )
O(1)
稳定
希尔排序
对直接插入排序一种改进，又称“缩小增量排序”。先将整个待排序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
kn ln n
O( )
O(logn)
不稳定
快速排序
对冒泡排序的一种本质的改进。通过一趟扫视后，使待排序序列的长度能大幅度的减少。在一趟扫视后，使某个结点移到中间的正确位置，并使在它左边序列的结点的键值都比它的小，而它右边序列的结点的键值都不比它的小。称这样一次扫视为“划分”。每次划分使一个长序列变成两个新的较小子序列，对这两个小的子序列分别作同样的划分，直至新的子序列的长度为1使才不再划分。当所有子序列长度都为1时，序列已是排好序的了。
O(nlogn)
O( )
O(logn)
不稳定
堆排序
一种树形选择排序，是对直接选择排序的有效改进。一个堆是这样一棵顺序存储的二叉树，它的所有父结点（e[i]）的键值均不小于它的左子结点（e[2*i+1]）和右子结点（e[2*i+2]）的键值。初始时，若把待排序序列的n个结点看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换，并对少了一个结点后的n-1结点重新作调整，使之再次成为堆。这样，在根结点得到结点序列键值次最大值。依次类推，直到只有两个结点的堆，并对它们作交换，最后得到有序的n个结点序列。
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
将两个或两个以上的有序子表合并成一个新的有序表。对于两个有序子表合并一个有序表的两路合并排序来说，初始时，把含n个结点的待排序序列看作有n个长度都为1的有序子表所组成，将它们依次两两合并得到长度为2的若干有序子表，再对它们作两两合并……直到得到长度为n的有序表，排序即告完成。
O(nlogn)
O(nlogn)
O(n)
稳定
后面根据各种排序算法，给出了C语言的实现，大家在复习的时候可以做下参考。
u 选择排序
void ss_sort(int e[], int n)
{ int i, j, k, t;
for(i=0; i< n-1; i++) {
for(k=i, j=i+1; j<n; j++)
if(e[k]>e[j]) k=j;
if(k!=i) {
t=e[i]; e[i]=e[k]; e[k]=t;
}
}
}
u 直接插入排序
void si_sort(int e[], int n)
{ int i, j, t;
for(i=0; i< n; i++) {
for(t=e[i], j=i-1; j>=0&&t<e[j]; j--)
e[j+1]=e[j];
e[j+1]=t;
}
}
u 冒泡排序
void sb_sort(int e[], int n)
{ int j, p, h, t;
for(h=n-1; h>0; h=p) {
for(p=j=0; j<h; j++)
if(e[j]>e[j+1]) {
t=e[j]; e[j]=e[j+1]; e[j+1]=t;
p=j;
}
}
}
u 希尔排序
void shell(int e[], int n)
{ int j, k, h, y;
for(h=n/2; h>0; h=h/2)
for(j=h; j<n; j++) {
y=e[j];
for(k=j-h; k>0&&y<e[k]; k-=h)
e[k+h]=e[k];
e[k+h]=y;
}
}
u 堆排序
void sift(e, n, s)
int e[];
int n;
int s;
{ int t, k, j;
t=e[s];
k=s; j=2*k+1;
while(j<n) {
if(j<n-1&&e[j]<e[j+1])
j++;
if(t<e[j]) {
e[k]=e[j];
k=j;
j=2*k+1;
}else break;
}
e[k]=t;
}
void heapsorp (int e[], int n)
{ int i, k, t;
for(i=n/2-1; i>=0; i--)
sift(e, n, i);
for(k=n-1; k>=1; k--) {
t=e[0]; e[0]=e[k]; e[k]=t;
sift(e, k, 0);
}
}
u 快速排序
void r_quick(int e[], int low, int high)
{ int i, j, t;
if(low<high) {
i=low; j=high; t=e[low];
while(i<j) {
while (i<j&&e[j]>t) j--;
if(i<j) e[I++]=e[j];
while (i<j&&e[i]<=t) i++;
if(I<j) e[j--]=e[i];
}
e[i]=t;
r_quick(e,low,i-1);
r_quick(w,i+1,high);
}
}
另外，外排序是对大型文件的排序，待排序的记录存储在外存中，在排序过程中，内存只存储文件的一部分记录，整个排序过程需进行多次的内外存间的交换。
*** 查找
查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点。
按查找的条件分类，有按结点的关键码查找、关键码以外的其他数据项查找或其他数据项的组合查找等。按查找数据在内存或外存，分内存查找和外存查找。按查找目的，查找如果只是为了确定指定条件的结点存在与否，成为静态查找；查找是为确定结点的插入位置或为了删除找到的结点，称为动态查找。
这里简单介绍几种常见的查找方法。
u 顺序存储线性表的查找
这是最常见的查找方式。结点集合按线性表组织，采用顺序存储方式，结点只含关键码，并且是整数。如果线性表无序，则采用顺序查找，即从线性表的一端开始逐一查找。而如果线性表有序，则可以使用顺序查找、二分法查找或插值查找。
u 分块查找
分块查找的过程分两步，先用二分法在索引表中查索引项，确定要查的结点在哪一块。然后，再在相应块内顺序查找。
u 链接存储线性表的查找
对于链接存储线性表的查找只能从链表的首结点开始顺序查找。同样对于无序的链表和有序的链表查找方法不同。
u 散列表的查找
散列表又称杂凑表，是一种非常实用的查找技术。它的原理是在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确定结点的位置。其技术的关键在于解决两个问题。
I. 找一个好的散列函数
❸ Rob Hess给出的sift代码运行出现如下错误：error C2198: “cvKMeans2”: 用于调用的参数太少，请大侠指教
这是源码里针对找到图像特征点进行聚类的函数，运行到这里sift算法已经结束了。可以试着吧调用kmeans算法的部分注释掉，只执行sift算法然后打出来特征点看一下效果。我也不明白在一张图像上对特征点聚类的意义何在。对多张图像聚类还有意义。
❹ sift算法的matlab程序有一段没有看懂，请大神帮忙
这段matlab是个空壳，其核心是调用siftWin32.exe。（对windows）
Q1 这是pgm文件的格式要求。可以自己查去
Q2 !表示后面执行的命令是在系统shell里执行的。对windows来说就是命令提示符
Q3 那是可执行程序siftWin32.exe需要的参数
Q4 那是可执行程序siftWin32.exe需要的
❺ 各位大神，求一份尺度不变特征变换（SIFT算法）MATLAB实现的代码，最好有注释，小弟刚刚起步，谢谢了！
附件中是sift的matlab实现代码，在matlab中直接点击运行do_demo_3.m即可实现图像匹配
do_demo_1.m可以显示sift特征点
具体的详细用法你可以研究一下代码
这份代码是我目前在网上找到的最简洁的代码
希望对你能有所帮助