排序演算法復雜度

1. 排序演算法的時間復雜度計算

你這個問題是自己想出來的吧？
第一，你指的時間復雜度是大O表示法的復雜度，也就是一個上界，但不是上確界，所以就算你以一種方式中斷排序過程，時間復雜度還是O(N*logN)，假設排序過程還能執行的話。
第二，達到O(N*logN)的排序演算法，以快速排序為例，快速排序不知道你看過沒有，它不像選擇排序或者冒泡排序那樣，每一趟可以確定一直最大或者最小值，對於快速排序，每一趟排序後如果你刪掉最後一個元素將導致整個演算法失效。如果你要用這種刪除元素方法的話，只能採用冒泡排序或者選擇排序，時間復雜度是O(N^2)
所以，我猜想你是不是想做類似於在N個元素中尋找前K個最大者之類的事情（K=N-L）
如果是這樣的話，有復雜度是O(N*logK)的演算法，利用快速排序中的partition操作
經過partition後，pivot左邊的序列sa都大於pivot右邊的序列sb；
如果|sa|==K或者|sa|==K-1，則數組的前K個元素就是最大的前K個元素，演算法終止;
如果|sa|<K-1，則從sb中尋找前K-|sa|-1大的元素;
如果|sa|>K，則從sa中尋找前K大的元素。
一次partition(arr,begin,end)操作的復雜度為end-begin，也就是O(N)，最壞情況下一次partition操作只找到第1大的那個元素，則需要進行K次partition操作，總的復雜度為O(N*K)。平均情況下每次partition都把序列均分兩半，需要logK次partition操作，總的復雜度為O(N*logK)。
由於K的上界是N，所以以N表示的總復雜度還是O(N*logN)

2. 所有排序演算法的時間復雜度

冒泡排序是這樣實現的：

首先將所有待排序的數字放入工作列表中。

從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。

重復2號步驟，直至再也不能交換。

冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。

選擇排序

選擇排序是這樣實現的：

設數組內存放了n個待排數字，數組下標從1開始，到n結束。

i=1

從數組的第i個元素開始到第n個元素，尋找最小的元素。

將上一步找到的最小元素和第i位元素交換。

如果i=n－1演算法結束，否則回到第3步

選擇排序的平均時間復雜度也是O(n^2)的。

3. 八大排序時間復雜度

怕時間的復雜程度非常高，因為他們那個序列多，而且那個排列復雜。

4. 排序演算法有幾種 時間復雜度

排序以及關系

5. 什麼排序的速度（時間復雜度）最快

從時間復雜度看，所有內部排序方法可以分為兩類。

1.插入排序 選擇排序 起泡排序
其時間復雜度為O(n2)；

2.堆排序 快速排序 歸並排序
其時間復雜度為O(nlog2n)。

這是就平均情況而言的，如果從最好的情況考慮，
則插入排序和起泡排序的時間復雜度最好，為O(n)，
而其他演算法的最好情況同平均情況大致相同。

如果從最壞的情況考慮，快速排序的時間復雜度為O(n2)，插入排序和起泡排序雖然同平均情況相同，但系數大約增加一倍，運行速度降低一半，而選擇排序、堆排序和歸並排序則影響不大。

總之，
在平均情況下，快速排序最快；
在最好情況下，插入排序和起泡排序最快；
在最壞情況下，堆排序和歸並排序最快。

6. 冒泡排序法的演算法復雜度！！急急急！！

選擇C。

雙層循環，內層都是n個，所以復雜度是n方。冒泡排序就是把小的元素往前調或者把大的元素往後調，比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。

所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。

(6)排序演算法復雜度擴展閱讀：

演算法原理：

1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

3、針對所有的元素重復以上的步驟，除了最後一個。

4、持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

7. 八大排序 時間復雜度

直接插入排序：

最好：待排序已經有序， 從前往後走都不用往裡面 插入。 時間復雜度為o(n)

最壞：待排序列是逆序，每一次都要移位插入。 時間復雜度o(n^2)

是穩定排序
2：希爾排序：

最好：縮小增量的插入排序，待排序已經有序。時間復雜度o(n）

一般：平均時間復雜度o(n1.3)，最差也是時間復雜度o(n1.3)

不穩定排序
3：冒泡排序：

最好：待排序已經有序。時間復雜度o(n）

最壞：待排序是逆序。時間復雜度o(n^2）

穩定排序
4：快速排序：

最好：待排序無序。時間復雜度o(nlogn)

最壞: 待排序已經有序，基準定義在開始。 時間復雜度為o(n^2)

不穩定排序
5：直接選擇排序：

無論好壞:o(n^2)

穩定排序
6：堆排序：

無論好壞：時間復雜度o(nlogn)

不穩定排序
7：歸並排序：
穩定排序
8：基數排序：

無論好壞:o(d(n+r)) ，r為基數，d為位數.

穩定排序

8. 在排序演算法中，哪個排序演算法的時間復雜度最差為什麼

這個不一定,要看數據內容.如果是特殊數據會導致一些演算法退化.綜合來看應該是基數最快,選擇最慢吧(你說的選擇是冒泡排序吧)

9. 排序演算法的復雜度

由於程序比較簡單，所以沒有加什麼注釋。所有的程序都給出了完整的運行代碼，並在我的VC環境
下運行通過。因為沒有涉及MFC和WINDOWS的內容，所以在BORLAND C++的平台上應該也不會有什麼
問題的。在代碼的後面給出了運行過程示意，希望對理解有幫助。 這是最原始，也是眾所周知的最慢的演算法了。他的名字的由來因為它的工作看來象是冒泡： #include<iostream>usingnamespacestd;voidBubbleSort(int*pData,intCount){intiTemp;for(inti=0;i<Count;i++){for(intj=Count-1;j>i;j--){if(pData[j]<pData[j-1]){iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[7]={10,9,8,7,6,5,4};BubbleSort(data,7）;for(inti=0;i<7;i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}倒序（最糟情況)
第一輪：10，9，8，7->10，9，7，8->10，7，9，8->7，10，9，8（交換3次)
第二輪：7，10，9，8->7，10，8，9->7，8，10，9（交換2次)
第一輪：7，8，10，9->7，8，9，10（交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8，10，7，9->8，10，7，9->8，7，10，9->7，8，10，9（交換2次)
第二輪：7，8，10，9->7，8，9，10->7，8，10，9（交換1次)
（這是原撰寫人的--7，8，10，9->7，8，10，9->7，8，10，9（交換0次)，第二輪應該是這樣的）
第三輪：7，8，9，10->7，8，9，10（交換1次)
循環次數：6次
交換次數：3次
上面我們給出了程序段，現在我們分析它：這里，影響我們演算法性能的主要部分是循環和交換，
顯然，次數越多，性能就越差。從上面的程序我們可以看出循環的次數是固定的，為1+2+...+n-1。
寫成公式就是1/2*(n-1）*n。
現在注意，我們給出O方法的定義：
若存在一常量K和起點n0，使當n>=n0時，有f(n)<=K*g(n)，則f(n) = O(g(n))。（呵呵，不要說沒學好數學呀，對於編程數學是非常重要的！！！）
現在我們來看1/2*(n-1）*n，當K=1/2，n0=1，g(n)=n*n時，1/2*(n-1）*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我們程序循環的復雜度為O(n*n)。
再看交換。從程序後面所跟的表可以看到，兩種情況的循環相同，交換不同。其實交換本身同數據源的
有序程度有極大的關系，當數據處於倒序的情況時，交換次數同循環一樣（每次循環判斷都會交換），
復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(0)。亂序時處於中間狀態。正是由於這樣的
原因，我們通常都是通過循環次數來對比演算法。 交換法的程序最清晰簡單，每次用當前的元素一一的同其後的元素比較並交換。 #include<iostream.h>voidExchangeSort(int*pData，intCount){intiTemp;for(inti=0;i<Count-1;i++){//共（count-1）輪，每輪得到一個最小值for(intj=i+1;j<Count;j++){//每次從剩下的數字中尋找最小值，於當前最小值相比，如果小則交換if(pData[j]<pData[i]){iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;}}}}voidmain(){intdata[]={10,9,8,7,6,5,4};ExchangeSort(data,sizeof(data)/sizeof(int));for(inti=0;i<sizeof(data)/sizeof(int);i++){cout<<data[i]<<;}cout<<endl;system(PAUSE);}第一輪： 9，10，8，7->8，10，9，7->7，10，9，8（交換3次)
第二輪：7，10，9，8->7，9，10，8->7，8，10，9（交換2次)
第一輪：7，8，10，9->7，8，9，10（交換1次)
循環次數：6次
交換次數：6次
其他：
第一輪：8，10，7，9->8，10，7，9->7，10，8，9->7，10，8，9（交換1次)
第二輪：7，10，8，9->7，8，10，9->7，8，10，9（交換1次)
第一輪：7，8，10，9->7，8，9，10（交換1次)
循環次數：6次
交換次數：3次
從運行的表格來看，交換幾乎和冒泡一樣糟。事實確實如此。循環次數和冒泡一樣
也是1/2*(n-1）*n，所以演算法的復雜度仍然是O(n*n)。由於我們無法給出所有的情況，所以
只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。 現在我們終於可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下）
這種方法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從剩下的部分中
選擇最小的與第二個交換，這樣往復下去。 #include<iostream.h>voidSelectSort(int*pData，intCount){intiTemp;intiPos;for(inti=0;i<Count-1;i++){iTemp=pData[i];iPos=i;for(intj=i+1;j<Count;j++){if(pData[j]<iTemp){iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp;}}voidmain(){intdata[]={10，9，8，7，6，5，4};SelectSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;cout<< ;}倒序（最糟情況)
第一輪：10，9，8，7->(iTemp=9）10，9，8，7->(iTemp=8）10，9，8，7->(iTemp=7）7，9，8，10（交換1次)
第二輪：7，9，8，10->7，9，8，10(iTemp=8）->(iTemp=8）7，8，9，10（交換1次)
第一輪：7，8，9，10->(iTemp=9）7，8，9，10（交換0次)
循環次數：6次
交換次數：2次
其他：
第一輪：8，10，7，9->(iTemp=8）8，10，7，9->(iTemp=7）8，10，7，9->(iTemp=7）7，10，8，9（交換1次)
第二輪：7，10，8，9->(iTemp=8）7，10，8，9->(iTemp=8）7，8，10，9（交換1次)
第一輪：7，8，10，9->(iTemp=9）7，8，9，10（交換1次)
循環次數：6次
交換次數：3次
遺憾的是演算法需要的循環次數依然是1/2*(n-1）*n。所以演算法復雜度為O(n*n)。
我們來看他的交換。由於每次外層循環只產生一次交換（只有一個最小值）。所以f(n)<=n
所以我們有f(n)=O(n)。所以，在數據較亂的時候，可以減少一定的交換次數。 插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然後繼續下一張 #include<iostream.h>voidInsertSort(int*pData，intCount){intiTemp;intiPos;for(inti=1;i<Count;i++){iTemp=pData[i];//保存要插入的數iPos=i-1;//被插入的數組數字個數while((iPos>=0)&&(iTemp<pData[iPos])){//從最後一個（最大數字）開始對比，大於它的數字往後移位pData[iPos+1]=pData[iPos];iPos--;}pData[iPos+1]=iTemp;//插入數字的位置}}voidmain(){intdata[]={10，9，8，7，6，5，4};InsertSort(data，7);for(inti=0;i<7;i++)cout<<data<<;cout<< ;}其他：
第一輪：8，10，7，9->8，10，7，9(交換0次)(循環1次)
第二輪：9，10，8，7->8，9，10，7（交換1次)（循環2次)
第一輪：8，9，10，7->7，8，9，10（交換1次)（循環3次)
循環次數：6次
交換次數：3次
其他：
第一輪：8，10，7，9->8，10，7，9（交換0次)（循環1次)
第二輪：8，10，7，9->7，8，10，9（交換1次)（循環2次)
第一輪：7，8，10，9->7，8，9，10（交換1次)（循環1次)
循環次數：4次
交換次數：2次
上面結尾的行為分析事實上造成了一種假象，讓我們認為這種演算法是簡單演算法中最好的，其實不是，
因為其循環次數雖然並不固定，我們仍可以使用O方法。從上面的結果可以看出，循環的次數f(n)<=
1/2*n*(n-1）<=1/2*n*n。所以其復雜度仍為O(n*n)（這里說明一下，其實如果不是為了展示這些簡單
排序的不同，交換次數仍然可以這樣推導）。現在看交換，從外觀上看，交換次數是O(n)（推導類似
選擇法），但我們每次要進行與內層循環相同次數的『=』操作。正常的一次交換我們需要三次『=』
而這里顯然多了一些，所以我們浪費了時間。
最終，我個人認為，在簡單排序演算法中，選擇法是最好的。 高級排序演算法中我們將只介紹這一種，同時也是目前我所知道（我看過的資料中）的最快的。
它的工作看起來仍然象一個二叉樹。首先我們選擇一個中間值middle程序中我們使用數組中間值，然後
把比它小的放在左邊，大的放在右邊（具體的實現是從兩邊找，找到一對後交換）。然後對兩邊分別使
用這個過程（最容易的方法——遞歸）。
1.快速排序：//這段代碼編譯可以通過，一運行就出錯，內部的細節有些問題，我還沒找到解決方法。 #include<iostream.h>voidrun(int*pData，intleft，intright){inti，j;intmiddle，iTemp;i=left;j=right;middle=pData[left];do{while((pData[i]<middle)&&(i<right))//從左掃描大於中值的數i++；while((pData[j]>middle)&&(j>left))//從右掃描大於中值的數j--;if(i<=j)//找到了一對值{//交換iTemp=pData[i];pData[i]=pData[j];pData[j]=iTemp;i++;j--;}}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）//當左邊部分有值（left<j)，遞歸左半邊if(left<j)run(pData，left，j);//當右邊部分有值（right>i)，遞歸右半邊if(right>i)run(pData，i，right);}voidQuickSort(int*pData，intCount){run(pData，0，Count-1）;}voidmain(){intdata[]={10，9，8，7，6，5，4};QuickSort(data，7）;for(inti=0;i<7;i++)cout<<data[i]<<;//原作者此處代碼有誤，輸出因為date[i],date數組名輸出的是地址cout<< ;}這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析演算法：首先我們考慮最理想的情況
1.數組的大小是2的冪，這樣分下去始終可以被2整除。假設為2的k次方，即k=log2(n)。
2.每次我們選擇的值剛好是中間值，這樣，數組才可以被等分。
第一層遞歸，循環n次，第二層循環2*(n/2）......
所以共有n+2(n/2）+4(n/4）+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以演算法復雜度為O(log2(n)*n)
其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那麼他將變
成交換法（由於使用了遞歸，情況更糟）。但是你認為這種情況發生的幾率有多大？？呵呵，你完全
不必擔心這個問題。實踐證明，大多數的情況，快速排序總是最好的。
如果你擔心這個問題，你可以使用堆排序，這是一種不穩定的O(log2(n)*n)演算法，但是通常情況下速度要慢
於快速排序（因為要重組堆）。 雙向冒泡
通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。 #include<iostream.h>inlinevoidexchange(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}voidbubblesort(int*array,intnum){inti,j,k,flag=0;for(i=0;i<num;i++){printf(%d,array[i]);}printf( );for(i=0;i<num;i++){//所有數的個數為num個flag=0;for(j=i;j<num-i-1;j++){//每循環一次最底端的數的順序都會排好，所以初始時j=i;if(array[j]>array[j+1]){exchange(&array[j],&array[j+1]);flag=1;}}for(k=num-1-i-1;k>i;k--){//每循環一次最頂端的數據的順序也會排好，所以初始時k=num-i-2if(array[k]<array[k-1]){exchange(&array[k],&array[k-1]);flag=1;}}if(flag==0){//如果flag未發生改變則說明未發生數據交換，則排序完成return;}}}voidmain(){intdata[]={10，9，8，7，6，5，4，3，2，1，-10，-1};bubblesort(data，12）;for(inti=0;i<12;i++)cout<<data<<;cout<< ;} 這個程序我想就沒有分析的必要了，大家看一下就可以了。不明白可以在論壇上問。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index，char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//這里重載了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index，char* strData):
m_iIndex(Index)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember，SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include MyData.h
template <class T>
void run(T* pData，int left，int right)
{
int i，j;
T middle，iTemp;
i = left;
j = right;
//下面的比較都調用我們重載的操作符函數
middle = pData[(left+right)/2]; //求中間值
do{
while((pData<middle) && (i<right))//從左掃描大於中值的數
i++；
while((pData[j]>middle) && (j>left))//從右掃描大於中值的數
j--;
if(i<=j)//找到了一對值
{
//交換
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果兩邊掃描的下標交錯，就停止（完成一次）
//當左邊部分有值（left<j)，遞歸左半邊
if(left<j)
run(pData，left，j);
//當右邊部分有值（right>i)，遞歸右半邊
if(right>i)
run(pData，i，right);
}
template <class T>
void QuickSort(T* pData，int Count)
{
run(pData，0，Count-1）;
}
void main()
{
CMyData data[] = {
CMyData（8，xulion)，
CMyData（7，sanzoo)，
CMyData（6，wangjun)，
CMyData（5，VCKBASE)，
CMyData（4，jacky2000)，
CMyData（3，cwally)，
CMyData（2，VCUSER)，
CMyData（1，isdong)
};
QuickSort(data，8）;
for (int i=0;i<8;i++)
cout<<data.m_iIndex<< <<data.GetData()<< ;
cout<< ;

10. 幾種常用的排序演算法以及其時間復雜度

資料來源：https://zh.wikipedia.org/wiki/排序演算法