算法中的横向排列

1. 数据结构 java开发中常用的排序算法有哪些

排序算法有很多，所以在特定情景中使用哪一种算法很重要。为了选择合适的算法，可以按照建议的顺序考虑以下标准：
（1）执行时间
（2）存储空间
（3）编程工作
对于数据量较小的情形，（1）（2）差别不大，主要考虑（3）；而对于数据量大的，（1）为首要。

主要排序法有：
一、冒泡（Bubble）排序——相邻交换
二、选择排序——每次最小/大排在相应的位置
三、插入排序——将下一个插入已排好的序列中
四、壳（Shell）排序——缩小增量
五、归并排序
六、快速排序
七、堆排序
八、拓扑排序

一、冒泡（Bubble）排序

----------------------------------Code 从小到大排序n个数------------------------------------
void BubbleSortArray()
{
for(int i=1;i<n;i++)
{
for(int j=0;i<n-i;j++)
{
if(a[j]>a[j+1])//比较交换相邻元素
{
int temp;
temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
}
}
}
}
-------------------------------------------------Code------------------------------------------------
效率 O（n²）,适用于排序小列表。

二、选择排序
----------------------------------Code 从小到大排序n个数--------------------------------
void SelectSortArray()
{
int min_index;
for(int i=0;i<n-1;i++)
{
min_index=i;
for(int j=i+1;j<n;j++)//每次扫描选择最小项
if(arr[j]<arr[min_index]) min_index=j;
if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置
{
int temp;
temp=arr[i]; arr[i]=arr[min_index]; arr[min_index]=temp;
}
}
}
-------------------------------------------------Code-----------------------------------------
效率O（n²），适用于排序小的列表。

三、插入排序
--------------------------------------------Code 从小到大排序n个数-------------------------------------
void InsertSortArray()
{
for(int i=1;i<n;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分
{
int temp=arr[i];//temp标记为未排序第一个元素
int j=i-1;
while (j>=0 && arr[j]>temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
}
------------------------------Code--------------------------------------------------------------
最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，适用于排序小列表
若列表基本有序，则插入排序比冒泡、选择更有效率。

四、壳（Shell）排序——缩小增量排序
-------------------------------------Code 从小到大排序n个数-------------------------------------
void ShellSortArray()
{
for(int incr=3;incr<0;incr--)//增量递减，以增量3，2，1为例
{
for(int L=0;L<(n-1)/incr;L++)//重复分成的每个子列表
{
for(int i=L+incr;i<n;i+=incr)//对每个子列表应用插入排序
{
int temp=arr[i];
int j=i-incr;
while(j>=0&&arr[j]>temp)
{
arr[j+incr]=arr[j];
j-=incr;
}
arr[j+incr]=temp;
}
}
}
}
--------------------------------------Code-------------------------------------------
适用于排序小列表。
效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。
壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。

五、归并排序
----------------------------------------------Code 从小到大排序---------------------------------------
void MergeSort(int low,int high)
{
if(low>=high) return;//每个子列表中剩下一个元素时停止
else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表*/
MergeSort(low,mid);//子列表进一步划分
MergeSort(mid+1,high);
int [] B=new int [high-low+1];//新建一个数组，用于存放归并的元素
for(int i=low,j=mid+1,k=low;i<=mid && j<=high;k++)/*两个子列表进行排序归并，直到两个子列表中的一个结束*/
{
if (arr[i]<=arr[j];)
{
B[k]=arr[i];
I++;
}
else
{ B[k]=arr[j]; j++; }
}
for( ;j<=high;j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表
B[k]=arr[j];
for( ;i<=mid;i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中
B[k]=arr[i];
for(int z=0;z<high-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中
arr[z]=B[z];
}
-----------------------------------------------------Code---------------------------------------------------
效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。
适用于排序大列表，基于分治法。

六、快速排序
------------------------------------Code--------------------------------------------
/*快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。*/ void swap(int a,int b){int t;t =a ;a =b ;b =t ;}
int Partition(int [] arr,int low,int high)
{
int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素
while (low < high)
{
//从后往前栽后半部分中寻找第一个小于枢纽元素的元素
while (low < high && arr[high] >= pivot)
{
--high;
}
//将这个比枢纽元素小的元素交换到前半部分
swap(arr[low], arr[high]);
//从前往后在前半部分中寻找第一个大于枢纽元素的元素
while (low <high &&arr [low ]<=pivot )
{
++low ;
}
swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分
}
return low ;//返回枢纽元素所在的位置
}
void QuickSort(int [] a,int low,int high)
{
if (low <high )
{
int n=Partition (a ,low ,high );
QuickSort (a ,low ,n );
QuickSort (a ,n +1,high );
}
}
----------------------------------------Code-------------------------------------
平均效率O（nlogn），适用于排序大列表。
此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n²）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。
基于分治法。

七、堆排序
最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。
思想：
(1)令i=l,并令temp＝ kl ;
(2)计算i的左孩子j=2i+1;
(3)若j<＝n－1，则转(4),否则转(6);
(4)比较kj和kj+1,若kj+1>kj,则令j＝j＋1，否则j不变；
(5)比较temp和kj，若kj>temp，则令ki等于kj，并令i=j,j=2i+1,并转(3),否则转(6)
(6)令ki等于temp，结束。
-----------------------------------------Code---------------------------
void HeapSort(SeqIAst R)

{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元 int I; BuildHeap(R)； //将R[1-n]建成初始堆for(i=n;i>1；i--) //对当前无序区R[1..i]进行堆排序，共做n-1趟。{ R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; //将堆顶和堆中最后一个记录交换 Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } } ---------------------------------------Code--------------------------------------

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)， 它是不稳定的排序方法。

堆排序与直接插入排序的区别:
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。

八、拓扑排序
例 ：学生选修课排课先后顺序
拓扑排序：把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。
方法：
在有向图中选一个没有前驱的顶点且输出
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。
---------------------------------------Code--------------------------------------
void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/
{
int indegree[M];
int i,k,j;
char n;
int count=0;
Stack thestack;
FindInDegree(G,indegree);//对各顶点求入度indegree[0....num]
InitStack(thestack);//初始化栈
for(i=0;i<G.num;i++)
Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]);
for(i=0;i<G.num;i++)
{
if(indegree[i]==0)
Push(thestack.vertices[i]);
}
Console.Write("拓扑排序输出顺序为：");
while(thestack.Peek()!=null)
{
Pop(thestack.Peek());
j=locatevex(G,n);
if (j==-2)
{
Console.WriteLine("发生错误，程序结束。");
exit();
}
Console.Write(G.vertices[j].data);
count++;
for(p=G.vertices[j].firstarc;p!=NULL;p=p.nextarc)
{
k=p.adjvex;
if (!(--indegree[k]))
Push(G.vertices[k]);
}
}
if (count<G.num)
Cosole.WriteLine("该图有环，出现错误，无法排序。");
else
Console.WriteLine("排序成功。");
}
----------------------------------------Code--------------------------------------
算法的时间复杂度O（n+e）。

2. 数据结构请教

B
前驱就是前面的意思了。p在Q前那么p->link==q,由于是指针，所以用->不用.
A
emptey返回的是true 或者false吧，也就是1和0了。
压入两个，弹出两个。
怎么说呢，你用的不是标准的方法，不知道你定义的返回是什么
标准的方法是这样的
bool empty() const
size_type size() const
void push(const value_type& x)
void pop()
explicit stack(const Container& = Container())
value_type& top()
const value_type& top() const
这个跟你定义的方法有关，按标准理解应该就是都弹出了
3
c
右指针非空就是说右边有一个兄弟节点了。通过广义表可以看出来b有兄弟c，d处于其右边。c有d在右边，e有f在右边。所以有三个
4 A，最短路径记录的也是顶点序列吧记得dijs……算法里面记录的就是这个顶点序列了。 不过无向无权图最短路径是边数。
5 B 广度优先搜索结果有两种了。
1234 1324 搜索可以从1到达的顶点的时候可以先让2进入队列，也可以先让3进入队列，如果2先进队列那么就是1234这个结果，如果先让3入队列就是1243了
6 C 可以取特例 如n=1时，有2个
n=2时有3个所以选C

3. 数据结构的排序算法中，哪些排序是稳定的，哪些排序是不稳定的

一、稳定排序算法

1、冒泡排序

2、鸡尾酒排序

3、插入排序

4、桶排序

5、计数排序

6、合并排序

7、基数排序

8、二叉排序树排序

二、不稳定排序算法

1、选择排序

2、希尔排序

3、组合排序

4、堆排序

5、平滑排序

6、快速排序

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

一个排序算法是稳定的，就是当有两个相等记录的关键字R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。

做这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

(3)算法中的横向排列扩展阅读：

排序算法的分类：

1、通过时间复杂度分类

计算的复杂度（最差、平均、和最好性能），依据列表(list)的大小(n)。

一般而言，好的性能是 O(nlogn)，且坏的性能是 O(n^2)。对于一个排序理想的性能是 O(n)。

而仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要 O(nlogn)。

2、通过空间复杂度分类

存储器使用量（空间复杂度）（以及其他电脑资源的使用）

3、通过稳定性分类

稳定的排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。

4. 排列组合的公式

排列组合计算公式如下：

1、从n个不同元素中取出m（m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A（n,m）表示。

排列就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。

(4)算法中的横向排列扩展阅读

排列组合的发展历程：

根据组合学研究与发展的现状，它可以分为如下五个分支：经典组合学、组合设计、组合序、图与超图和组合多面形与最优化。

由于组合学所涉及的范围触及到几乎所有数学分支，也许和数学本身一样不大可能建立一种统一的理论。

然而，如何在上述的五个分支的基础上建立一些统一的理论，或者从组合学中独立出来形成数学的一些新分支将是对21世纪数学家们提出的一个新的挑战。

5. 排序算法有多少种

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：
(1)冒泡排序；
(2)选择排序；
(3)插入排序；
(4)希尔排序；
(5)归并排序；
(6)快速排序；
(7)基数排序；
(8)堆排序；
(9)计数排序；
(10)桶排序。
插入排序
插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。插入排序分直接插入排序、折半插入排序和希尔排序3类。
冒泡排序
冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第(n一1)个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。
选择排序
选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法。首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置，再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。使用这种排序时，要注意其中一个不同于冒泡法的细节。举例说明：序列58539．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。
快速排序
快速排序的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，最终能够实现将所需排序的无序序列元素变为一个有序的序列。
归并排序
归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。

6. 请问雷达成像算法中的时域反转镜技术具体计算过程是怎样的谢谢~

雷达成像基于目标的散射点模型.雷达通常发射长时宽的线频调(chirp)信号，然后用参考信号对回波作解线频调(dechirp)处理，再将解线频调的回波作横向排列，则在一定条件下它可近似为二维正弦信号模型，通过二维傅里叶变换，可以重构目标的二维像；采用超分辨算法［1～3］，还可得到更精细的二维目标像.
应当指出，上述二维模型是假设散射点在成像期间不发生超越分辨单元走动，近似认为散射点的移动只影响回波的相移，而子回波包络则固定不变.这种近似，只适用于小观察角时参考点附近有限小尺寸目标成像.
如果目标较大，特别是在离参考点较远处，越分辨单元移动(MTRC)便会发生，从而使得用简单二维模型获得的图像模糊.传统解决的方法是按目标转动用极坐标-直角坐标插值.插值不可避免地会有误差，而超分辨算法通常基于参数化估计，对误差较为敏感，这会影响成像质量.
本文介绍一种近似度较高的二维模型，并利用该模型通过超分辨算法成像，可获得较好的结果.
二、维回波模型
设目标有K个散射点，雷达以平面波自下向上照射目标(图1).目标以参考点为原点相对雷达射线转动，经过N次脉冲发射，散射点Pk点移至P′k点，移动中第n次脉冲时该散射点的垂直坐标为：
ykn=yk+Δykn=xksin(nδθ)+ykcos(nδθ),n=0,1,…,N-1(1)
式中δθ为相邻脉冲的转角，总观测角Δθ=(N-1)δθ.考虑到雷达发射的是长时宽的线频调信号，以原点为参考作解线频调处理，并对信号以 的频率采样，得目标的回波信号(离散形式)为：
(2)
式中Ak为第k个散射点子回波信号的复振幅;fc、γ分别是雷达载频和调频率，c为光速；e(m,n)为加性噪声.

图1二维雷达目标几何图
由于观测角Δθ很小，取近似sin(nδθ)≈nδθ和cos(nδθ)≈1，则式(2)可近似写成:
(3)
式中
式(3)指数项中的第三项是时频耦合项，它是线频调信号(其模糊函数为斜椭圆)所特有的，如果采用窄脉冲发射，则该项不存在.将该项忽略，则式(3)成为常用的回波二维正弦信号模型.
实际上，式(3)的第三项系“距离移动”项，它与散射点的横坐标xk成正比，目标区域大时必须考虑，而且这还远远不够，散射点的多普勒移动也必须考虑.为此，令sin(nδθ)≈nδθ和cos(nδθ)≈1-(nδθ)2/2，则式(2)较精确的近似式可写成：
(4)
式(4)与式(3)相比较，指数中增加了两项，其中前一项是“多普勒移动”项，纵坐标yk越大，影响也越大，这可以补充式(3)之不足；而后项是时频耦合的多普勒移动项，由于Mγ/Fs<<fc，它的影响可以忽略.因此，可将考虑MTRC情况下，回波二维模型的一阶近似式写成：
(5)
需要指出，每个散射点的参数之间存在下述关系：ωk/μk=2γ/Fsfcδθ2和 k/vk=fcFs/γδθ.由于雷达参数(fc,γ,Fs)和运动参数(δθ)均已知，所以待估计的五个参数中只有三个是独立的.本文假设五个参数是独立的，而在成像计算中已考虑参数之间的关系.
设{ξk}Kk=1≡{αk,ωk, k,μk,vk}Kk=1，现在我们要从y(m,n)中估计参量{ξk}Kk=1.
三、二维推广的RELAX算法
对于(5)式所示的信号模型，令：
Y=［y(m,n)］M×N
则 (6)
式中

设ξk估计值为 ，则ξk的估计问题可通过优化下述代价函数解决：
(7)
式中‖.‖F表示矩阵的Frobenius范数，⊙表示矩阵的Hadamard积.
上式中C1的最优化是一个多维空间的寻优问题，十分复杂.本文将RELAX［3］算法推广以求解.为此，首先做以下准备工作，令：
(8)
即假定{ i}i=1,2,…,K,i≠k已经求出，则式(7)C1的极小化等效于下式的极小化：
C2(ξk)=‖Yk-αk(aM(ωk)bTN( k)Pk)⊙Dk(vk)‖2F(9)
令：Zk=YkP-1k⊙Dk(-vk)(10)
由于Pk为酉矩阵，矩阵Dk的每个元素的模|Dk(m,n)|=1,显然矩阵Yk与Zk的F范数相同，故C2的极小化等效于下式的极小化：
C3=‖Zk-αkaM(ωk)bTN( k)‖2F(11)
对上式关于αk求极小值就获得αk的估计值 k：
k=aHM(ωk)Zkb*N( k)/(MN)(12)
从式(12)可以看出： 是Zk归一化的二维离散傅里叶变换在{ωk, k}处的值，所以只要得到估计值{ k, k, k, k}，即可通过2D-FFT获得 k.
将估计值 k代入式(11)后，估计值{ k, k, k, k}可由下式寻优得到：
(13)
由上式可见，对于固定的{μk,vk}取值,估计值{ k, k}为归一化的周期图|aHM(ωk)Zkb*N( k)|2/(MN)主峰处的二维频率值.这样，式(13)的优化问题归结为：在(μk,vk)平面上可能的取值范围内寻找一点{ k, k}，在该点处周期图|aHM(ωk)Zkb*N( k)|2/(MN)的主峰值比其余各点处的主峰值都大.所以，我们通过上述二维寻优获得{μk,vk}的估计值{ k, k}，再由式(13)得到{ωk, k}的估计值{ k, k}.
实际中，为了加快运算速度，二维(μk,vk)平面的寻优可以用Matlab中的函数Fmin()实现.
在做了以上的准备工作以后，基于推广的RELAX算法的参量估计步骤如下：
第一步：假设信号数K=1,分别利用式(13)和式(12)计算 1.
第二步(2)：假设信号数K=2，首先将第一步计算所得到的 1代入式(8)求出Y2，再利用式(13)和式(12)计算 2；将计算的 2代入式(8)求出Y1，然后利用式(13)和式(12)重新计算 1，这个过程反复叠代，直至收敛.
第三步:假设信号数K=3,首先将第二步计算所得到的 1和 2代入式(8)求出Y3，再利用式(13)和式(12)计算 3；将计算的 3和 2代入式(8)求出Y1，然后利用式(13)和式(12)重新计算 1；将计算的 1和 3代入式(8)求出Y2，然后利用式(13)和式(12)重新计算 2，这个过程反复叠代，直至收敛.
剩余步骤：令K=K+1,上述步骤持续进行，直到K等于待估计信号数.
上述过程中的收敛判据与RELAX算法的收敛判据相同，即比较代价函数C1在两次叠代过程中的变化值，如果这个变换值小于某个值，如ε=10-3，则认为过程收敛.
四、数值模拟
1.算法参数估计性能模拟
模拟数据由式（5）产生，M=10,N=10，信号数K=2.信号参数和实验条件如表1所示,为复高斯白噪声.注意两信号的频率差小于FFT的分辨率Δf=Δω/(2π)=0.1.表1给出了信号参数估计均方根误差的统计结果及相应情形时的C-R界，可见，估计均方根误差与CR界十分接近.另外表中还给出了估计均值，与真实值也非常接近.
表1二维信号的参数估计、CRB及与均方根差的比较

2.SAR成像模拟
雷达参数为：中心频率f0=24.24GHz,调频率γ=33.357×1011Hz/s,带宽B=133.5MHz,脉冲宽度tp=40μs.四个点目标作正方形放置，间隔50米，左下角的点作为参考点.雷达与目标间隔1公里，观察角Δθ=3.15，数据长度为128×128.采用FFT成像方法时，其纵向和横向距离分辨率为ρr=ρa=1.123米，防止MTRC现象发生所需的目标最大范围为［4］：纵向尺寸Dr＜4ρ2r/λ=40米，横向尺寸Da＜4ρ2a/λ=40米.采用常规超分辨方法时，目标尺寸Dr=Da＞10米则出现明显的性能下降.图2、图3分别给出了RELAX方法及本文推广的RELAX(Extended RELAX)算法的成像结果.可以看出，由于目标远离参考中心，已在横向和纵向出现距离走动，采用常规超分辨的RELAX算法产生图像模糊，对于本文算法，则得到基本正确的成像结果.图4和图5则比较了RELAX算法和推广的RELAX算法的散射点强度估计结果，可以看到，RELAX算法由于距离走动影响，散射点（除参考点以外）的强度降低.对于本文算法，散射点强度接近真实值.

图2距离走动误差下的RELAX成像结果 图3距离走动误差下的

图4RELAX方法估计的信号强度推广RELAX成像结果 图5推广RELAX方法估计的信号强度
五、结束语
现有的雷达成像超分辨算法是基于目标回波信号的二维正弦信号模型，所以仅适用于目标位于参考点附近很小区域时的情形.当目标远离参考点时，模型误差，特别是距离走动误差，将使算法性能严重下降或失效.为此，本文提出一种基于雷达成像近似二维模型的超分辨算法,从而扩大了超分辨算法的适用范围.本文进一步的工作包括SAR实测数据成像及ISAR机动目标成像，结果将另文报道.
附 录：参数估计的C-R界
下面我们给出式(5)所示的二维信号参量估计的C-R界表达式.同时假设式(5)中加性噪声为零均值高斯色噪声，其协方差矩阵未知.令：
y=vec(Y)(A.1)
e=vec(E)(A.2)
dk=vec(Dk)(A.3)
式中vec(X)=(xT1,xT2，…，xTN)T，向量xn(n=1,2,…,N)为矩阵X的列向量.我们将式(5)改写为如下向量形式：
(A.4)
式中 表示Kronecker积,Ω=［{［P1bN( 1)］ aM(ω1)}⊙d1…{［PkbN( K)］ aM(ωK)}⊙dK］,α=(α1，α2，…，αK)T.
令Q=E(eeH)为e的协方差矩阵，则对于由式(A.4)所示的二维信号模型，其Fisher信息阵(FIM)的第ij个元素推广的Slepian-Bangs公式为［5,6］:
(FIM)ij=tr(Q-1Q′iQ-1Q′j)+2Re［(αHΩH)′iQ-1(Ωα)′j］(A.5)
式中X′i表示矩阵X对第i个参数求导，tr(X)为矩阵的迹，Re(X)为矩阵的实部.由于Q与Ωα中的参量无关，而Ωα亦与Q的元素无关，显然FIM为一块对角阵.所以待估计参量的C-R界矩阵由(A.5)式的第二项得到.
令：η=(［Re(α)］T［Im(α)］TωT TμTvT)T(A.6)
式中ω=(ω1，ω2，…，ωK)T,μ=(μ1,μ2,…,μK)T, =( 1， 2，…， K)T,v=(v1,v2,…,vK)T.
令：F=［ΩjΩDωΘD ΘDμΘDvΘ］(A.7)
式中矩阵Dω、D 、Dμ、Dv的第k列分别为： ［{［PkbN( k)］ aM(ωk)}⊙dk］/ ωk、 ［{［PkbN( k)］ aM(ωk)}⊙dk］/ k、 ［{［PkbN( k)］ aM(ωk)}⊙dk］/ μk、 ［{［PkbN( k)］ aM(ωk)}⊙dk］/ vk，Θ=diag{α1α2…αK}.则关于参量向量η的CRB矩阵为
CRB(η)=［2Re(FHQ-1F)］-1(A.8)

7. 常用的排序算法都有哪些

排序算法 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
分类
在计算机科学所使用的排序算法通常被分类为：
计算的复杂度（最差、平均、和最好表现），依据串行（list）的大小（n）。一般而言，好的表现是O。(n log n)，且坏的行为是Ω(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要Ω(n log n)。
记忆体使用量（以及其他电脑资源的使用）
稳定度：稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。
一般的方法：插入、交换、选择、合并等等。交换排序包含冒泡排序（bubble sort）和快速排序（quicksort）。选择排序包含shaker排序和堆排序（heapsort）。
当相等的元素是无法分辨的，比如像是整数，稳定度并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在这个状况下，有可能产生两种不同的结果，一个是依照相等的键值维持相对的次序，而另外一个则没有：
(3, 1) (3, 7) (4, 1) (5, 6) (维持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)
不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地时作为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个物件间之比较，就会被决定使用在原先资料次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。
排列算法列表
在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。
稳定的
冒泡排序（bubble sort） — O(n2)
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体
原地归并排序 — O(n2)
二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体
基数排序 （radix sort）— O(n·k); 需要 O(n) 额外记忆体
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 额外记忆体
不稳定
选择排序 （selection sort）— O(n2)
希尔排序 （shell sort）— O(n log n) 如果使用最佳的现在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情况时间, 需要 额外的 O(n + k) 空间, 也需要找到最长的递增子序列（longest increasing subsequence）
不实用的排序算法
Bogo排序 — O(n × n!) 期望时间, 无穷的最坏情况。
Stupid sort — O(n3); 递回版本需要 O(n2) 额外记忆体
Bead sort — O(n) or O(√n), 但需要特别的硬体
Pancake sorting — O(n), 但需要特别的硬体
排序的算法
排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。
插入排序
冒泡排序
选择排序
快速排序
堆排序
归并排序
基数排序
希尔排序
插入排序
插入排序是这样实现的：
首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。
从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。
重复2号步骤，直至原数列为空。
插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。
冒泡排序
冒泡排序是这样实现的：
首先将所有待排序的数字放入工作列表中。
从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
重复2号步骤，直至再也不能交换。
冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。
选择排序
选择排序是这样实现的：
设数组内存放了n个待排数字，数组下标从1开始，到n结束。
i=1
从数组的第i个元素开始到第n个元素，寻找最小的元素。
将上一步找到的最小元素和第i位元素交换。
如果i=n－1算法结束，否则回到第3步
选择排序的平均时间复杂度也是O(n²)的。
快速排序
现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。
堆排序
堆排序与前面的算法都不同，它是这样的：
首先新建一个空列表，作用与插入排序中的"有序列表"相同。
找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。
重复2号步骤，直至原数列为空。
堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。
看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。
平均时间复杂度
插入排序 O(n2)
冒泡排序 O(n2)
选择排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n1.25)
冒泡排序
654
比如说这个，我想让它从小到大排序，怎么做呢？
第一步：6跟5比，发现比它大，则交换。564
第二步：5跟4比，发现比它大，则交换。465
第三步：6跟5比，发现比它大，则交换。456