概念
将雜亂無章的數據元素,通過一定的方法按關鍵字順序排列的過程叫做排序。
常見排序算法
快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序算法,而基數排序、冒泡排序、直接插入排序、折半插入排序、歸并排序是穩定的排序算法。
分類
◆穩定排序:假設在待排序的文件中,存在兩個或兩個以上的記錄具有相同的關鍵字,在
用某種排序法排序後,若這些相同關鍵字的元素的相對次序仍然不變,則這種排序方法
是穩定的。其中冒泡,插入,基數,歸并屬于穩定排序,選擇,快速,希爾,歸屬于不穩定排序。
◆就地排序:若排序算法所需的輔助空間并不依賴于問題的規模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
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++程序
對N個數進行從小到大排序:
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++程序
Java程序
插入排序
原理
插入排序:已知一組升序排列數據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程序
C++程序
希爾排序
由希爾在1959年提出,是對直接插入排序的優化,又稱希爾排序(ShellSort)。
原理
已知一組無序數據a[1]、a[2]、……a[n],需将其按升序排列。發現當n不大時,插入排序的效果很好。首先取一增量d(d
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程序
優劣
優點:快,數據移動少。
缺點:不穩定,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[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
begin
a[i]:=a[j];
inc(i);
inc(l);
while (a[i]
begin
inc(k);
inc(i);
end;
if i
a[j]:=a[i];
dec(j);
inc(l);
end;
end;
until i=j;
a[i]:=t;
inc(i);
dec(j);
inc(l);
if z
if i
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. [5]
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、箱排序的基本思想
箱排序也稱桶排序(Bucket Sort),其基本思想是:設置若幹個箱子,依次掃描待排序的記錄R[0],R[1],…,R[n-1],把關鍵字等于k的記錄全都裝入到第k個箱子裡(分配),然後按序号依次将各非空的箱子首尾連接起來(收集)。
【例】要将一副混洗的52張撲克牌按點數A<2<…
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.
樹型排序
原理
樹形選擇排序又稱錦标賽排序(TournamentSort),是一種按照錦标賽的思想進行選擇排序的方法。首先對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.