排序
計算機內經常進行的操作
排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。分內部排序和外部排序，若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。內部排序的過程是一個逐步擴大記錄的有序序列長度的過程。
將雜亂無章的數據元素，通過一定的方法按關鍵字順序排列的過程叫做排序。
快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序演演算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸併排序是穩定的排序演演算法。
◆穩定排序：假設在待排序的文件中，存在兩個或兩個以上的記錄具有相同的關鍵字，在
用某種排序法排序后，若這些相同關鍵字的元素的相對次序仍然不變，則這種排序方法
是穩定的。其中冒泡，插入，基數，歸併屬於穩定排序，選擇，快速，希爾，歸屬於不穩定排序。
◆就地排序：若排序演演算法所需的輔助空間並不依賴於問題的規模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次交換。
優點：穩定。
缺點：慢，每次只能移動相鄰兩個數據。
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]
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.
N個數排序：
指定個數排序：
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次）。
缺點：比較次數多，不穩定。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include #include #include using namespace std; const int N=10; int main() { int a[N],i,j,temp,b; srand(time(NULL)); for(i=0;i a[i]=rand()%100; for(i=0;i cout< cout< for(i=0;i { temp=i; for(j=i+1;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 cout< cout< |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | public static void selectSort(int[]a) { int minIndex=0; int temp=0; if((a==null)||(a.length==0)) return; for(int i=0;i { minIndex=i;//無序區的最小數據數組下標 for(intj=i+1;j { //在無序區中找到最小數據並保存其數組下標 if(a[j] { 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）。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小為量級小於千，那麼插入排序還是一個不錯的選擇。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | private static int[] insertSort(int[]arr){ if(arr == null || arr.length < 2){ return arr; } for(inti=1;i for(intj=i;j>0;j--){ if(arr[j] //TODO: int temp=arr[j]; arr[j]=arr[j-1]; arr[j-1]=temp; }else{ break; } } } return arr; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include template voidinsertion_sort(biIterbegin,biIterend) { typedeftypenamestd::iterator_traits 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; } } |
由希爾在1959年提出，又稱希爾排序(shell排序)。
已知一組無序數據a[1]、a[2]、……a[n]，需將其按升序排列。發現當n不大時，插入排序的效果很好。首先取一增量d(d
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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; } |
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.
優點：快，數據移動少。
缺點：不穩定，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]兩組數據進行快速排序。
優點：極快，數據移動少。
缺點：不穩定。
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.
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int i = left;
int j = right;
int pivot = arr[left + (right - left)/2];
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if(i
quickSort(arr, i, right);
}
if(j>left){
quickSort(arr, left, j);
}
}
已知一組無序正整數數據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 是按輸入的順序，這對要排序數據包含多個信息而要按其中的某一個信息排序，要求其它信息盡量按輸入的順序排列時很重要，這也是它比快速排序優勢的地方。
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個較小者之間再進行兩兩比較，如此重複，直至選出最小的記錄為止。樹形排序的要素就是讓所有的左子樹都比根及右子樹大。
優點：效率高。
缺點：不穩定。
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.
基本信息
- 中文名
- 排序
- 外文名
- sequence
- 應用學科
- 數學、計算機
- 排序演算法
- 快速排序、希爾排序、堆排序等
- 分類
- 穩定排序等
- 性質
- 計算機內經常進行的一種操作
目錄