各個排序演算法適用情況和長處

1. 緊急!!!!!!!有什麼排序方法各有什麼特點

4.1 簡單排序

1.選擇排序

選擇排序的基本思想是：

對待排序的記錄序列進行n-1遍的處理，第1遍處理是將L[1..n]中最小者與L[1]交換位置，第2遍處理是將L[2..n]中最小者與L[2]交換位置，......，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置就已經按從小到大的順序排列好了。

例1:輸入序列數據按非減順序輸出.

程序如下:

program xzpx;
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
writeln;
for i:=1 to n-1 do
begin
k:=i;
for j:=i+1 to n do
if a[j]<a[k] then k:=j;
if k<>i then
begin t:=a[i];a[i]:=a[k];a[k]:=t;end;
end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.

2.插入排序
插入排序的基本思想:經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置p，原來p後的元素一一向右移動一個位置,使得L[1..i]又是排好序的序列。

例2:輸入序列數據按非減順序輸出.

程序1:

program crpx;
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
writeln;
for i:=2 to n do
begin
k:=a[i];j:=i-1;
while (k<a[j]) and (j>0) do
begin a[j+1]:=a[j];j:=j-1 end;
a[j+1]:=k;
end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.

3.冒泡排序

冒泡排序又稱交換排序其基本思想是:對待排序的記錄的關鍵字進行兩兩比較,如發現兩個

記錄是反序的,則進行交換,直到無反序的記錄為止。

例:輸入序列數據按非減順序輸出。

程序1:

program mppx;
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
for i:=1 to n -1 do
for j:=n downto i+1 do
if a[j-1]<a[j] then
begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.

程序2：

program mppx;
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
bool:boolean;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
i:=1;bool:=true;
while (i<n) and bool do
begin
bool:=false;
for j:=n downto i+1 do
if a[j-1]<a[j] then
begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=true end;
i:=i+1;
end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.

程序3：

program mppx;
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a[i]);
writeln;
k:=n;
while k>0 do
begin
j:=k-1;k:=0;
for i:=1 to j do
if a[i]>a[i+1] then
begin t:=a[i];a[i]:=a[i+1];a[i+1]:=t;k:=i;end;
end;
write('output data:');
for i:= 1 to n do write(a[i]:6);
writeln;
end.

返回

4.2快速排序

快速排序的思想是:先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結束.

例:輸入一組數據小到大排序.

程序1:

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.

程序2:

program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin b[i]:=b[j];i:=i+1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin b[j]:=b[i];j:=j-1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.

返回

4.3希爾排序

基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序或冒泡排序。

序列分割方法：將相隔某個增量h的元素構成一個子序列。在排序過程中，逐次減小這個增量，最後當h減到1時，進行一次插入排序或冒泡排序，排序就完成。增量序列一般採用：d1=n div 2 ,di=di-1 div 2 ；i=2,3,4.....其中n為待排序序列的長度。

程序1:(子序列是插入排序)

program xepx;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i,j,t,d:integer;
bool:boolean;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
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;
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.

程序2:(子序列是冒泡排序)

program xepx;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i,temp,d:integer;
bool:boolean;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
d:=n
while d>1 do
begin
d:=d div 2;
repeat
bool:=true;
for i:=1 to n-d do
if a[i]>a[i+d] then
begin temp:=a[i];a[i]:=a[i+d];a[i+d]:=temp; bool:=false end;
until bool;
end;
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.

返回

4.4 堆排序與二叉樹排序

1.堆排序

堆：設有數據元素的集合（R1,R2,R3,...Rn)它們是一棵順序二叉樹的結點且有

Ri<=R2i 和Ri<=R2i+1(或>=)

堆的性質：堆的根結點上的元素是堆中的最小元素，且堆的每一條路徑上的元素都是有序的。

堆排序的思想是：

1）建初始堆（將結點[n/2],[ n/2]-1,...3,2,1分別調成堆）

2）當未排序完時

輸出堆頂元素，刪除堆頂元素，將剩餘的元素重新建堆。

程序如下：

program ipx;
const n=8;
type arr=array[1..n] of integer;
var a:arr;i:integer;
procere sift(var a:arr;l,m:integer);
var i,j, t:integer;
begin
i:=l;j:=2*i;t:=a[i];
while j<=m do
begin
if (j<m) and (a[j]>a[j+1]) then j:=j+1;
if t>a[j] then
begin a[i]:=a[j];i:=j;j:=2*i; end
else exit;
a[i]:=t;
end;

end;
begin
for i:=1 to n do read(a[i]);
for i:=(n div 2) downto 1 do
sift(a,i,n);
for i:=n downto 2 do
begin
write(a[1]:4);
a[1]:=a[i];
sift(a,1,i-1);
end;
writeln(a[1]:4);
end.

2.二叉樹排序

排序二叉樹：每一個參加排列的數據對應二叉樹的一個結點，且任一結點如果有左（右）子樹，則左（右）子樹各結點的數據必須小（大）於該結點的數據。中序遍歷排序二叉樹即得排序結果。程序如下：

program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i:integer;
procere 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;
procere hyt1(p:point);
begin
with p^ do
begin
if left<>nil then hyt1(left);
write(w:4);
if right<>nil then hyt1(right);
end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a[i],first);
hyt1(root);writeln;
end.

返回

4.5 歸並排序

歸並就是將多個有序的數列合成一個有序的數列。將兩個有序序列合並為一個有序序列叫二路歸並(merge).歸並排序就是n長度為1的子序列,兩兩歸並最後變為有序的序列。

1.二路歸並

例1:將有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合並一個有序表 L.

program gb;

const m=3;n=7;

type arrl1=array[1..m] of integer;

arrl2=array[1..n] of integer;

arrl=array[1..m+n] of integer;

var a:arrl1;

b:arrl2;

c:arrl;

i,j,k,r:integer;

begin

write('Enter l1(sorted):');

for i:=1 to m do read(a[i]);

write('Enter l2(sorted):');

for i:=1 to n do read(b[i]);

i:=1;j:=1;k:=0;

while (i<=m) and (j<=n) do

begin

k:=k+1;

if a[i]<=b[j] then begin c[k]:=a[i];i:=i+1; end

else begin c[k]:=b[j];j:=j+1;end;

end;

if i<=m then for r:=i to m do c[m+r]:=a[r];

if j<=n then for r:=j to n do c[n+r]:=b[r];

writeln('Output data:');

for i:=1 to m+n do write(c[i]:5);

writeln;

end.

2.歸並排序

program gbpx;
const maxn=7;
type arr=array[1..maxn] of integer;
var a,b,c:arr;
i:integer;
procere merge(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;
procere mergesort( 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;
mergesort(r,c,s,k);
mergesort(r,c,k+1,t);
merge(c,s,k,t,r1)
end;
end;
begin
write('Enter data:');
for i:= 1 to maxn do
read(a[i]);
mergesort(a,b,1,maxn);
for i:=1 to maxn do
write(b[i]:9);
writeln;
end.

返回

4.6 線形排序

以上我們討論的演算法均是基於比較的排序演算法，在排序演算法中有基於數字本身的演算法：計數、桶、基數排序。

1.計數排序

基本思想是對於序列中的每一元素x,確定序列中小於x的元素的個數。

例：n個整數序列且每個值在[1,m],排序之。

program jspx;
const m=6;n=8;
var i,j:integer;
a,b:array[1..n] of integer;
c:array[1..m] of integer;
begin
writeln('Enter data:');
for i:=1 to n do read(a[i]);
for i:=1 to m do c[i]:=0;
for i:=1 to n do c[a[i]]:=c[a[i]]+1;
for i:=2 to m do c[i]:=c[i]+c[i-1];
for i:=n downto 1 do
begin
b[c[a[i]]]:=a[i];
c[a[i]]:=c[a[i]]-1;
end;
writeln('Sorted data:');
for i:= 1 to n do
write(b[i]:6);
end.

2.桶排序

桶排序的思想是若待排序的記錄的關鍵字在一個明顯有限范圍內(整型)時,可設計有限個有序桶,每個桶裝入一個值,順序輸出各桶的值,將得到有序的序列。

例：輸入n個0到100之間的整數，由小到大排序輸出。

program tpx;
const n=7;
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.

3.基數排序

基本思想是對n個元素依次按k,k-1,...1位上的數字進行桶排序。

program jspx;
const n=8;
type link=^node;
node=record
data:integer;
next:link;
end;
var i,j,l,m,k:integer;
a:array[1..n] of integer;
s:string;
q,head:array[0..9] of link;
p,p1:link;
begin
writeln('Enter data:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
begin
for j:=0 to 9 do
begin
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
end;
for j:=1 to n do
begin
str(a[j],s);
for k:=1 to 5-length(s) do
s:='0'+ s;
m:=ord(s[i])-48;
new(p);
p^.data:=a[j];
p^.next:=nil;
q[m]^.next:=p;
q[m]:=p;
end;
l:=0;
for j:=0 to 9 do
begin
p:=head[j];
while p^.next<>nil do
begin
l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;
end;
end;
end;
writeln('Sorted data:');
for i:= 1 to n do
write(a[i]:6);
end.

4.7各種排序演算法的比較

1.穩定性比較

插入排序、冒泡排序、二叉樹排序、二路歸並排序及其他線形排序是穩定的

選擇排序、希爾排序、快速排序、堆排序是不穩定的

2.時間復雜性比較

插入排序、冒泡排序、選擇排序的時間復雜性為O(n2)

其它非線形排序的時間復雜性為O(nlog2n)

線形排序的時間復雜性為O(n);

3.輔助空間的比較

線形排序、二路歸並排序的輔助空間為O(n),其它排序的輔助空間為O(1);

4.其它比較

插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。

反而在這種情況下，快速排序反而慢了。

當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。

若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許是用桶排序。

當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。

當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下。

宜用歸並排序。

當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。

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個記錄，並將這些歸並段全部寫到臨時緩沖區（由一個可用的磁碟充當）內了，這是第一步的排序結果。
完成第二步該怎麼做呢？這時候歸並演算法就有用處了。

3. 常見排序演算法歸納

排序演算法一般分類：

比較兩個相鄰的元素，將值大的元素交換至右端。

依次比較兩個相鄰的數，將小數放到前面，大數放到後面

即在第一趟：首先比較第1個數和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此一直繼續下去，直到比較最後兩個數，將小數放前，大數放後。然後重復第一趟步驟，直到所有排序完成。

第一趟比較完成後，最後一個數一定是數組中最大的一個數，所以第二趟比較的時候最後一個數不參與比較。

第二趟完成後，倒數第二個數也一定是數組中第二大的數，所以第三趟比較的時候最後兩個數不參與比較。

依次類推......

輸出結果：

冒泡排序的優點： 每進行一趟排序，就會少比較一次，因為每進行一趟排序都會找出一個較大值。如上例：第一趟比較之後，排在最後的一個數一定是最大的一個數，第二趟排序的時候，只需要比較除了最後一個數以外的其他的數，同樣也能找出一個最大的數排在參與第二趟比較的數後面，第三趟比較的時候，只需要比較除了最後兩個數以外的其他的數，以此類推……也就是說，沒進行一趟比較，每一趟少比較一次，一定程度上減少了演算法的量。

用時間復雜度來說：

從一個數組中隨機選出一個數N，通過一趟排序將數組分割成三個部分，1、小於N的區域 2、等於N的區域 3、大於N的區域，然後再按照此方法對小於區的和大於區分別遞歸進行，從而達到整個數據變成有序數組。

如下圖：

假設最開始的基準數據為數組的第一個元素23，則首先用一個臨時變數去存儲基準數據，即 tmp=23 ，然後分別從數組的兩端掃描數組，設兩個指示標志： low 指向起始位置， high 指向末尾。

首先從後半部分開始，如果 掃描到的值大於基準數據 就讓 high-1 ，如果發現有元素比該基準數據的值小，比如上面的 18 <= tmp ，就讓 high位置的值賦值給low位置 ，結果如下：

然後開始從前往後掃描，如果掃描到的值小於基準數據就讓 low+1 ，如果發現有元素大於基準數據的值，比如上圖 46 >= tmp ，就再將 low 位置的值賦值給 high 位置的值，指針移動並且數據交換後的結果如下：

然後再開始從前往後遍歷，直到 low=high 結束循環，此時low或者high的下標就是 基準數據23在該數組中的正確索引位置 ，如下圖所示：

這樣一遍遍的走下來，可以很清楚的知道，快排的本質就是把比基準數據小的都放到基準數的左邊，比基準數大的數都放到基準數的右邊，這樣就找到了該數據在數組中的正確位置。

然後採用遞歸的方式分別對前半部分和後半部分排序，最終結果就是自然有序的了。

輸出結果：

最好情況下快排每次能恰好均分序列，那麼時間復雜度就是O(nlogn)，最壞情況下，快排每次劃分都只能將序列分為一個元素和其它元素兩部分，這時候的快排退化成冒泡排序，時間復雜度為O(n^2)。

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。

將一個數據插入到 已經排好序的有序數據 中

第一趟排序：

用數組的第二個數與第一個數( 看成是已有序的數據 )比較

第二趟排序：

用數組的第三個數與已是有序的數據 {2,3} (剛才在第一趟排的)比較

在第二步中：

...

後面依此類推

輸出結果：

選擇排序是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

舉例：數組 int[] arr={5,2,8,4,9,1}

第一趟排序 ： 原始數據： 5 2 8 4 9 1

最小數據1，把1放在首位，也就是1和5互換位置，

排序結果： 1 2 8 4 9 5

第二趟排序 ：

第1以外的數據 {2 8 4 9 5} 進行比較，2最小，

排序結果： 1 2 8 4 9 5

第三趟排序 ：

除 1、2 以外的數據 {8 4 9 5} 進行比較，4最小，8和4交換

排序結果： 1 2 4 8 9 5

第四趟排序 :

除第 1、2、4 以外的其他數據 {8 9 5} 進行比較，5最小，8和5交換

排序結果： 1 2 4 5 9 8

第五趟排序：

除第 1、2、4、5 以外的其他數據 {9 8} 進行比較，8最小，8和9交換

排序結果： 1 2 4 5 8 9

輸出結果：

歸並排序（merge sort）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

比如我們對 [8,4,5,7,1,3,6,2] 這個數組進行歸並排序，我們首先利用分治思想的「分」將數組拆分。

輸出結果：

4. 常用的數據排序演算法有哪些,各有什麼特點舉例結合一種排序演算法並應用數組進行數據排序。

排序簡介
排序是數據處理中經常使用的一種重要運算,在計算機及其應用系統中,花費在排序上的時間在系統運行時間中佔有很大比重;並且排序本身對推動演算法分析的發展也起很大作用。目前已有上百種排序方法，但尚未有一個最理想的盡如人意的方法，本章介紹常用的如下排序方法，並對它們進行分析和比較。

1、插入排序（直接插入排序、折半插入排序、希爾排序）；
2、交換排序（起泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸並排序；
5、基數排序；

學習重點
1、掌握排序的基本概念和各種排序方法的特點，並能加以靈活應用；
2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸並排序的方法及其性能分析方法；
3、了解基數排序方法及其性能分析方法。

排序（sort）或分類

所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序對象--文件
被排序的對象--文件由一組記錄組成。
記錄則由若干個數據項(或域)組成。其中有一項可用來標識一個記錄，稱為關鍵字項。該數據項的值稱為關鍵字(Key)。
注意：
在不易產生混淆時，將關鍵字項簡稱為關鍵字。

2．排序運算的依據--關鍵字
用來作排序運算依據的關鍵字，可以是數字類型，也可以是字元類型。
關鍵字的選取應根據問題的要求而定。
【例】在高考成績統計中將每個考生作為一個記錄。每條記錄包含准考證號、姓名、各科的分數和總分數等項內容。若要惟一地標識一個考生的記錄，則必須用"准考證號"作為關鍵字。若要按照考生的總分數排名次，則需用"總分數"作為關鍵字。

排序的穩定性

當待排序記錄的關鍵字均不相同時，排序結果是惟一的，否則排序結果不唯一。
在待排序的文件中，若存在多個關鍵字相同的記錄，經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變，該排序方法是穩定的；若具有相同關鍵字的記錄之間的相對次序發生變化，則稱這種排序方法是不穩定的。
注意：
排序演算法的穩定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得演算法不滿足穩定性要求，則該排序演算法就是不穩定的。

排序方法的分類

1．按是否涉及數據的內、外存交換分
在排序過程中，若整個文件都是放在內存中處理，排序時不涉及數據的內、外存交換，則稱之為內部排序(簡稱內排序)；反之，若排序過程中要進行數據的內、外存交換，則稱之為外部排序。
注意：
① 內排序適用於記錄個數不很多的小文件
② 外排序則適用於記錄個數太多，不能一次將其全部記錄放人內存的大文件。

2．按策略劃分內部排序方法
可以分為五類：插入排序、選擇排序、交換排序、歸並排序和分配排序。

排序演算法分析

1．排序演算法的基本操作
大多數排序演算法都有兩個基本的操作：
(1) 比較兩個關鍵字的大小；
(2) 改變指向記錄的指針或移動記錄本身。
注意：
第(2)種基本操作的實現依賴於待排序記錄的存儲方式。

2．待排文件的常用存儲方式
（1） 以順序表(或直接用向量)作為存儲結構
排序過程：對記錄本身進行物理重排（即通過關鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲結構
排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈式)排序；

（3） 用順序的方式存儲待排序的記錄，但同時建立一個輔助表(如包括關鍵字和指向記錄位置的指針組成的索引表)
排序過程：只需對輔助表的表目進行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用於難於在鏈表上實現，仍需避免排序過程中移動記錄的排序方法。

3．排序演算法性能評價
（1） 評價排序演算法好壞的標准
評價排序演算法好壞的標准主要有兩條：
① 執行時間和所需的輔助空間
② 演算法本身的復雜程度

（2） 排序演算法的空間復雜度
若排序演算法所需的輔助空間並不依賴於問題的規模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。
非就地排序一般要求的輔助空間為O(n)。

（3） 排序演算法的時間開銷
大多數排序演算法的時間開銷主要是關鍵字之間的比較和記錄的移動。有的排序演算法其執行時間不僅依賴於問題的規模，還取決於輸入實例中數據的狀態。

文件的順序存儲結構表示

#define n l00 //假設的文件長度，即待排序的記錄數目
typedef int KeyType； //假設的關鍵字類型
typedef struct{ //記錄類型
KeyType key； //關鍵字項
InfoType otherinfo；//其它數據項，類型InfoType依賴於具體應用而定義
}RecType；
typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個單元一般用作哨兵
注意：
若關鍵字類型沒有比較算符，則可事先定義宏或函數來表示比較運算。
【例】關鍵字為字元串時，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那麼演算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。

按平均時間將排序分為四類：

（1）平方階(O(n2))排序
一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；

（2）線性對數階(O(nlgn))排序
如快速、堆和歸並排序；

（3）O(n1+￡)階排序
￡是介於0和1之間的常數，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序
如桶、箱和基數排序。

各種排序方法比較

簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。

影響排序效果的因素

因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法應綜合考慮下列因素：
①待排序的記錄數目n；
②記錄的大小(規模)；
③關鍵字的結構及其初始狀態；
④對穩定性的要求；
⑤語言工具的條件；
⑥存儲結構；
⑦時間和輔助空間復雜度等。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少於直接插人，應選直接選擇排序為宜。
(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應採用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；
堆排序所需的輔助空間少於快速排序，並且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸並排序。但本章介紹的從單個記錄起進行兩兩歸並的 排序演算法並不值得提倡，通常可以將它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子文件，然後再兩兩歸並之。因為直接插入排序是穩定的，所以改進後的歸並排序仍是穩定的。

4)在基於比較的排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程。
當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlgn)的時間。
箱排序和基數排序只需一步就會引起m種可能的轉移，即把一個記錄裝入m個箱子之一，因此在一般情況下，箱排序和基數排序可能在O(n)時間內完成對n個記錄的排序。但是，箱排序和基數排序只適用於像字元串和整數這類有明顯結構特徵的關鍵字，而當關鍵字的取值范圍屬於某個無窮集合(例如實數型關鍵字)時，無法使用箱排序和基數排序，這時只有藉助於"比較"的方法來排序。
若n很大，記錄的關鍵字位數較少且可以分解時，採用基數排序較好。雖然桶排序對關鍵字的結構無要求，但它也只有在關鍵字是隨機分布時才能使平均時間達到線性階，否則為平方階。同時要注意，箱、桶、基數這三種分配排序均假定了關鍵字若為數字時，則其值均是非負的，否則將其映射到箱(桶)號時，又要增加相應的時間。
(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導致實現歸並、快速(它們用遞歸實現較簡單)和基數(使用了指針)等排序演算法變得復雜。此時可考慮用其它排序。
(6)本章給出的排序演算法，輸人數據均是存儲在一個向量中。當記錄的規模較大時，為避免耗費大量的時間去移動記錄，可以用鏈表作為存儲結構。譬如插入排序、歸並排序、基數排序都易於在鏈表上實現，使之減少記錄的移動次數。但有的排序方法，如快速排序和堆排序，在鏈表上卻難於實現，在這種情況下，可以提取關鍵字建立索引表，然後對索引表進行排序。然而更為簡單的方法是：引人一個整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序演算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結束後，向量t就指示了記錄之間的順序關系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最終結果是：
R[0].key≤R[1].key≤…≤R[n-1].key
則可以在排序結束後，再按輔助表所規定的次序重排各記錄，完成這種重排的時間是O(n)。

5. 各種排序演算法的總結和比較

排序演算法是《數據結構與演算法》中最基本的演算法之一。

排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。用一張圖概括：

點擊以下圖片查看大圖：

關於時間復雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸並排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序演算法：冒泡排序、插入排序、歸並排序和基數排序。

不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模 k："桶"的個數 In-place：佔用常數內存，不佔用額外內存 Out-place：佔用額外內存 穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同

包含以下內容：

1、冒泡排序 2、選擇排序 3、插入排序 4、希爾排序 5、歸並排序 6、快速排序 7、堆排序 8、計數排序 9、桶排序 10、基數排序

排序演算法包含的相關內容具體如下：

冒泡排序演算法

冒泡排序（Bubble Sort）也是一種簡單直觀的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。

選擇排序演算法

選擇排序是一種簡單直觀的排序演算法，無論什麼數據進去都是 O(n?) 的時間復雜度。所以用到它的時候，數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間。

插入排序演算法

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

希爾排序演算法

希爾排序，也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序演算法。

歸並排序演算法

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

堆排序演算法

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

計數排序演算法

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

桶排序演算法

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。

基數排序演算法

基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。

6. 幾種排序演算法的比較

一、八大排序演算法的總體比較

4.3、堆的插入：

每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中

（1）用大根堆排序的基本思想

先將初始數組建成一個大根堆，此對為初始的無序區；

再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；

由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；

..........

直到無序區只有一個元素為止；

4.4：應用

尋找M個數中的前K個最小的數並保持有序；

時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]

5.希爾排序

（1）基本思想

先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；

（2）適用場景

比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；

6.歸並排序

（1）基本思想

首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；

（2）適用場景

若n較大，並且要求排序穩定，則可以選擇歸並排序；

7.簡單選擇排序

（1）基本思想

第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；

第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；

...........

第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；

以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；