演算法中的橫向排列

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