考慮這樣一個排序演算法對於待排序_排序演算法如何實現 C++

Ⅰ 排序演算法如何實現 C++

一、簡單排序演算法
由於程序比較簡單，所以沒有加什麼注釋。所有的程序都給出了完整的運行代碼，並在我的VC環境
下運行通過。因為沒有涉及MFC和WINDOWS的內容，所以在BORLAND C++的平台上應該也不會有什麼
問題的。在代碼的後面給出了運行過程示意，希望對理解有幫助。
1.冒泡法：
這是最原始，也是眾所周知的最慢的演算法了。他的名字的由來因為它的工作看來象是冒泡：
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情況)
第一輪：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,10,9->7,8,10,9(交換0次)
第一輪：7,8,10,9->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)。亂序時處於中間狀態。正是由於這樣的原因，我們通常都是通過循環次數來對比演算法。
2.交換法：
交換法的程序最清晰簡單，每次用當前的元素一一的同其後的元素比較並交換。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：10,9,8,7->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)。由於我們無法給出所有的情況，所以只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。

3.選擇法：
現在我們終於可以看到一點希望：選擇法，這種方法提高了一點性能（某些情況下）這種方法類似我們人為的排序習慣：從數據中選擇最小的同第一個值交換，在從省下的部分中選擇最小的與第二個交換，這樣往復下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情況)
第一輪：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)。所以，在數據較亂的時候，可以減少一定的交換次數。

4.插入法：
插入法較為復雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應的位置插入，然後繼續下一張
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=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;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情況)
第一輪：10,9,8,7->9,10,8,7(交換1次)(循環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>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中間值
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);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
這里我沒有給出行為的分析，因為這個很簡單，我們直接來分析演算法：首先我們考慮最理想的情況
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)演算法，但是通常情況下速度要慢於快速排序（因為要重組堆）。

三、其他排序
1.雙向冒泡：
通常的冒泡是單向的，而這里是雙向的，也就是說還要進行反向的工作。代碼看起來復雜，仔細理一下就明白了，是一個來回震盪的方式。寫這段代碼的作者認為這樣可以在冒泡的基礎上減少一些交換（我不這么認為，也許我錯了）。反正我認為這是一段有趣的代碼，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do {
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

2.SHELL排序
這個排序非常復雜，看了程序就知道了。首先需要一個遞減的步長，這里我們使用的是9、5、3、1（最後的步長必須是1）。工作原理是首先對相隔9-1個元素的所有內容排序，然後再使用同樣的方法對相隔5-1個元素的排序，以次類推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int i,Temp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step個元素的下標
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起來有些頭疼。不過也不是很難，把s==0的塊去掉就輕松多了，這里是避免使用0 步長造成程序異常而寫的代碼。這個代碼我認為很值得一看。這個演算法的得名是因為其發明者的名字D.L.SHELL。依照參考資料上的說法：「由於復雜的數學原因避免使用2的冪次步長，它能降低演算法效率。」另外演算法的復雜度為n的1.2次冪。同樣因為非常復雜並「超出本書討論范圍」的原因（我也不知道過程），我們只有結果了

Ⅱ 排序演算法概述

十大排序演算法：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序、希爾排序、計數排序，基數排序，桶排序

穩定：如果a原本在b前面，而a=b，排序之後a仍然在b的前面；
不穩定 ：如果a原本在b的前面，而a=b，排序之後a可能會出現在b的後面；
排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，前一個鍵排序的結果可以為後一個鍵排序所用。

演算法的復雜度往往取決於數據的規模大小和數據本身分布性質。
時間復雜度 ：一個演算法執行所耗費的時間。
空間復雜度 ：對一個演算法在運行過程中臨時佔用存儲空間大小的量度。
常見復雜度由小到大 ：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

在各種不同演算法中，若演算法中語句執行次數(佔用空間)為一個常數，則復雜度為O(1)；
當一個演算法的復雜度與以2為底的n的對數成正比時，可表示為O(log n)；
當一個演算法的復雜度與n成線性比例關系時，可表示為O (n)，依次類推。

冒泡、選擇、插入排序需要兩個for循環，每次只關注一個元素，平均時間復雜度為
（一遍找元素O(n)，一遍找位置O(n)）
快速、歸並、堆基於分治思想，log以2為底，平均時間復雜度往往和O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）相關
而希爾排序依賴於所取增量序列的性質，但是到目前為止還沒有一個最好的增量序列。例如希爾增量序列時間復雜度為O(n²)，而Hibbard增量序列的希爾排序的時間復雜度為，有人在大量的實驗後得出結論;當n在某個特定的范圍後希爾排序的最小時間復雜度大約為n^1.3。

從平均時間來看，快速排序是效率最高的：
快速排序中平均時間復雜度O(nlog n)，這個公式中隱含的常數因子很小，比歸並排序的O(nlog n)中的要小很多，所以大多數情況下，快速排序總是優於合並排序的。

而堆排序的平均時間復雜度也是O(nlog n)，但是堆排序存在著重建堆的過程，它把根節點移除後，把最後的葉子結點拿上來後需要重建堆，但是，拿上的值是要比它的兩個葉子結點要差很多的，一般要比較很多次，才能回到合適的位置。堆排序就會有很多的時間耗在堆調整上。

雖然快速排序的最壞情況為排序規模（n）的平方關系，但是這種最壞情況取決於每次選擇的基準，對於這種情況，已經提出了很多優化的方法，比如三取樣劃分和Dual-Pivot快排。
同時，當排序規模較小時，劃分的平衡性容易被打破，而且頻繁的方法調用超過了O(nlog n)為
省出的時間，所以一般排序規模較小時，會改用插入排序或者其他排序演算法。

一種簡單的排序演算法。它反復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。這個工作重復地進行直到沒有元素再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為元素會經由交換慢慢「浮」到數列的頂端。
1.從數組頭開始，比較相鄰的元素。如果第一個比第二個大(小)，就交換它們兩個；
2.對每一對相鄰元素作同樣的工作，從開始第一對到尾部的最後一對，這樣在最後的元素應該會是最大(小)的數；
3.重復步驟1~2，重復次數等於數組的長度，直到排序完成。

首先，找到數組中最大（小）的那個元素；
其次，將它和數組的第一個元素交換位置（如果第一個元素就是最大（小）元素那麼它就和自己交換）；
再次，在剩下的元素中找到最大（小）的元素，將它與數組的第二個元素交換位置。如此往復，直到將整個數組排序。
這種方法叫做選擇排序，因為它在不斷地選擇剩餘元素之中的最大（小）者。

對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。
為了給要插入的元素騰出空間，我們需要將插入位置之後的已排序元素在都向後移動一位。
插入排序所需的時間取決於輸入中元素的初始順序。例如，對一個很大且其中的元素已經有序（或接近有序）的數組進行排序將會比對隨機順序的數組或是逆序數組進行排序要快得多。
總的來說，插入排序對於部分有序的數組十分高效，也很適合小規模數組。

一種基於插入排序的快速的排序演算法。簡單插入排序對於大規模亂序數組很慢，因為元素只能一點一點地從數組的一端移動到另一端。例如，如果主鍵最小的元素正好在數組的盡頭，要將它挪到正確的位置就需要N-1 次移動。
希爾排序為了加快速度簡單地改進了插入排序，也稱為縮小增量排序，同時該演算法是突破O(n^2）的第一批演算法之一。
希爾排序是把待排序數組按一定數量的分組，對每組使用直接插入排序演算法排序；然後縮小數量繼續分組排序，隨著數量逐漸減少，每組包含的元素越來越多，當數量減至 1 時，整個數組恰被分成一組，排序便完成了。這個不斷縮小的數量，就構成了一個增量序列。

在先前較大的增量下每個子序列的規模都不大,用直接插入排序效率都較高，盡管在隨後的增量遞減分組中子序列越來越大,由於整個序列的有序性也越來越明顯,則排序效率依然較高。
從理論上說，只要一個數組是遞減的，並且最後一個值是1，都可以作為增量序列使用。有沒有一個步長序列,使得排序過程中所需的比較和移動次數相對較少,並且無論待排序列記錄數有多少,演算法的時間復雜度都能漸近最佳呢？但是目前從數學上來說，無法證明某個序列是「最好的」。
常用的增量序列
希爾增量序列：{N/2, (N / 2)/2, ..., 1}，其中N為原始數組的長度，這是最常用的序列，但卻不是最好的
Hibbard序列：{2^k-1, ..., 3,1}
Sedgewick序列：{... , 109 , 41 , 19 , 5，1} 表達式為

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法的一個非常典型的應用。
對於給定的一組數據，利用遞歸與分治技術將數據序列劃分成為越來越小的半子表，在對半子表排序後，再用遞歸方法將排好序的半子表合並成為越來越大的有序序列。
為了提升性能，有時我們在半子表的個數小於某個數（比如15）的情況下，對半子表的排序採用其他排序演算法，比如插入排序。
若將兩個有序表合並成一個有序表，稱為2-路歸並，與之對應的還有多路歸並。

快速排序（Quicksort）是對冒泡排序的一種改進，也是採用分治法的一個典型的應用。
首先任意選取一個數據（比如數組的第一個數）作為關鍵數據，我們稱為基準數(Pivot)，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序，也稱為分區（partition）操作。
通過一趟快速排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數組變成有序序列。
為了提升性能，有時我們在分割後獨立的兩部分的個數小於某個數（比如15）的情況下，會採用其他排序演算法，比如插入排序。

基準的選取：最優的情況是基準值剛好取在無序區數值的中位數，這樣能夠最大效率地讓兩邊排序，同時最大地減少遞歸劃分的次數，但是一般很難做到最優。基準的選取一般有三種方式，選取數組的第一個元素，選取數組的最後一個元素，以及選取第一個、最後一個以及中間的元素的中位數（如4 5 6 7, 第一個4, 最後一個7, 中間的為5, 這三個數的中位數為5, 所以選擇5作為基準）。
Dual-Pivot快排：雙基準快速排序演算法，其實就是用兩個基準數, 把整個數組分成三份來進行快速排序，在這種新的演算法下面，比經典快排從實驗來看節省了10%的時間。

許多應用程序都需要處理有序的元素，但不一定要求他們全部有序，或者不一定要一次就將他們排序，很多時候，我們每次只需要操作數據中的最大元素（最小元素），那麼有一種基於二叉堆的數據結構可以提供支持。
所謂二叉堆，是一個完全二叉樹的結構，同時滿足堆的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。在一個二叉堆中，根節點總是最大（或者最小）節點。
堆排序演算法就是抓住了這一特點，每次都取堆頂的元素，然後將剩餘的元素重新調整為最大（最小）堆，依次類推，最終得到排序的序列。

推論1：對於位置為K的結點左子結點=2 k+1 右子結點=2 (k+1)
驗證：C:2 2 2+1=5 2 (2+1)=6
推論2：最後一個非葉節點的位置為 (N/2)-1，N為數組長度。
驗證：數組長度為6，(6/2)-1=2

計數排序對一定范圍內的整數排序時候的速度非常快，一般快於其他排序演算法。但計數排序局限性比較大，只限於對整數進行排序，而且待排序元素值分布較連續、跨度小的情況。
計數排序是一個排序時不比較元素大小的排序演算法。
如果一個數組里所有元素都是整數，而且都在0-K以內。對於數組里每個元素來說，如果能知道數組里有多少項小於或等於該元素，就能准確地給出該元素在排序後的數組的位置。

桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，利用某種函數的映射關系將數據分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序）。
桶排序利用函數的映射關系，減少了幾乎所有的比較工作。實際上，桶排序的f(k)值的計算，其作用就相當於快排中劃分，已經把大量數據分割成了基本有序的數據塊(桶)。然後只需要對桶中的少量數據做排序即可。

常見的數據元素一般是由若干位組成的，比如字元串由若干字元組成，整數由若干位0~9數字組成。基數排序按照從右往左的順序，依次將每一位都當做一次關鍵字，然後按照該關鍵字對數組排序，同時每一輪排序都基於上輪排序後的結果；當我們將所有的位排序後，整個數組就達到有序狀態。基數排序不是基於比較的演算法。
基數是什麼意思？對於十進制整數，每一位都只可能是0~9中的某一個，總共10種可能。那10就是它的基，同理二進制數字的基為2；對於字元串，如果它使用的是8位的擴展ASCII字元集，那麼它的基就是256。

基數排序 vs 計數排序 vs 桶排序

基數排序有兩種方法：
MSD 從高位開始進行排序
LSD 從低位開始進行排序
這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶
計數排序：每個桶只存儲單一鍵值
桶排序：每個桶存儲一定范圍的數值

有時，待排序的文件很大，計算機內存不能容納整個文件，這時候對文件就不能使用內部排序了（我們一般的排序都是在內存中做的，所以稱之為內部排序，而外部排序是指待排序的內容不能在內存中一下子完成，它需要做內外存的內容交換），外部排序常採用的排序方法也是歸並排序，這種歸並方法由兩個不同的階段組成：
採用適當的內部排序方法對輸入文件的每個片段進行排序，將排好序的片段（成為歸並段）寫到外部存儲器中（通常由一個可用的磁碟作為臨時緩沖區），這樣臨時緩沖區中的每個歸並段的內容是有序的。
利用歸並演算法，歸並第一階段生成的歸並段，直到只剩下一個歸並段為止。

例如要對外存中4500個記錄進行歸並，而內存大小隻能容納750個記錄，在第一階段，我們可以每次讀取750個記錄進行排序，這樣可以分六次讀取，進行排序，可以得到六個有序的歸並段
每個歸並段的大小是750個記錄，並將這些歸並段全部寫到臨時緩沖區（由一個可用的磁碟充當）內了，這是第一步的排序結果。
完成第二步該怎麼做呢？這時候歸並演算法就有用處了。

Ⅲ 排序演算法（九）：桶排序

桶排序是將待排序集合中處於同一個值域的元素存入同一個桶中，也就是根據元素值特性將集合拆分為多個區域，則拆分後形成的多個桶，從值域上看是處於有序狀態的。對每個桶中元素進行排序，則所有桶中元素構成的集合是已排序的。

step 1:

遍歷集合可得，最大值為：，最小值為：，待申請桶的個數為：

step 2:

遍歷待排序集合，依次添加各元素到對應的桶中。

step 3:

對每一個桶中元素進行排序，並移動回原始集合中，即完成排序過程。

第一個循環作用為將待排序集合中元素移動到對應的桶中，復雜度為；第二個循環的作用為對每個桶中元素進行排序，並移動回初始集合中，若桶個數為，平均每個桶中元素個數為，則復雜度為。當時，即桶排序向計數排序方式演化，則堆排序不發揮作用，復雜度為，只需要將元素移動回初始集合即可。當時，即桶排序向比較性質排序演算法演化，對集合進行堆排序，並將元素移動回初始集合，復雜度為。

由演算法過程可知，桶排序的時間復雜度為，其中表示桶的個數。由於需要申請額外的空間來保存元素，並申請額外的數組來存儲每個桶，所以空間復雜度為。演算法的穩定性取決於對桶中元素排序時選擇的排序演算法。由桶排序的過程可知，當待排序集合中存在元素值相差較大時，對映射規則的選擇是一個挑戰，可能導致元素集中分布在某一個桶中或者絕大多數桶是空桶的現象，對演算法的時間復雜度或空間復雜度有較大影響，所以同計數排序一樣，桶排序適用於元素值分布較為集中的序列。

Ⅳ 編一程序用簡單選擇排序方法對n個整數排序（從大到小）。對n個數進行降序排列，簡單選擇排序的演算法思

#include<stdio.h>

int main()

{int i,j,t,n,a[100];

printf("請輸入有幾個整數(<=100)：");

scanf("%d",&n);

printf("請輸入這%d個整數： ");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

for(i=0;i<n-1;i++)

{k=i;

for(j=i+1;j<n;j++)

if(a[j]<a[k])

k=j;

t=a[i];a[i]=a[k];a[k]=t;

}

printf("排序以後的數： ");

for(i=0;i<n;i++)

printf("%d ",a[i]);

printf(" ");

return 0;

}

(4)考慮這樣一個排序演算法對於待排序擴展閱讀：

在簡單選擇排序過程中，所需移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄。

最壞情況下，即待排序記錄初始狀態是按第一條記錄最小，之後的記錄從小到大順序排列，則需要移動記錄的次數最多為3（n-1）。

簡單選擇排序過程中需要進行的比較次數與初始狀態下待排序的記錄序列的排列情況無關。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依次類推，共需要進行的比較次數是(n-1)+(n-2)+…+2+1=n(n-1)/2，即進行比較操作的時間復雜度為O(n^2)，進行移動操作的時間復雜度為O(n)。

Ⅳ 計數排序(count sorting)

我認為這是桶排不知對不對。
program tpx;
var b:array[0..100] of integer;
k:0..100;
i:integer;
begin
write('Enter date:(0-100)');
for i:=0 to 100 do b[i]:=0;
for i:= 1 to n do
begin
read(k);
b[k]:=b[k]+1;
end;
writeln('Output data:');
for i:=0 to 100 do
while b[i]>0 do begin write(i:6);b[i]:=b[i]-1 end;
writeln;
end.

Ⅵ 對同一個基本有序的待排序列分別進行堆排序、快速排序和冒泡排序,最省時間的演算法是什麼

對同一個基本有序的待排序列分別進行堆排序、快速排序和冒泡排序，最省時間的演算法是冒泡排序。

冒泡排序的最好比較次數為n次，最差比較次數為n＾2次，最差比較次數為0次，最差比較次數為n＾2次，最差比較次數為1次，最差比較次數為1次。

快速排序的最好比較次數為nlogn次，最差比較次數為n＾2次，最差比較次數為logn次，最差比較次數為n次，最差比較次數為logn次，最差比較次數為n次。

堆排序的最好比較次數為nlogn次，最差比較次數為nlogn次，最差比較次數為nlogn次，最差比較次數為nlogn次，最差比較次數為1次，最差比較次數為1次。

(6)考慮這樣一個排序演算法對於待排序擴展閱讀：

冒泡排序（BubbleSort）重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。

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

Ⅶ 交換類排序演算法

根據排序時數據所佔用存儲器的不同，可將排序分為兩類，一類是整個排序過程完全在內存中進行，成為內部排序。另一類是由於待排序記錄數據太大，內存無法容納全部數據，需要藉助外部存儲才能完成，稱為外部排序。

按照方法可以分為交換類排序和插入類排序。

演算法思想：

從待排序記錄序列中選取一個記錄（通常是第一個）作為樞軸，其關鍵字設為K1，然後將其餘關鍵字小於K1的記錄移動到前面，關鍵字大於K1的移動到後面，結果將待排序記錄分成兩個子表，最後將關鍵字為K1的記錄插到分界線的位置處。這個過程稱為一趟快速排序。

演算法步驟：

假設待劃分序列為r,r,....,r,具體實現過程，可以設兩個指針i和j，它們的初值分別是left和right。首先將基準記錄r移至變數x中，然後反復進行下兩步，直到i和j相遇。

1、i從左向右掃描直到r>x時，將r移至空單元r，此時r相當於空單元。

2、j從右向左掃描直到r<x時，將r移至空單元r，此時r相當於空單元。

當i和j相遇的時候，給空單元賦值x，然後對於左右形成的兩個子表採用同樣的方法進一步劃分。

Ⅷ 基本排序演算法原理

演算法原理：每次對相鄰的兩個元素進行比較，若前者大於後者則進行交換，如此一趟下來最後一趟的就是最大元素，重復以上的步驟，除了已經確定的元素。

演算法原理：每次對相鄰的兩個元素進行比較，若前者大於後者則進行交換，如此一趟下來最後一趟的就是最大元素，重復以上的步驟，除了已經確定的元素

演算法步驟

1) 設置兩個變數i、j，排序開始的時候：i=0，j=n-1；

2）第一個數組值作為比較值，首先保存到temp中，即temp=A[0]；

3）然後j-- ,向前搜索,找到小於temp後,因為s[i]的值保存在temp中,所以直接賦值,s[i]=s[j]

4）然後i++,向後搜索,找到大於temp後,因為s[j]的值保存在第2步的s[i]中,所以直接賦值,s[j]=s[i],然後j--,避免死循環

5）重復第3、4步，直到i=j,最後將temp值返回s[i]中

6) 然後採用「二分」的思想,以i為分界線,拆分成兩個數組 s[0,i-1]、s[i+1,n-1]又開始排序

排序圖解

演算法原理：從第一個元素開始，左邊視為已排序數組，右邊視為待排序數組，從左往右依次取元素，插入左側已排序數組，對插入新元素的左側數組重新生成有序數組。需要注意的是，在往有序數組插入一個新元素的過程中，我們可以採用按順序循環比較，也可以通過折半查找法來找到新元素的位置，兩種方式的效率取決於數組的數據量

演算法原理：希爾排序也是利用插入排序的思想來排序。希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後演算法再取越來越小的步長進行排序，演算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了，插入效率比較高。

排序圖解

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。選擇排序的主要優點與數據移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種。

歸並排序，顧名思義就是一種「遞歸合並」的排序方法（這個理解很重要）。對於一個數列，我們把它進行二分處理，依次遞歸下去，然後將小范圍的數進行排序，最後將其合並在一起。就實現了歸並排序。

這實際上是運用了分治思想，顯然，想要把一個數列排好序，最終達到的目的就是它的任何一部分都是有序的。這樣的話，我們可以考慮分別把數列分成N多個部分，讓每個部分分別有序，然後再將其統一，變成所有的東西都有序。這樣就實現了排序。這個想法就叫分治思想。

排序圖解

排序圖解

Ⅸ 排序法都有哪些

一、插入排序(InsertionSort)
1.基本思想：
每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。
2.排序過程：
【示例】：
[初始關鍵字][49]38659776132749
J=2(38)[3849]659776132749
J=3(65)[384965]9776132749
J=4(97)[38496597]76132749
J=5(76)[3849657697]132749
J=6(13)[133849657697]2749
J=7(27)[13273849657697]49
J=8(49)[1327384949657697]

ProcereInsertSort(VarR:FileType);
//對R[1..N]按遞增序進行插入排序,R[0]是監視哨//
Begin
forI:=2ToNDo//依次插入R[2],...,R[n]//
begin
R[0]:=R;J:=I-1;
WhileR[0]<R[J]Do//查找R的插入位置//
begin
R[J+1]:=R[J];//將大於R的元素後移//
J:=J-1
end
R[J+1]:=R[0];//插入R//
end
End;//InsertSort//

復制代碼二、選擇排序
1.基本思想：
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
2.排序過程：
【示例】：
初始關鍵字[4938659776132749]
第一趟排序後13［38659776492749]
第二趟排序後1327［659776493849]
第三趟排序後132738[9776496549]
第四趟排序後13273849[49976576]
第五趟排序後1327384949[979776]
第六趟排序後132738494976[7697]
第七趟排序後13273849497676[97]
最後排序結果1327384949767697

ProcereSelectSort(VarR:FileType);//對R[1..N]進行直接選擇排序//
Begin
forI:=1ToN-1Do//做N-1趟選擇排序//
begin
K:=I;
ForJ:=I+1ToNDo//在當前無序區R[I..N]中選最小的元素R[K]//
begin
IfR[J]<R[K]ThenK:=J
end;
IfK<>IThen//交換R和R[K]//
beginTemp:=R;R:=R[K];R[K]:=Temp;end;
end
End;//SelectSort//

復制代碼三、冒泡排序(BubbleSort)
1.基本思想：
兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。
2.排序過程：
設想被排序的數組R［1..N］垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。
【示例】：
4913131313131313
3849272727272727
6538493838383838
9765384949494949
7697654949494949
1376976565656565
2727769776767676
4949497697979797

ProcereBubbleSort(VarR:FileType)//從下往上掃描的起泡排序//
Begin
ForI:=1ToN-1Do//做N-1趟排序//
begin
NoSwap:=True;//置未排序的標志//
ForJ:=N-1DownTo1Do//從底部往上掃描//
begin
IfR[J+1]<R[J]Then//交換元素//
begin
Temp:=R[J+1];R[J+1:=R[J];R[J]:=Temp;
NoSwap:=False
end;
end;
IfNoSwapThenReturn//本趟排序中未發生交換，則終止演算法//
end
End;//BubbleSort//

復制代碼四、快速排序（QuickSort）
1.基本思想：
在當前無序區R[1..H]中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區劃分為左右兩個較小的無序區：R[1..I-1]和R[I+1..H]，且左邊的無序子區中數據元素均小於等於基準元素，右邊的無序子區中數據元素均大於等於基準元素，而基準X則位於最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止。
2.排序過程：
【示例】：
初始關鍵字[4938659776132749］
第一次交換後
［2738659776134949］
第二次交換後
［2738499776136549］
J向左掃描，位置不變，第三次交換後
［2738139776496549］
I向右掃描，位置不變，第四次交換後
［2738134976976549］
J向左掃描
［2738134976976549］
（一次劃分過程）

初始關鍵字
［4938659776132749］
一趟排序之後
［273813］49［76976549］
二趟排序之後
［13］27［38］49［4965］76［97］
三趟排序之後1327384949［65］7697
最後的排序結果1327384949657697
各趟排序之後的狀態

ProcereParttion(VarR:FileType;L,H:Integer;VarI:Integer);
//對無序區R[1,H]做劃分，I給以出本次劃分後已被定位的基準元素的位置//
Begin
I:=1;J:=H;X:=R;//初始化，X為基準//
Repeat
While(R[J]>=X)And(I<J)Do
begin
J:=J-1//從右向左掃描，查找第1個小於X的元素//
IfI<JThen//已找到R[J]〈X//
begin
R:=R[J];//相當於交換R和R[J]//
I:=I+1
end;
While(R<=X)And(I<J)Do
I:=I+1//從左向右掃描，查找第1個大於X的元素///
end;
IfI<JThen//已找到R>X//
begin R[J]:=R;//相當於交換R和R[J]//
J:=J-1
end
UntilI=J;
R:=X//基準X已被最終定位//
End;//Parttion//

復制代碼

ProcereQuickSort(VarR:FileType;S,T:Integer);//對R[S..T]快速排序//
Begin
IfS<TThen//當R[S..T]為空或只有一個元素是無需排序//
begin
Partion(R,S,T,I);//對R[S..T]做劃分//
QuickSort(R,S,I-1);//遞歸處理左區間R[S,I-1]//
QuickSort(R,I+1,T);//遞歸處理右區間R[I+1..T]//
end;
End;//QuickSort//

復制代碼五、堆排序(HeapSort)
1.基本思想：
堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
2.堆的定義:N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性：
Ki≤K2iKi≤K2i+1(1≤I≤[N/2])

堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大於等於其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結點的關鍵字均大於等於其孩子的關鍵字，則稱之為大根堆。
3.排序過程：
堆排序正是利用小根堆（或大根堆）來選取當前無序區中關鍵字小（或最大）的記錄實現排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區調整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區中的最後一個記錄交換。這樣，正好和直接選擇排序相反，有序區是在原記錄區的尾部形成並逐步向前擴大到整個記錄區。
【示例】：對關鍵字序列42，13，91，23，24，16，05，88建堆

ProcereSift(VarR:FileType;I,M:Integer);
//在數組R[I..M]中調用R，使得以它為完全二叉樹構成堆。事先已知其左、右子樹(2I+1<=M時)均是堆//
Begin
X:=R;J:=2*I;//若J<=M,R[J]是R的左孩子//
WhileJ<=MDo//若當前被調整結點R有左孩子R[J]//
begin
If(J<M)AndR[J].Key<R[J+1].KeyThen
J:=J+1//令J指向關鍵字較大的右孩子//
//J指向R的左、右孩子中關鍵字較大者//
IfX.Key<R[J].KeyThen//孩子結點關鍵字較大//
begin
R:=R[J];//將R[J]換到雙親位置上//
I:=J;J:=2*I//繼續以R[J]為當前被調整結點往下層調整//
end;
Else
Exit//調整完畢，退出循環//
end
R:=X;//將最初被調整的結點放入正確位置//
End;//Sift//

復制代碼

ProcereHeapSort(VarR:FileType);//對R[1..N]進行堆排序//
Begin
ForI:=NDivDownto1Do//建立初始堆//
Sift(R,I,N)
ForI:=NDownto2do//進行N-1趟排序//
begin
T:=R[1];R[1]:=R;R:=T;//將當前堆頂記錄和堆中最後一個記錄交換//
Sift(R,1,I-1)//將R[1..I-1]重成堆//
end
End;//HeapSort//

復制代碼六、幾種排序演算法的比較和選擇
1.選取排序方法需要考慮的因素：
(1)待排序的元素數目n；
(2)元素本身信息量的大小；
(3)關鍵字的結構及其分布情況；
(4)語言工具的條件，輔助空間的大小等。
2.小結：
(1)若n較小(n<=50)，則可以採用直接插入排序或直接選擇排序。由於直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。
(2)若文件的初始狀態已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。
(3)若n較大，則應採用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序法中被認為是最好的方法。
(4)在基於比較排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlog2n)的時間。

這句話很重要它告訴我們自己寫的演算法是有改進到最優當然沒有必要一直追求最優
(5)當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。

導航:首頁 > 源碼編譯 > 考慮這樣一個排序演算法對於待排序

考慮這樣一個排序演算法對於待排序

與考慮這樣一個排序演算法對於待排序相關的資料