基本介紹
概念,常見排序算法,分類,冒泡排序,原理,優劣,Pascal程式,c、c++程式,c#程式,選擇排序,原理,優劣,C++程式,Java程式,插入排序,原理,優劣,算法複雜度,Java程式,C++程式,希爾排序,原理,Pascal程式,C程式,優劣,快速排序,原理,優劣,Pascal程式,JAVA程式,箱排序,原理,優劣,歸併排序,原理,Pascal程式,樹型排序,原理,優劣,Pascal程式,
概念
常見排序算法
分類
◆穩定排序：假設在待排序的檔案中，存在兩個或兩個以上的記錄具有相同的關鍵字，在
用某種排序法排序後，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法
是穩定的。其中冒泡，插入，基數，歸併屬於穩定排序，選擇，快速，希爾，歸屬於不穩定排序。
◆就地排序：若排序算法所需的輔助空間並不依賴於問題的規模n，即輔助空間為O（1），
則稱為就地排序。
冒泡排序
原理
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先比較a[1]與a[2]的值，若a[1]大於a[2]則交換兩者的值，否則不變。再比較a[2]與a[3]的值，若a[2]大於a[3]則交換兩者的值，否則不變。再比較a[3]與a[4]，以此類推，最後比較a[n-1]與a[n]的值。這樣處理一輪後，a[n]的值一定是這組數據中最大的。再對a[1]~a[n-1]以相同方法處理一輪，則a[n-1]的值一定是a[1]~a[n-1]中最大的。再對a[1]~a[n-2]以相同方法處理一輪，以此類推。共處理n-1輪後a[1]、a[2]、……a[n]就以升序排列了。降序排列與升序排列相類似，若a[1]小於a[2]則交換兩者的值，否則不變，後面以此類推。 總的來講，每一輪排序後最大（或最小）的數將移動到數據序列的最後，理論上總共要進行n(n-1）/2次交換。
優劣
優點：穩定。
缺點：慢，每次只能移動相鄰兩個數據。
Pascal程式
program name;
var
a:array[1..N] of 1..MAX;
temp,i,j:integer;
begin
randomize;
for i:=1 to N do a:=1+random(MAX);
writeln('Array before sorted:');
for i:=1 to N do write(a,' ');
writeln;
for i:=N-1 downto 1 do
for j:=1 to i do
if a[j]<a[j+1] then
begin
temp:=a[j];
a[j]:=a[j+1];
a[j+1]:=temp
end;
writeln('Array sorted:');
for i:=1 to N do write(a,' ');
writeln;
writeln('End sorted.');
readln;
end.
c、c++程式
N個數排序：
inttemp=0;inta[10]={7,8,5,4,3,2,6,9,0,1};for(intn=0;n<10;++n){cout<<a[n]<<endl;}//輸出，僅用來測試for(inti=0;i<10-1;++i)//只需要冒泡9個數最後一個就已經有序了for(intj=0;j<10-i-1;++j)//j的取值需<10-i-1;為何-1，if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}for(intn=0;n<10;++n){cout<<a[n]<<endl;}//輸出for(inti=0;i<10-1;++i)//只需要冒泡9個數最後一個就已經有序了for(intj=0;j<10-i-1;++j){if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}for(intn=0;n<10;++n){cout<<a[n]<<endl;}//輸出c#程式
指定個數排序：
static void Main(string[] args)
{
int[] arr = { 4, 2, 5, 7, 4, 9, 6, 21 };
for (int i = 0; i < arr.Length; i++)
{
for (int j = i + 1; j < arr.Length; j++)
{
int temp = 0;
if (arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
foreach (int num in arr)
{
Console.Write(" {0}", num);
}
Console.ReadKey();
}
選擇排序
原理
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
選擇排序是不穩定的排序方法(很多教科書都說選擇排序是不穩定的，但是，完全可以將其實現成穩定的排序方法)。
n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R[1..n]，有序區為空。
②第1趟排序
在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
優劣
優點：移動數據的次數已知（n-1次）。
缺點：比較次數多，不穩定。
C++程式
#include<iostream>#include<time.h>#include<iomanip>using namespace std;const int N=10;int main(){ int a[N],i,j,temp,b; srand(time(NULL)); for(i=0;i<N;i++) a[i]=rand()%100; for(i=0;i<N;i++) cout<<setw(3)<<a[i]; cout<<endl; for(i=0;i<N-1;i++) { temp=i; for(j=i+1;j<N;j++) { if(a[temp]>a[j]) temp=j; } if(i!=temp) { b=a[temp]; a[temp]=a[i]; a[i]=b;} } for(i=0;i<N;i++) cout<<setw(3)<<a[i]; cout<<endl;}Java程式
public static void selectSort(int[]a){ int minIndex=0; int temp=0; if((a==null)||(a.length==0)) return; for(int i=0;i<a.length-1;i++) { minIndex=i;//無序區的最小數據數組下標 for(intj=i+1;j<a.length;j++) { //在無序區中找到最小數據並保存其數組下標 if(a[j]<a[minIndex]) { minIndex=j; } } if(minIndex!=i) { //如果不是無序區的最小值位置不是默認的第一個數據，則交換之。 temp=a[i]; a[i]=a[minIndex]; a[minIndex]=temp; } }}插入排序
原理
插入排序：已知一組升序排列數據a[1]、a[2]、……a[n]，一組無序數據b[1]、b[2]、……b[m]，需將二者合併成一個升序數列。首先比較b[1]與a[1]的值，若b[1]大於a[1]，則跳過，比較b[1]與a[2]的值，若b[1]仍然大於a[2]，則繼續跳過，直到b[1]小於a數組中某一數據a[x]，則將a[x]~a[n]分別向後移動一位，將b[1]插入到原來a[x]的位置這就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若無數組a，可將b[1]當作n=1的數組a）
優劣
優點：穩定，快。
缺點：比較次數不一定，比較次數越多，插入點後的數據移動越多，特別是當數據總量龐大的時候，但用鍊表可以解決這個問題。
算法複雜度
如果目標是把n個元素的序列升序排列，那么採用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那么此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序算法的時間複雜度為O(n^2）。因而，插入排序不適合對於數據量比較大的排序套用。但是，如果需要排序的數據量很小為量級小於千，那么插入排序還是一個不錯的選擇。
Java程式
/***插入排序*@paramarr*@return*/private static int[] insertSort(int[]arr){if(arr == null || arr.length < 2){ return arr;}for(inti=1;i<arr.length;i++){for(intj=i;j>0;j--){if(arr[j]<arr[j-1]){//TODO:int temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}else{break;}}}return arr;}C++程式
#include<iterator>template<typenamebiIter>voidinsertion_sort(biIterbegin,biIterend){typedeftypenamestd::iterator_traits<biIter>::value_typevalue_type;biIterbond=begin;std::advance(bond,1);for(;bond!=end;std::advance(bond,1)){value_typekey=*bond;biIterins=bond;biIterpre=ins;std::advance(pre,-1);while(ins!=begin&&*pre>key){*ins=*pre;std::advance(ins,-1);std::advance(pre,-1);}*ins=key;}}#include<iterator>template<typenamebiIter>voidinsertion_sort(biIterbegin,biIterend){typedeftypenamestd::iterator_traits<biIter>::value_typevalue_type;biIterbond=begin;std::advance(bond,1);for(;bond!=end;std::advance(bond,1)){value_typekey=*bond;biIterins=bond;biIterpre=ins;std::advance(pre,-1);while(ins!=begin&&*pre>key){*ins=*pre;std::advance(ins,-1);std::advance(pre,-1);}*ins=key;}} 希爾排序
原理
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d<n)，將a[1]、a[1+d]、a[1+2d]……列為第一組，a[2]、a[2+d]、a[2+2d]……列為第二組……，a[d]、a[2d]、a[3d]……列為最後一組以次類推，在各組內用插入排序，然後取d'<d，重複上述操作，直到d=1。
Pascal程式
program Shell;
type
arr=array[1..100] of integer;
var
a:arr;
i,j,t,d,n:integer;
bool:boolean;
begin
readln(n);
for i:=1 to n do
read(a[i]);
d:=n;
while d>1 do
begin
d:=d div 2;
for j:=d+1 to n do
begin
t:=a[j];
i:=j-d;
while (i>0) and (a[i]>t) do
begin
a[i+d]:=a[i];
i:=i-d;
end;
a[i+d]:=t;
end;
end;
for i:=1 to n do write(a[i],' ');
end.
C程式
int[] a = new int[] { 2, 0, 5, 9, 3, 1, 7 }; int n = a.Length; int k = n / 2; while (k > 0) { for (int i = k; i < n; i++) { int t = a[i]; int j = i - k; while (j >= 0 && t < a[j]) { a[j + k] = a[j]; j = j - k; } a[j + k] = t; } k /= 2; }優劣
優點：快，數據移動少。
缺點：不穩定，d的取值是多少，應取多少個不同的值，都無法確切知道，只能憑經驗來取。
不需要大量的輔助空間，和歸併排序一樣容易實現。希爾排序是基於插入排序的一種算法， 在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間複雜度為 O(N*(logN)2)， 沒有快速排序算法快 O(N*(logN))，因此中等大小規模表現良好，對規模非常大的數據排序不是 最優選擇。但是比O(N2）複雜度的算法快得多。並且希爾排序非常容易實現，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞 的情況下執行的效率會非常差。 專家門提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快， 再改成快速排序這樣更高級的排序算法. 本質上講，希爾排序算法的一種改進，減少了其複製的次數，速度要快很多。 原因是，當N值很大時數據項每一趟排序需要的個數很少，但數據項的距離很長。 當N值減小時每一趟需要和動的數據增多，此時已經接近於它們排序後的最終位置。 正是這兩種情況的結合才使希爾排序效率比插入排序高很多。
快速排序
快速排序是大家已知的常用排序算法中最快的排序方法。
原理
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。首先任取數據a[x]作為基準。比較a[x]與其它數據並排序，使a[x]排在數據的第k位，並且使a[1]~a[k-1]中的每一個數據<a[x]，a[k+1]~a[n]中的每一個數據>a[x]，然後採用分治的策略分別對a[1]~a[k-1]和a[k+1]~a[n]兩組數據進行快速排序。
優劣
優點：極快，數據移動少。
缺點：不穩定。
Pascal程式
program kuaipai;
var
a:array[1..100]of integer;
k,l,n,i:integer;
procedure kp(z,y:integer);
var
i,j,t:integer;
begin
i:=z;
j:=y;
t:=a[i];
repeat
while (a[j]>t)and(j>i) do
begin
inc(k);
dec(j);
end;
if i<j then
begin
a[i]:=a[j];
inc(i);
inc(l);
while (a[i]<t)and(i<j) do
begin
inc(k);
inc(i);
end;
if i<j then begin
a[j]:=a[i];
dec(j);
inc(l);
end;
end;
until i=j;
a[i]:=t;
inc(i);
dec(j);
inc(l);
if z<j then kp(z,j);
if i<y then kp(i,y);
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
k:=0;
l:=0;
kp(1,n);
for i:=1 to n do
write(a[i],' ');
end.
JAVA程式
//化分區間,找到最後元素的排序位置。並返回分隔的點（即最後一數據排序的位置）。
//劃分的區間是[nBegin, nEnd). pData是保存數據的指針
static int Partition(int[] pData, int nBeging, int nEnd)
{
int i = nBeging - 1; //分隔設定號，最後nD保存在這裡
--nEnd;
int nD = pData[nEnd]; //比較的數據。
int nTemp; // 交換用的臨時數據
//遍歷數據比較，找到nD的位置，這裡注意，比較結果是,
//如果i的左邊是小於等於nD的，i的右邊是大於nD的
for (int j = nBeging; j < nEnd; ++j)
{
if (pData[j] <= nD) //如果數據比要比較的小，則在該數據的左邊，與i+1交換
{
++i; //小於nD的數據多一個，所以要加1，i的左邊數據都比nD小
nTemp = pData[i]; //交換數據
pData[i] = pData[j];
pData[j] = nTemp;
}
}
//最後不要忘了吧nD和i+1交換，因為這裡就是nD的位置咯。
++i;
pData[nEnd] = pData[i];
pData[i] = nD;
return i; //返回nD的位置，就是分割的位置。
}
//排序的遞歸調用。
static int QuickSortRecursion(int[] pData, int nBeging, int nEnd)
{
if (nBeging >= nEnd -1) //如果區域不存在或只有一個數據則不遞歸排序
{
return 1;
}
//這裡因為分割的時候，分割點處的數據就是排序中他的位置。
//也就是說他的左邊的數據都小於等於他，他右邊的數據都大於他。
//所以他不在遞歸調用的數據中。
int i = Partition(pData, nBeging, nEnd); //找到分割點
QuickSortRecursion(pData, nBeging, i); //遞歸左邊的排序
QuickSortRecursion(pData, i + 1, nEnd); //遞歸右邊的排序
return 1;
}
//快速排序
public static int QuickSort(int[] pData, int nLen)
{
//遞歸調用，快速排序。
QuickSortRecursion(pData, 0, nLen);
return 1;
}
箱排序
已知一組無序正整數數據a[1]、a[2]、……a[n]，需將其按升序排列。首先定義一個數組x[m],且m>=a[1]、a[2]、……a[n]，接著循環n次，每次x[a]++。
原理
1、箱排序的基本思想
【例】要將一副混洗的52張撲克牌按點數A<2<…<J<Q<K排序，需設定13個"箱子"，排序時依次將每張牌按點數放入相應的箱子裡，然後依次將這些箱子首尾相接，就得到了按點數遞增序排列的一副牌。
2、箱排序中，箱子的個數取決於關鍵字的取值範圍。
若R[0..n-1]中關鍵字的取值範圍是0到m-1的整數，則必須設定m個箱子。因此箱排序要求關鍵字的類型是有限類型，否則可能要無限個箱子。
3、箱子的類型應設計成鍊表為宜
一般情況下每個箱子中存放多少個關鍵字相同的記錄是無法預料的，故箱子的類型應設計成鍊表為宜。
4、為保證排序是穩定的，分配過程中裝箱及收集過程中的連線必須按先進先出原則進行。
（1） 實現方法一
每個箱子設為一個鏈佇列。當一記錄裝入某箱子時，應做人隊操作將其插入該箱子尾部；而收集過程則是對箱子做出隊操作，依次將出隊的記錄放到輸出序列中。
（2） 實現方法二
若輸入的待排序記錄是以鍊表形式給出時，出隊操作可簡化為是將整個箱子鍊表連結到輸出鍊表的尾部。這只需要修改輸出鍊表的尾結點中的指針域，令其指向箱子鍊表的頭，然後修改輸出鍊表的尾指針，令其指向箱子鍊表的尾即可。
5、算法簡析
分配過程的時間是O(n)；收集過程的時間為O(m) （採用鍊表來存儲輸入的待排序記錄）或O(m+n)。因此，箱排序的時間為O(m+n)。若箱子個數m的數量級為O(n)，則箱排序的時間是線性的，即O(n)。箱排序實用價值不大，僅適用於作為基數排序的一個中間步驟。
優劣
優點：快，效率達到O(1)。
缺點：數據範圍必須為正整數並且比較小。
歸併排序
原理
歸併排序是多次將兩個或兩個以上的有序表合併成一個新的有序表。最簡單的歸併是直接將兩個有序的子表合併成一個有序的表。
歸併排序是穩定的排序.即相等的元素的順序不會改變。如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括弧中是記錄的關鍵字)時輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序，這對要排序數據包含多個信息而要按其中的某一個信息排序,要求其它信息儘量按輸入的順序排列時很重要，這也是它比快速排序優勢的地方。
Pascal程式
program guibing;
type
arr=array[1..100] of integer;
var
a,b,c:arr;
i:integer;
procedure gb(r:arr;l,m,n:integer;var r2:arr);
var
i,j,k,p:integer;
begin
i:=l;
j:=m+1;
k:=l-1;
while (i<=m)and (j<=n) do
begin
k:=k+1;
if r[i]<=r[j] then
begin
r2[k]:=r[i];
i:=i+1
end
else
begin
r2[k]:=r[j];
j:=j+1
end
end;
if i<=m then
for p:=i to m do
begin
k:=k+1;
r2[k]:=r[p]
end;
if j<=n then
for p:=j to n do
begin
k:=k+1;
r2[k]:=r[p]
end;
end;
procedure gp( var r,r1:arr;s,t:integer);
var
k:integer;
c:arr;
begin
if s=t then r1[s]:=r[s]
else
begin
k:=(s+t) div 2;
gp(r,c,s,k);
gp(r,c,k+1,t);
gb(c,s,k,t,r1)
end;
end;
begin
readln(n);
for i:= 1 to n do
read(a[i]);
gp(a,b,1,n);
for i:=1 to n do
write(b[i],' ');
writeln;
end.
樹型排序
原理
樹形選擇排序又稱錦標賽排序（Tournament Sort），是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關鍵字進行兩兩比較，然後在n/2個較小者之間再進行兩兩比較，如此重複，直至選出最小的記錄為止。樹形排序的要素就是讓所有的左子樹都比根及右子樹大。
優劣
優點：效率高。
缺點：不穩定。
Pascal程式
program shupai;
type
point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var
a:array[1..100]of integer;
root,first:point;
k:boolean;
i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin
w:=d;
right:=nil;
left:=nil
end;
if k then
begin
root:=p;
k:=false
end;
end
else
with p^ do
if d>=w then
hyt(d,right)
else
hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
begin
if left<>nil then
hyt1(left);
write(w,' ');
if right<>nil then hyt1(right);
end;
end;
begin
first:=nil;
k:=true;
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
hyt(a[i],first);
hyt1(root);
end.
