排序演算法復雜度

㈠ 排序演算法的時間復雜度

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序演算法，就是如何使得記錄按照要求排列的方法。排序演算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。

一個優秀的演算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規范，要得到一個符合實際的優秀演算法，得經過大量的推理和分析。

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 。

而一般的遞歸演算法就要有O(n)的空間復雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要佔用的存儲空間兩個方面衡量。

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

排序演算法經過了很長時間的演變，產生了很多種不同的方法。對於初學者來說，對它們進行整理便於理解記憶顯得很重要。每種演算法都有它特定的使用場合，很難通用。因此，我們很有必要對所有常見的排序演算法進行歸納。

排序大的分類可以分為兩種：內排序和外排序。在排序過程中，全部記錄存放在內存，則稱為內排序，如果排序過程中需要使用外存，則稱為外排序。下面講的排序都是屬於內排序。

內排序有可以分為以下幾類：

(1)、插入排序：直接插入排序、二分法插入排序、希爾排序。

(2)、選擇排序：直接選擇排序、堆排序。

(3)、交換排序：冒泡排序、快速排序。

(4)、歸並排序

(5)、基數排序

㈡ 快速排序演算法復雜度

快速排序演算法的平均時間復雜度為O(nlogn)

㈢ 八大排序 時間復雜度

直接插入排序：

最好：待排序已經有序， 從前往後走都不用往裡面 插入。 時間復雜度為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為位數.

穩定排序

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

排序以及關系

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

冒泡排序是這樣實現的：

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

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

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

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

選擇排序

選擇排序是這樣實現的：

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

i=1

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

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

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

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

㈥ 冒泡排序演算法的時間復雜度是什麼

初始狀態是正序的，一趟掃描即可完成排序，所需的關鍵字比較次數和記錄移動次數均達到最小值：

冒泡排序就是把小的元素往前調或者把大的元素往後調，比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。

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

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

冒泡排序演算法的原理如下：

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

2、對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。

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

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

㈦ 八大排序時間復雜度

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

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

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

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

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

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

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

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

㈨ 排序演算法的復雜度

由於程序比較簡單，所以沒有加什麼注釋。所有的程序都給出了完整的運行代碼，並在我的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<< ;