// 排序
从策划到设计制作，每一步都追求做到细腻，制作可持续发展的企业网站。为客户提供网站设计制作、成都网站制作、网站策划、网页设计、域名申请、网络空间、网络营销、VI设计、 网站改版、漏洞修补等服务。为客户提供更好的一站式互联网解决方案,以客户的口碑塑造优易品牌,携手广大客户,共同发展进步。
public class Array
{
public static int[] random(int n) //产生n个随机数，返回整型数组
{
if (n0)
{
int table[] = new int[n];
for (int i=0; itable.length; i++)
table[i] = (int)(Math.random()*100); //产生一个0～100之间的随机数
return table; //返回一个数组
}
return null;
}
public static void print(int[] table) //输出数组元素
{
if (table!=null)
for (int i=0; itable.length; i++)
System.out.print(" "+table[i]);
System.out.println();
}
public static void insertSort(int[] table) //直接插入排序
{ //数组是引用类型，元素值将被改变
System.out.println("直接插入排序");
for (int i=1; itable.length; i++) //n-1趟扫描
{
int temp=table[i], j; //每趟将table[i]插入到前面已排序的序列中
// System.out.print("移动");
for (j=i-1; j-1 temptable[j]; j--) //将前面较大元素向后移动
{
// System.out.print(table[j]+", ");
table[j+1] = table[j];
}
table[j+1] = temp; //temp值到达插入位置
System.out.print("第"+i+"趟: ");
print(table);
}
}
public static void shellSort(int[] table) //希尔排序
{
System.out.println("希尔排序");
for (int delta=table.length/2; delta0; delta/=2) //控制增量，增量减半，若干趟扫描
{
for (int i=delta; itable.length; i++) //一趟中若干组，每个元素在自己所属组内进行直接插入排序
{
int temp = table[i]; //当前待插入元素
int j=i-delta; //相距delta远
while (j=0 temptable[j]) //一组中前面较大的元素向后移动
{
table[j+delta] = table[j];
j-=delta; //继续与前面的元素比较
}
table[j+delta] = temp; //插入元素位置
}
System.out.print("delta="+delta+" ");
print(table);
}
}
private static void swap(int[] table, int i, int j) //交换数组中下标为i、j的元素
{
if (i=0 itable.length j=0 jtable.length i!=j) //判断i、j是否越界
{
int temp = table[j];
table[j] = table[i];
table[i] = temp;
}
}
public static void bubbleSort(int[] table) //冒泡排序
{
System.out.println("冒泡排序");
boolean exchange=true; //是否交换的标记
for (int i=1; itable.length exchange; i++) //有交换时再进行下一趟，最多n-1趟
{
exchange=false; //假定元素未交换
for (int j=0; jtable.length-i; j++) //一次比较、交换
if (table[j]table[j+1]) //反序时，交换
{
int temp = table[j];
table[j] = table[j+1];
table[j+1] = temp;
exchange=true; //有交换
}
System.out.print("第"+i+"趟: ");
print(table);
}
}
public static void quickSort(int[] table) //快速排序
{
quickSort(table, 0, table.length-1);
}
private static void quickSort(int[] table, int low, int high) //一趟快速排序，递归算法
{ //low、high指定序列的下界和上界
if (lowhigh) //序列有效
{
int i=low, j=high;
int vot=table[i]; //第一个值作为基准值
while (i!=j) //一趟排序
{
while (ij vot=table[j]) //从后向前寻找较小值
j--;
if (ij)
{
table[i]=table[j]; //较小元素向前移动
i++;
}
while (ij table[i]vot) //从前向后寻找较大值
i++;
if (ij)
{
table[j]=table[i]; //较大元素向后移动
j--;
}
}
table[i]=vot; //基准值的最终位置
System.out.print(low+".."+high+", vot="+vot+" ");
print(table);
quickSort(table, low, j-1); //前端子序列再排序
quickSort(table, i+1, high); //后端子序列再排序
}
}
public static void selectSort(int[] table) //直接选择排序
{
System.out.println("直接选择排序");
for (int i=0; itable.length-1; i++) //n-1趟排序
{ //每趟在从table[i]开始的子序列中寻找最小元素
int min=i; //设第i个数据元素最小
for (int j=i+1; jtable.length; j++) //在子序列中查找最小值
if (table[j]table[min])
min = j; //记住最小元素下标
if (min!=i) //将本趟最小元素交换到前边
{
int temp = table[i];
table[i] = table[min];
table[min] = temp;
}
System.out.print("第"+i+"趟: ");
print(table);
}
}
private static void sift(int[] table, int low, int high) //将以low为根的子树调整成最小堆
{ //low、high是序列下界和上界
int i=low; //子树的根
int j=2*i+1; //j为i结点的左孩子
int temp=table[i]; //获得第i个元素的值
while (j=high) //沿较小值孩子结点向下筛选
{
if (jhigh table[j]table[j+1]) //数组元素比较（改成为最大堆）
j++; //j为左右孩子的较小者
if (temptable[j]) //若父母结点值较大（改成为最大堆）
{
table[i]=table[j]; //孩子结点中的较小值上移
i=j; //i、j向下一层
j=2*i+1;
}
else
j=high+1; //退出循环
}
table[i]=temp; //当前子树的原根值调整后的位置
System.out.print("sift "+low+".."+high+" ");
print(table);
}
public static void heapSort(int[] table)
{
System.out.println("堆排序");
int n=table.length;
for (int j=n/2-1; j=0; j--) //创建最小堆
sift(table, j, n-1);
// System.out.println("最小堆？ "+isMinHeap(table));
for (int j=n-1; j0; j--) //每趟将最小值交换到后面，再调整成堆
{
int temp = table[0];
table[0] = table[j];
table[j] = temp;
sift(table, 0, j-1);
}
}
public static void mergeSort(int[] X) //归并排序
{
System.out.println("归并排序");
int n=1; //已排序的子序列长度，初值为1
int[] Y = new int[X.length]; //Y数组长度同X数组
do
{
mergepass(X, Y, n); //一趟归并，将X数组中各子序列归并到Y中
print(Y);
n*=2; //子序列长度加倍
if (nX.length)
{
mergepass(Y, X, n); //将Y数组中各子序列再归并到X中
print(X);
n*=2;
}
} while (nX.length);
}
private static void mergepass(int[] X, int[] Y, int n) //一趟归并
{
System.out.print("子序列长度n="+n+" ");
int i=0;
while (iX.length-2*n+1)
{
merge(X,Y,i,i+n,n);
i += 2*n;
}
if (i+nX.length)
merge(X,Y,i,i+n,n); //再一次归并
else
for (int j=i; jX.length; j++) //将X剩余元素复制到Y中
Y[j]=X[j];
}
private static void merge(int[] X, int[] Y, int m, int r, int n) //一次归并
{
int i=m, j=r, k=m;
while (ir jr+n jX.length) //将X中两个相邻子序列归并到Y中
if (X[i]X[j]) //较小值复制到Y中
Y[k++]=X[i++];
else
Y[k++]=X[j++];
while (ir) //将前一个子序列剩余元素复制到Y中
Y[k++]=X[i++];
while (jr+n jX.length) //将后一个子序列剩余元素复制到Y中
Y[k++]=X[j++];
}
public static void main(String[] args)
{
// int[] table = {52,26,97,19,66,8,49};//Array.random(9);{49,65,13,81,76,97,38,49};////{85,12,36,24,47,30,53,91,76};//;//{4,5,8,1,2,7,3,6};// {32,26,87,72,26,17};//
int[] table = {13,27,38,49,97,76,49,81}; //最小堆
System.out.print("关键字序列: ");
Array.print(table);
// Array.insertSort(table);
// Array.shellSort(table);
// Array.bubbleSort(table);
// Array.quickSort(table);
// Array.selectSort(table);
// Array.heapSort(table);
// Array.mergeSort(table);
System.out.println("最小堆序列? "+Array.isMinHeap(table));
}
//第9章习题
public static boolean isMinHeap(int[] table) //判断一个数据序列是否为最小堆
{
if (table==null)
return false;
int i = table.length/2 -1; //最深一棵子树的根结点
while (i=0)
{
int j=2*i+1; //左孩子
if (jtable.length)
if (table[i]table[j])
return false;
else
if (j+1table.length table[i]table[j+1]) //右孩子
return false;
i--;
}
return true;
}
}
/*
程序运行结果如下：
关键字序列: 32 26 87 72 26 17 8 40
直接插入排序
第1趟排序: 26 32 87 72 26 17 8 40
第2趟排序: 26 32 87 72 26 17 8 40
第3趟排序: 26 32 72 87 26 17 8 40
第4趟排序: 26 26 32 72 87 17 8 40 //排序算法稳定
第5趟排序: 17 26 26 32 72 87 8 40
第6趟排序: 8 17 26 26 32 72 87 40
第7趟排序: 8 17 26 26 32 40 72 87
关键字序列: 42 1 74 25 45 29 87 53
直接插入排序
第1趟排序: 1 42 74 25 45 29 87 53
第2趟排序: 1 42 74 25 45 29 87 53
第3趟排序: 1 25 42 74 45 29 87 53
第4趟排序: 1 25 42 45 74 29 87 53
第5趟排序: 1 25 29 42 45 74 87 53
第6趟排序: 1 25 29 42 45 74 87 53
第7趟排序: 1 25 29 42 45 53 74 87
关键字序列: 21 12 2 40 99 97 68 57
直接插入排序
第1趟排序: 12 21 2 40 99 97 68 57
第2趟排序: 2 12 21 40 99 97 68 57
第3趟排序: 2 12 21 40 99 97 68 57
第4趟排序: 2 12 21 40 99 97 68 57
第5趟排序: 2 12 21 40 97 99 68 57
第6趟排序: 2 12 21 40 68 97 99 57
第7趟排序: 2 12 21 40 57 68 97 99
关键字序列: 27 38 65 97 76 13 27 49 55 4
希尔排序
delta=5 13 27 49 55 4 27 38 65 97 76
delta=2 4 27 13 27 38 55 49 65 97 76
delta=1 4 13 27 27 38 49 55 65 76 97
关键字序列: 49 38 65 97 76 13 27 49 55 4 //严书
希尔排序
delta=5 13 27 49 55 4 49 38 65 97 76
delta=2 4 27 13 49 38 55 49 65 97 76 //与严书不同
delta=1 4 13 27 38 49 49 55 65 76 97
关键字序列: 65 34 25 87 12 38 56 46 14 77 92 23
希尔排序
delta=6 56 34 14 77 12 23 65 46 25 87 92 38
delta=3 56 12 14 65 34 23 77 46 25 87 92 38
delta=1 12 14 23 25 34 38 46 56 65 77 87 92
关键字序列: 84 12 43 62 86 7 90 91
希尔排序
delta=4 84 7 43 62 86 12 90 91
delta=2 43 7 84 12 86 62 90 91
delta=1 7 12 43 62 84 86 90 91
关键字序列: 32 26 87 72 26 17
冒泡排序
第1趟排序: 26 32 72 26 17 87
第2趟排序: 26 32 26 17 72 87
第3趟排序: 26 26 17 32 72 87
第4趟排序: 26 17 26 32 72 87
第5趟排序: 17 26 26 32 72 87
关键字序列: 1 2 3 4 5 6 7 8
冒泡排序
第1趟排序: 1 2 3 4 5 6 7 8
关键字序列: 1 3 2 4 5 8 6 7
冒泡排序
第1趟排序: 1 2 3 4 5 6 7 8
第2趟排序: 1 2 3 4 5 6 7 8
关键字序列: 4 5 8 1 2 7 3 6
冒泡排序
第1趟排序: 4 5 1 2 7 3 6 8
第2趟排序: 4 1 2 5 3 6 7 8
第3趟排序: 1 2 4 3 5 6 7 8
第4趟排序: 1 2 3 4 5 6 7 8
第5趟排序: 1 2 3 4 5 6 7 8
关键字序列: 38 26 97 19 66 1 5 49
0..7, vot=38 5 26 1 19 38 66 97 49
0..3, vot=5 1 5 26 19 38 66 97 49
2..3, vot=26 1 5 19 26 38 66 97 49
5..7, vot=66 1 5 19 26 38 49 66 97
关键字序列: 38 5 49 26 19 97 1 66
0..7, vot=38 1 5 19 26 38 97 49 66
0..3, vot=1 1 5 19 26 38 97 49 66
1..3, vot=5 1 5 19 26 38 97 49 66
2..3, vot=19 1 5 19 26 38 97 49 66
5..7, vot=97 1 5 19 26 38 66 49 97
5..6, vot=66 1 5 19 26 38 49 66 97
关键字序列: 49 38 65 97 76 13 27 49
0..7, vot=49 49 38 27 13 49 76 97 65
0..3, vot=49 13 38 27 49 49 76 97 65
0..2, vot=13 13 38 27 49 49 76 97 65
1..2, vot=38 13 27 38 49 49 76 97 65
5..7, vot=76 13 27 38 49 49 65 76 97
关键字序列: 27 38 65 97 76 13 27 49 55 4
low=0 high=9 vot=27 4 27 13 27 76 97 65 49 55 38
low=0 high=2 vot=4 4 27 13 27 76 97 65 49 55 38
low=1 high=2 vot=27 4 13 27 27 76 97 65 49 55 38
low=4 high=9 vot=76 4 13 27 27 38 55 65 49 76 97
low=4 high=7 vot=38 4 13 27 27 38 55 65 49 76 97
low=5 high=7 vot=55 4 13 27 27 38 49 55 65 76 97
关键字序列: 38 26 97 19 66 1 5 49
直接选择排序
第0趟排序: 1 26 97 19 66 38 5 49
第1趟排序: 1 5 97 19 66 38 26 49
第2趟排序: 1 5 19 97 66 38 26 49
第3趟排序: 1 5 19 26 66 38 97 49
第4趟排序: 1 5 19 26 38 66 97 49
第5趟排序: 1 5 19 26 38 49 97 66
第6趟排序: 1 5 19 26 38 49 66 97
最小堆
关键字序列: 81 49 76 27 97 38 49 13 65
sift 3..8 81 49 76 13 97 38 49 27 65
sift 2..8 81 49 38 13 97 76 49 27 65
sift 1..8 81 13 38 27 97 76 49 49 65
sift 0..8 13 27 38 49 97 76 49 81 65
13 27 38 49 97 76 49 81 65
sift 0..7 27 49 38 65 97 76 49 81 13
sift 0..6 38 49 49 65 97 76 81 27 13
sift 0..5 49 65 49 81 97 76 38 27 13
sift 0..4 49 65 76 81 97 49 38 27 13
sift 0..3 65 81 76 97 49 49 38 27 13
sift 0..2 76 81 97 65 49 49 38 27 13
sift 0..1 81 97 76 65 49 49 38 27 13
sift 0..0 97 81 76 65 49 49 38 27 13
最大堆
关键字序列: 49 65 13 81 76 27 97 38 49
sift 3..8 49 65 13 81 76 27 97 38 49
sift 2..8 49 65 97 81 76 27 13 38 49
sift 1..8 49 81 97 65 76 27 13 38 49
sift 0..8 97 81 49 65 76 27 13 38 49
97 81 49 65 76 27 13 38 49
sift 0..7 81 76 49 65 49 27 13 38 97
sift 0..6 76 65 49 38 49 27 13 81 97
sift 0..5 65 49 49 38 13 27 76 81 97
sift 0..4 49 38 49 27 13 65 76 81 97
sift 0..3 49 38 13 27 49 65 76 81 97
sift 0..2 38 27 13 49 49 65 76 81 97
sift 0..1 27 13 38 49 49 65 76 81 97
sift 0..0 13 27 38 49 49 65 76 81 97
关键字序列: 52 26 97 19 66 8 49
归并排序
子序列长度n=1 26 52 19 97 8 66 49
子序列长度n=2 19 26 52 97 8 49 66
子序列长度n=4 8 19 26 49 52 66 97
关键字序列: 13 27 38 49 97 76 49 81 65
最小堆序列? true
*/
这几天继续在看Lowe大神的SIFT神作，看的眼花手脚抽筋。也是醉了！！！！实在看不下去，来点干货。我们知道opencv下自带SIFT特征检测以及MATCH匹配的库，这些库完全可以让我们进行傻瓜似的操作。但实际用起来的时候还不是那么简单。下文将对一个典型的基于OPENCV的SIFT特征点提取以及匹配的例程进行分析，并由此分析详细的对OPENCV中SIFT算法的使用进行一个介绍。
OPENCV下SIFT特征点提取与匹配的大致流程如下：
读取图片-》特征点检测（位置，角度，层）-》特征点描述的提取（16*8维的特征向量）-》匹配-》显示
其中，特征点提取主要有两个步骤，见上行黄子部分。下面做具体分析。
1、使用opencv内置的库读取两幅图片
2、生成一个SiftFeatureDetector的对象，这个对象顾名思义就是SIFT特征的探测器，用它来探测衣服图片中SIFT点的特征，存到一个KeyPoint类型的vector中。这里有必要说keypoint的数据结构，涉及内容较多，具体分析查看opencv中keypoint数据结构分析，里面讲的自认为讲的还算详细（表打我……）。简而言之最重要的一点在于：
keypoint只是保存了opencv的sift库检测到的特征点的一些基本信息，但sift所提取出来的特征向量其实不是在这个里面，特征向量通过SiftDescriptorExtractor 提取，结果放在一个Mat的数据结构中。这个数据结构才真正保存了该特征点所对应的特征向量。具体见后文对SiftDescriptorExtractor 所生成的对象的详解。
就因为这点没有理解明白耽误了一上午的时间。哭死！
3、对图像所有KEYPOINT提取其特征向量：
得到keypoint只是达到了关键点的位置，方向等信息，并无该特征点的特征向量，要想提取得到特征向量就还要进行SiftDescriptorExtractor 的工作，建立了SiftDescriptorExtractor 对象后，通过该对象，对之前SIFT产生的特征点进行遍历，找到该特征点所对应的128维特征向量。具体方法参见opencv中SiftDescriptorExtractor所做的SIFT特征向量提取工作简单分析。通过这一步后，所有keypoint关键点的特征向量被保存到了一个MAT的数据结构中，作为特征。
4、对两幅图的特征向量进行匹配，得到匹配值。
两幅图片的特征向量被提取出来后，我们就可以使用BruteForceMatcher对象对两幅图片的descriptor进行匹配，得到匹配的结果到matches中，这其中具体的匹配方法暂没细看，过段时间补上。
至此，SIFT从特征点的探测到最后的匹配都已经完成，虽然匹配部分不甚了解，只扫对于如何使用OPENCV进行sift特征的提取有了一定的理解。接下来可以开始进行下一步的工作了。
附:使用OPENCV下SIFT库做图像匹配的例程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// opencv_empty_proj.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include opencv.hpp
#include features2d/features2d.hpp
#includenonfree/nonfree.hpp
#includelegacy/legacy.hpp
#include
using namespace std;
using namespace cv;
int _tmain(int argc, _TCHAR* argv[])
{
const char* imagename = "img.jpg";
//从文件中读入图像
Mat img = imread(imagename);
Mat img2=imread("img2.jpg");
//如果读入图像失败
if(img.empty())
{
fprintf(stderr, "Can not load image %s\n", imagename);
return -1;
}
if(img2.empty())
{
fprintf(stderr, "Can not load image %s\n", imagename);
return -1;
}
//显示图像
imshow("image before", img);
imshow("image2 before",img2);
//sift特征检测
SiftFeatureDetector siftdtc;
vectorkp1,kp2;
siftdtc.detect(img,kp1);
Mat outimg1;
drawKeypoints(img,kp1,outimg1);
imshow("image1 keypoints",outimg1);
KeyPoint kp;
vector::iterator itvc;
for(itvc=kp1.begin();itvc!=kp1.end();itvc++)
{
cout"angle:"angle"\t"class_id"\t"octave"\t"pt"\t"responseendl;
}
siftdtc.detect(img2,kp2);
Mat outimg2;
drawKeypoints(img2,kp2,outimg2);
imshow("image2 keypoints",outimg2);
SiftDescriptorExtractor extractor;
Mat descriptor1,descriptor2;
BruteForceMatcherL2 matcher;
vector matches;
Mat img_matches;
extractor.compute(img,kp1,descriptor1);
extractor.compute(img2,kp2,descriptor2);
imshow("desc",descriptor1);
coutendldescriptor1endl;
matcher.match(descriptor1,descriptor2,matches);
drawMatches(img,kp1,img2,kp2,matches,img_matches);
imshow("matches",img_matches);
//此函数等待按键，按键盘任意键就返回
waitKey();
return 0;
}
/**
根据你需要java的要求， 写了一个实现。
这个是一个整数最小优先的堆，只实现了加入功能。
应该还有删除，清空等功能，但并不是必须的。
你可以自己尝试实现。
测试为生成一组随机数，加入队列，每次加入后都察看一下堆的最优先元素是多少。
如果还有疑问 ,
至邮件:tazerkinq@163.com
*/
public class Heap {
int[] heap; //堆的储存空间
int size; //当前的元素的数量
Heap() {
size = 0; //初始化数量为0
heap = new int[1024]; //预留空间1024,为了操作方便,0位置被弃用
}
void add(int e){ //加入新的元素,也是维护堆的主要地方之一
int i = ++size; //数量增加一, 并用临时变量记录此位置
while(( 1i ) ( eheap[i/2] )){ //判断e是否小于父节点的元素, 如否,则停止
heap[i] = heap[i/2]; //如是, 则移动父节点元素当i记录位置
i/=2; //i继续向上迭代,指向刚才父节点的位置
}
heap[i] = e; //该位置即为元素最终位置
}
int peek(){ //返回堆头的元素
return heap[1]; //数组下标1的元素即是
} //当然如果当前元素为空的话,返回的则是初始值
int size(){ //返回当前元素数目
return size;
}
public static void main(String[] args) {
Heap h = new Heap();
for(int i=0;i100;i++){
int k=(int)(10000*Math.random()); //随机生成一个整数
h.add(k); //加入到堆中
System.out.printf(
"Currently adding number is %5d.\t"+
"Currently priority number is %5d.%n",k,h.peek()); //输出生成的随机数,并且输出该堆的优先元素
}
}
}
哈哈，我有一个基于opencv实现的sift，我把代码贴出来，你自己看看吧~~~
void sift_detector_and_descriptors(IplImage* i_left,IplImage* i_right)
{
Mat mat_image_left=Mat(i_left,false);
Mat mat_image_right=Mat(i_right,false);
cv::SiftFeatureDetector *pDetector=new cv::SiftFeatureDetector;
pDetector-detect(mat_image_left,left_key_point);
pDetector-detect(mat_image_right,right_key_point);
Mat left_image_descriptors,right_image_descriptors;
cv::SiftDescriptorExtractor *descriptor_extractor=new cv::SiftDescriptorExtractor;
descriptor_extractor-compute(mat_image_left,left_key_point,left_image_descriptors);
descriptor_extractor-compute(mat_image_right,right_key_point,right_image_descriptors);
Mat result_l,result_r;
drawKeypoints(mat_image_left,left_key_point,result_l,Scalar::all(-1),0);
drawKeypoints(mat_image_right,right_key_point,result_r,Scalar::all(-1),0);
//imshow("result_of_left_detector_sift",result_l);
//imshow("result_of_right_detector_sift",result_r);
Mat result_of_sift_match;
BruteForceMatcherL2float matcher;
matcher.match(left_image_descriptors,right_image_descriptors,result_of_point_match);
drawMatches(mat_image_left,left_key_point,mat_image_right,right_key_point,result_of_sift_match,result_of_sift_match);
imshow("matches_of_sift",result_of_sift_match);
imwrite("matches_of_sift.jpg",result_of_sift_match);
}
void main()
{
IplImage *n_left_image=cvLoadImage("D:\\lena.jpg");
IplImage *n_right_image=cvLoadImage("D:\\lena_r.jpg");
sift_detector_and_descriptors(n_left_image,n_right_image);
cvWaitKey(0);
}
这就是核心代码了，至于opencv所要用到的库，你自己弄一下吧，每个人的opencv版本不一样，这个都市不同的，希望能够帮到你~
