希望會對妳有幫助
相關知識介紹(所有定義只為幫助讀者理解相關概念，並非嚴格定義):
1、穩定排序和非穩定排序
簡單地說就是所有相等的數經過某種排序方法後，仍能保持它們在排序之前的相對次序，我們就
說這種排序方法是穩定的。反之，就是非穩定的。
比如:壹組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序後為a1,a2,a4,a3,a5，
則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序後它還是在a4的前面。假如變成a1,a4,
a2,a3,a5就不是穩定的了。
2、內排序和外排序
在排序過程中，所有需要排序的數都在內存，並在內存中調整它們的存儲順序，稱為內排序;
在排序過程中，只有部分數被調入內存，並借助內存調整數在外存中的存放順序排序方法稱為外排序。
3、算法的時間復雜度和空間復雜度
所謂算法的時間復雜度，是指執行算法所需要的計算工作量。
壹個算法的空間復雜度，壹般是指執行這個算法所需要的內存空間。
================================================================================
*/
/*
================================================
功能:選擇排序
輸入:數組名稱(也就是數組首地址)、數組中元素個數
================================================
*/
/*
====================================================
算法思想簡單描述:
在要排序的壹組數中，選出最小的壹個數與第壹個位置的數交換;
然後在剩下的數當中再找最小的與第二個位置的數交換，如此循環
到倒數第二個數和最後壹個數比較為止。
選擇排序是不穩定的。算法復雜度O(n2)--[n的平方]
=====================================================
*/
void
select_sort(int
*x,
int
n)
{
int
i,
j,
min,
t;
for
(i=0;
i<n-1;
i++)
/*要選擇的次數:0~n-2***n-1次*/
{
min
=
i;
/*假設當前下標為i的數最小，比較後再調整*/
for
(j=i+1;
j<n;
j++)/*循環找出最小的數的下標是哪個*/
{
if
(*(x+j)
<
*(x+min))
{
min
=
j;
/*如果後面的數比前面的小，則記下它的下標*/
}
}
if
(min
!=
i)
/*如果min在循環中改變了，就需要交換數據*/
{
t
=
*(x+i);
*(x+i)
=
*(x+min);
*(x+min)
=
t;
}
}
}
/*
================================================
功能:直接插入排序
輸入:數組名稱(也就是數組首地址)、數組中元素個數
================================================
*/
/*
====================================================
算法思想簡單描述:
在要排序的壹組數中，假設前面(n-1)
[n>=2]
個數已經是排
好順序的，現在要把第n個數插到前面的有序數中，使得這n個數
也是排好順序的。如此反復循環，直到全部排好順序。
直接插入排序是穩定的。算法時間復雜度O(n2)--[n的平方]
=====================================================
*/
void
insert_sort(int
*x,
int
n)
{
int
i,
j,
t;
for
(i=1;
i<n;
i++)
/*要選擇的次數:1~n-1***n-1次*/
{
/*
暫存下標為i的數。註意:下標從1開始，原因就是開始時
第壹個數即下標為0的數，前面沒有任何數，單單壹個，認為
它是排好順序的。
*/
t=*(x+i);
for
(j=i-1;
j>=0
&&
t<*(x+j);
j--)
/*註意:j=i-1，j--，這裏就是下標為i的數，在它前面有序列中找插入位置。*/
{
*(x+j+1)
=
*(x+j);
/*如果滿足條件就往後挪。最壞的情況就是t比下標為0的數都小，它要放在最前面，j==-1，退出循環*/
}
*(x+j+1)
=
t;
/*找到下標為i的數的放置位置*/
}
}
/*
================================================
功能:冒泡排序
輸入:數組名稱(也就是數組首地址)、數組中元素個數
================================================
*/
/*
====================================================
算法思想簡單描述:
在要排序的壹組數中，對當前還未排好序的範圍內的全部數，自上
而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沈，較
小的往上冒。即:每當兩相鄰的數比較後發現它們的排序與排序要
求相反時，就將它們互換。
下面是壹種改進的冒泡算法，它記錄了每壹遍掃描後最後下沈數的
位置k，這樣可以減少外層循環掃描的次數。
冒泡排序是穩定的。算法時間復雜度O(n2)--[n的平方]
=====================================================
*/
void
bubble_sort(int
*x,
int
n)
{
int
j,
k,
h,
t;
for
(h=n-1;
h>0;
h=k)
/*循環到沒有比較範圍*/
{
for
(j=0,
k=0;
j<h;
j++)
/*每次預置k=0，循環掃描後更新k*/
{
if
(*(x+j)
>
*(x+j+1))
/*大的放在後面，小的放到前面*/
{
t
=
*(x+j);
*(x+j)
=
*(x+j+1);
*(x+j+1)
=
t;
/*完成交換*/
k
=
j;
/*保存最後下沈的位置。這樣k後面的都是排序排好了的。*/
}
}
}
}
/*
================================================
功能:希爾排序
輸入:數組名稱(也就是數組首地址)、數組中元素個數
================================================
*/
/*
====================================================
算法思想簡單描述:
在直接插入排序算法中，每次插入壹個數，使有序序列只增加1個節點，
並且對插入下壹個數沒有提供任何幫助。如果比較相隔較遠距離(稱為
增量)的數，使得數移動時能跨過多個元素，則進行壹次比較就可能消除
多個元素交換。D.L.shell於1959年在以他名字命名的排序算法中實現
了這壹思想。算法先將要排序的壹組數按某個增量d分成若幹組，每組中
記錄的下標相差d.對每組中全部元素進行排序，然後再用壹個較小的增量
對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成
壹組，排序完成。
下面的函數是壹個希爾排序算法的壹個實現，初次取序列的壹半為增量，
以後每次減半，直到增量為1。
希爾排序是不穩定的。
=====================================================
*/
void
shell_sort(int
*x,
int
n)
{
int
h,
j,
k,
t;
for
(h=n/2;
h>0;
h=h/2)
/*控制增量*/
{
for
(j=h;
j<n;
j++)
/*這個實際上就是上面的直接插入排序*/
{
t
=
*(x+j);
for
(k=j-h;
(k>=0
&&
t<*(x+k));
k-=h)
{
*(x+k+h)
=
*(x+k);
}
*(x+k+h)
=
t;
}
}
}
/*
================================================
功能:快速排序
輸入:數組名稱(也就是數組首地址)、待排序元素起點、終點
================================================
*/
====================================================
算法思想簡單描述:
快速排序是對冒泡排序的壹種改進。它的基本思想是:通過壹躺排序將要排序的數據分割成獨立的兩部分，其中壹部分的所有數據都比另外壹不部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
假設要排序的數組是A[1]……A[N]，首先任意選取壹個數據(通常選用第壹個數據)作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為壹躺快速排序。壹躺快速排序的算法是:
1)、設置兩個變量I、J，排序開始的時候I:=1，J:=N;
2)以第壹個數組元素作為關鍵數據，賦值給X，即X:=A[1];
3)、從J開始向前搜索，即由後開始向前搜索(J:=J-1)，找到第壹個小於X的值，兩者交換;
4)、從I開始向後搜索，即由前開始向後搜索(I:=I+1)，找到第壹個大於X的值，兩者交換;
5)、重復第3、4步，直到I=J;
快速排序是不穩定的。
===================================================
void
quick_sort(int
*x,
int
low,
int
high)
{
int
i,
j,
t;
if
(low
<
high)
/*要排序的元素起止下標，保證小的放在左邊，大的放在右邊。這裏以下標為low的元素為基準點*/
{
i
=
low;
j
=
high;
t
=
*(x+low);
/*暫存基準點的數*/
while
(i<j)
/*循環掃描*/
{
while
(i<j
&&
*(x+j)>t)
/*在右邊的只要比基準點大仍放在右邊*/
{
j--;
/*前移壹個位置*/
}
if
(i<j)
{
*(x+i)
=
*(x+j);
/*上面的循環退出:即出現比基準點小的數，替換基準點的數*/
i++;
/*後移壹個位置*/
}
while
(i<j
&&
*(x+i)<=t)
/*在左邊的只要小於等於基準點仍放在左邊*/
{
i++;
/*後移壹個位置*/
}
if
(i<j)
{
*(x+j)
=
*(x+i);
/*上面的循環退出:即出現比基準點大的數，放到右邊*/
j--;
/*前移壹個位置*/
}
}
*(x+i)
=
t;
/*壹遍掃描完後，放到適當位置*/
quick_sort(x,low,i-1);
/*對基準點左邊的數再執行快速排序*/
quick_sort(x,i+1,high);
/*對基準點右邊的數再執行快速排序*/
}
}