演算法分析與設計快速排序
1. C++:設計排序典型演算法（冒泡與快速排序）
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
vector<int> quick_sort( vector<int> a )
{
if ( a.size() == 0 || a.size() == 1 )
{
return a;
}
int k = a[ 0 ];
vector<int> pre, suc;
for ( int i = 1; i < a.size(); ++i )
{
if ( a[ i ] <= k )
{
pre.push_back( a[ i ] );
}
else
{
suc.push_back( a[ i ] );
}
}
pre = quick_sort( pre );
suc = quick_sort( suc );
a = pre;
a.push_back( k );
for ( i = 0; i < suc.size(); ++i )
{
a.push_back( suc[ i ] );
}
return a;
}
void main()
{
srand( time( 0 ) );
vector<int> a;
for ( int i = 0; i < 10; ++i )
{
a.push_back( rand() % 100 + 1 );
}
for ( i = 0; i < 10; ++i )
{
cout << a[ i ] << " ";
}
cout << endl;
a = quick_sort( a );
for ( i = 0; i < 10; ++i )
{
cout << a[ i ] << " ";
}
cout << endl;
return;
}
2. 誰能解釋一下用遞歸做的排列演算法的詳細步驟參考王曉東的《計算機演算法設計與分析》p11
用到遞歸的排序演算法有快速排序和歸並排序。
快速排序：先選最開始的元素為樞軸，然後分別從兩頭中的一頭開始與樞軸比較。後面的應該大於樞軸，前面的應該小於樞軸，不然則交換（前面與後面），最後確定下來的位置（前後重合）就是樞軸的位置。這樣一來原序列就一分為二。不斷遞歸，再一分為二，最後直到被分為的兩端中有一個元素單獨的時候就結束分割。
歸並排序:第一次兩個兩個的來，排序之後就歸並成一個有序列，然後再四個四個的來，排序之後歸並成一個有序列……直到最後兩個歸並為一個有序列。
3. c語言，快速排序演算法
0和N-1表示的是數組下標。快排每一趟排序的目的是使值比設定的key值小的數都排到數組前部分，大的都排到後部分；然後對這兩部分用新的關鍵值key分別重復上一步的操作；遞歸，直到數組有序。
其中關鍵值key=a[low]。
用題目給定的數組模擬第一趟排序如下：
下標0123456789
值91647824661232551
low=0high=9
part_element=a[low]=9
進入for循環
進入第一個while
part_element<51，於是high--,high=8;
part_element<25，high--,high=7;
part_element>3,不滿足，結束while
a[low]=a[0]=a[high]=a[7]=3,low++,low=1;
進入第二個while
part_element<16,不滿足，結束while
a[high]=a[7]=a[low]=a[1]=16,high--,high=6
for第一個循環結束，數組如下
316478246612162551
low=1,high=6
for第二個循環同上，結束時數組如下
344782476612162551
low=2,high=3
for第三個循環，第一個while中high--以後，low==high，直接break跳出for循環，此時
344782476612162551
low=2,high=2
結束for以後
a[high]=a[2]=part_element=9,得到
34982476612162551
split函數returnhigh=2
quicksort函數中middle=2;
下面兩句遞歸，仍然是調用split函數，對數組
0-2,3-9兩部分分別重復上述操作
最後直到數組數據有序
4. 演算法設計與分析的題目，求高手啊
如何選擇排序、矩陣相乘、樹和圖演算法的時間復雜性計量單位？
排序：排序的循環次數（或遞歸次數）。
矩陣相乘：做實數乘法的次數。
樹：搜索的次數。
圖：同樹。
演算法有幾種基本結構？各種結構的時間復雜度的計算規則？
3種
順序結構：T(n)=O(c)
選擇結構：T(n)=O(c)
循環結構：T(n)=O(n)
最壞情況下的時間復雜性和平均情況下的時間復雜性的定義？
在規模n的全部輸入中，可以找尋執行一個演算法所需的最大時間資源的量，這個量稱為對規模n的輸入，演算法的最壞情況時間復雜性。
對規模都為n的一些有限輸入集，執行演算法所需的平均時間資源的量稱為平均情況下的時間復雜性。
為什麼選擇時間復雜度的漸進性態評價演算法？
因為在規模較小的時候無法客觀體現一個演算法的效率。
解釋f(n)=O(g(n))的意義。
若f(n)和g(n)是定義在正整數集合上的 兩個函數，則f(n)=O(g(n))表示存在正的常數C和n0 ,使得當n≥n0時滿足0≤f(n)≤C*g(n)。
簡述之就是這兩個函數當整型自變數n趨向於無窮大時，兩者的比值是一個不等於0的常數。
有效演算法和無效演算法的劃分原則？
區分在於問題是否能夠精確求解。
用分治法設計演算法有什麼好處？為什麼描述分治演算法需要使用遞歸技術？
分治法可以將問題分為許規模更小的子問題，這些子問題相互獨立且與原問題相同。使用遞歸技術，雖然一些簡單的循環結構替代之，但是復雜的問題，比如二階遞歸是無法替代的。
歸並排序演算法和快速排序演算法劃分子問題和合並子問題的解的方法各是是怎樣的？
歸並排序演算法：
劃分子問題：每次分成2個大小大致相同的子集和
合並子問題：將2個排好序的子數組合並為一個數組
快速排序演算法：對輸入的子數組a[p:r]
劃分子問題：劃分為a[p:q-1],a[q]和a[q+1:r]使a[p:q-1]任意元素小於a[q]，a[q+1:r] 任意元素大於a[q]
合並子問題：不需要（因為劃分過程就已經排序完成了）
簡述二分檢索（折半查找）演算法為什麼比順序查找的效率高？
對於二分搜索 最壞情況為O(logn)時間完成
而順序查找 需要O(n)次比較
顯然二分搜索效率高
貪心法的核心是什麼？
貪心演算法是通過一系列選擇得到問題的解，它所作出的選擇都是當前狀態下的最佳選擇。
背包問題的目標函數是什麼？背包問題貪心演算法的最優量度是什麼？演算法是否獲得最優解？ 用貪心演算法解0/1背包問題是否可獲得最優解？
Max=∑Vi*Xi (V是價值X取1，0表示裝入或不裝)
每次選取單位重量價值最高的
不一定是最優解
情況不妙啊 LZ還要繼續否。。。
早知發郵件了。。。
5. 數據結構(c語言)中快速排序什麼時候排序最慢，什麼情況下使用快速排序
當待排序的序列已經有序（不管是升序還是降序），此時快速排序最慢，一般當數據量很大的時候，用快速排序比較好，為了避免原來的序列有序，一般採用改進的快速排序演算法，在排序之前隨機交換兩個元素的位置，就可以達到目的了，有一本書，叫《演算法設計、分析與實現：C、C++和java》徐子珊著。可以看看，裡面寫了很多基本的演算法
6. 演算法中關於冒泡排序和快速排序
最壞情況下快排將脫變為冒泡時間復雜度同為n^2比較次數為n(n-1)/2
比較次數很容易理解：就是說進行了多少次比較操作。
來看看時間復雜度，這是個軟體工程方面的概念。
時間復雜度
演算法分析
同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。
1、時間復雜度
（1）時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
（2）時間復雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。
按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n),線性階O(n),
線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...，
k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。
2、空間復雜度
與時間復雜度類似，空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。記作:
S(n)=O(f(n))
我們一般所討論的是除正常佔用內存開銷外的輔助存儲單元規模。