排序與排序算法
時間：2018-09-26 來(lai)源：未知
一、排序(xu)的(de)基本概念(nian)與(yu)分類
1、排(pai)序的定義
假設含(han)有n個記錄的序(xu)列為(wei)(wei){r1,r2,……rn}，其相對(dui)應(ying)的關鍵字分別為(wei)(wei){k1,k2,……kn}，需確(que)定(ding)一(yi)種序(xu)列，使其關鍵字滿足k1<=k2<=……<=km(非(fei)遞(di)減)或k1>=k2>=……>=km(非(fei)遞(di)增(zeng))關系(xi)，即使得序(xu)列成(cheng)為(wei)(wei)一(yi)個按關鍵字有序(xu)的序(xu)列{r1,r2,……,rm}，這樣的操作就(jiu)稱為(wei)(wei)排序(xu)。
排(pai)序(xu)的(de)依據(ju)是關鍵(jian)字之間的(de)大小關系(xi)，那么，對(dui)于(yu)同(tong)一(yi)個記錄集合，針對(dui)不同(tong)的(de)關鍵(jian)字進行排(pai)序(xu)，可以得到(dao)不同(tong)的(de)序(xu)列。
2、排序的穩定(ding)性(xing)。
假設在排序前，有ki=kj(1<=i<=n，1<=j<=n，i不等于j)，且在排序前的序列中ri位置于rj(即i
例如有序列：
編(bian)號 姓(xing)名(ming) 總分
1 Li 750
2 Liu 730
3 Zhou 738
4 Han 750
此時我們按總分排(pai)序，如果得到
1 Li 750
4 Han 750
2 Zhou 738
3 Liu 730
這樣(yang)排(pai)序算法(fa)就是穩(wen)定的。而(er)如果得到
4 Han 750
1 Li 750
2 Zhou 738
3 Liu 730
則這樣的排序(xu)算法(fa)就是不穩定的。
對于多個關鍵(jian)字(zi)排序時，如果有一組關鍵(jian)字(zi)會得到不(bu)穩(wen)定(ding)的結(jie)果，則(ze)我(wo)們就認為此排序算法是不(bu)穩(wen)定(ding)的。
3、排序算法(fa)的分類
1)按數據(ju)位(wei)置(zhi)分類
根據排(pai)序(xu)(xu)過程中(zhong)待排(pai)數據是否全(quan)部(bu)被放置在內存中(zhong)，排(pai)序(xu)(xu)分為(wei)：內排(pai)序(xu)(xu)和外(wai)排(pai)序(xu)(xu)
內排(pai)序：排(pai)序過(guo)程中，待(dai)排(pai)數(shu)據全(quan)部被放置在內存中。
外(wai)排(pai)(pai)(pai)序：排(pai)(pai)(pai)序過程中，因記錄太多，不能同時放在內存中，整個排(pai)(pai)(pai)序過程中需要(yao)在內外(wai)存之間多次交換數據(ju)才能進行。
我們這里只討論內排(pai)序算法。對于(yu)內排(pai)序來說(shuo)，排(pai)序算法的性能主要受3個方面影響：
⒈時間性能
排(pai)(pai)序是數(shu)(shu)據處理時(shi)經(jing)常執行的操(cao)作，往(wang)往(wang)屬于核心代碼部分，因此排(pai)(pai)序算(suan)法(fa)的時(shi)間開銷是衡量其好壞的重(zhong)要標志。在排(pai)(pai)序中，主要涉及到兩(liang)種操(cao)作：比較與(yu)移動(dong)。高效率的排(pai)(pai)序算(suan)法(fa)應該是具有盡(jin)可(ke)能少的關鍵字比較次數(shu)(shu)和盡(jin)可(ke)能少的數(shu)(shu)據移動(dong)次數(shu)(shu)。
⒉輔助空間
評(ping)價(jia)排序算法的另一個(ge)主要標準(zhun)是(shi)執(zhi)行(xing)算法所(suo)需(xu)(xu)要的輔(fu)助空間。輔(fu)助存(cun)儲空間是(shi)除了存(cun)放待排序所(suo)占用(yong)的存(cun)儲空間之外(wai)，執(zhi)行(xing)算法所(suo)需(xu)(xu)要的額外(wai)存(cun)儲空間。
⒊算(suan)法(fa)的復雜(za)性
過于復雜的算法會影響其排序(xu)性能。
2)按排(pai)序操作分類
根(gen)據排(pai)序(xu)過程(cheng)中(zhong)借助的操(cao)作(zuo)，我們把排(pai)序(xu)分(fen)為(wei)：插入排(pai)序(xu)、交換排(pai)序(xu)、選擇(ze)排(pai)序(xu)和歸并排(pai)序(xu)。
3)按算(suan)法的復雜(za)性分類
根據排(pai)序算(suan)法(fa)的復雜性分(fen)類(lei)，可分(fen)為簡單(dan)排(pai)序算(suan)法(fa)和改進排(pai)序算(suan)法(fa)。
簡(jian)單排(pai)序(xu)(xu)(xu)算法：冒泡排(pai)序(xu)(xu)(xu)、直(zhi)接選擇排(pai)序(xu)(xu)(xu)、直(zhi)接插(cha)入排(pai)序(xu)(xu)(xu)
改進排(pai)序算法：Shell排(pai)序、堆排(pai)序、歸并排(pai)序、快速排(pai)序
//注(zhu)：下文中涉及到的代碼(ma)詳見(jian)附錄
二、冒(mao)泡排序
無論學習(xi)哪種(zhong)(zhong)編(bian)程語言，當學習(xi)到循環與數組(zu)等概念(nian)的時候，通常會介紹一種(zhong)(zhong)排序(xu)算法來(lai)作為(wei)例子或練習(xi)。而這種(zhong)(zhong)排序(xu)算法通常都是冒泡排序(xu)。
1、簡單的冒泡(pao)排序
冒泡排(pai)序(xu)(Bubble Sort)是一種交(jiao)(jiao)換(huan)(huan)排(pai)序(xu)，它(ta)的(de)基(ji)本思想(xiang)是：兩兩比(bi)較相鄰(lin)記(ji)錄的(de)關鍵字，如(ru)果反序(xu)則交(jiao)(jiao)換(huan)(huan)，直到沒有反序(xu)為止。
在排(pai)序過程中，較小的數字(或較大的數字)會如(ru)同(tong)水下的氣(qi)泡一樣慢慢浮(fu)出水面(mian)，冒泡排(pai)序的命名就此而來(lai)。
//代碼見附錄
2、冒泡排序優(you)化1
冒(mao)泡排序是否(fou)可以進(jin)行優化呢(ni)?答(da)案是肯定的。
試想(xiang)，如(ru)(ru)果(guo)待(dai)排序(xu)(xu)數據是(shi)基本(ben)有序(xu)(xu)的(例如(ru)(ru)2,1,3,4,5,6,7,8,9,10，除了第一和第二個關鍵字不同(tong)，需(xu)要交(jiao)換(huan)(huan)外(wai)，其(qi)他數據關鍵字都(dou)已(yi)經有序(xu)(xu)。此時(shi)我(wo)們只需(xu)交(jiao)換(huan)(huan)這(zhe)兩個數字即可(ke)，而(er)無需(xu)將冒(mao)泡排序(xu)(xu)執行到(dao)底。
我(wo)(wo)們(men)(men)可以(yi)設置一個標(biao)志位(wei)flag，用它(ta)來指(zhi)示(shi)一次冒(mao)泡排(pai)序執行后是否有數據交換(huan)。如果(guo)一次排(pai)序后沒有數據交換(huan)，我(wo)(wo)們(men)(men)就可以(yi)認為數據已經有序，無需(xu)再(zai)繼續執行后面(mian)的(de)工作了。
//代碼見附錄
代碼改(gai)動的關鍵(jian)就是(shi)在外(wai)層循環(huan)for()的結束條(tiao)件中，增加了對flag是(shi)否是(shi)true的判斷(duan)。這(zhe)樣的改(gai)進能避免數據在有序的情況下(xia)做無意義(yi)的循環(huan)判斷(duan)，從而提升效率。
3、冒泡排序優化2
從另一(yi)(yi)(yi)個(ge)角度來想，一(yi)(yi)(yi)次循環數據從前掃(sao)描(miao)(miao)到(dao)后(hou)，然后(hou)再(zai)從前掃(sao)描(miao)(miao)到(dao)后(hou)……也就是(shi)說，“磁(ci)頭(tou)”掃(sao)描(miao)(miao)一(yi)(yi)(yi)個(ge)來回(hui)移動(dong)一(yi)(yi)(yi)個(ge)關(guan)鍵字使其(qi)有(you)序。如果我們能(neng)在“磁(ci)頭(tou)”移動(dong)回(hui)表(biao)頭(tou)時，也能(neng)移動(dong)一(yi)(yi)(yi)個(ge)關(guan)鍵字，那么(me)就相當于(yu)一(yi)(yi)(yi)次掃(sao)描(miao)(miao)一(yi)(yi)(yi)個(ge)來回(hui)移動(dong)兩個(ge)關(guan)鍵字，可(ke)以提升(sheng)其(qi)執(zhi)行效率。
//代(dai)碼見附錄
三(san)、直接選擇排序
冒泡排(pai)序(xu)(xu)是基(ji)于比較和交換的排(pai)序(xu)(xu)，其算(suan)法思(si)想就是不斷交換，通過交換完(wan)成終排(pai)序(xu)(xu)。而直接選擇排(pai)序(xu)(xu)則是基(ji)于選擇的排(pai)序(xu)(xu)，其算(suan)法思(si)想是每次選出待排(pai)數據的關鍵字中大(或小)的數據作為第i個記錄。
1、直接選擇排序算法
選擇排序算法(Selection Sort)就是通過n-i次關鍵(jian)字(zi)比較，從n-i+1個(ge)數(shu)(shu)據中每次挑選出關鍵(jian)字(zi)小(或大)的數(shu)(shu)據并和第i(1<=i<=n)個(ge)數(shu)(shu)據交(jiao)換之(zhi)。
//代碼見附(fu)錄
注意代碼中的min是這次排序過(guo)程中小(xiao)數據(ju)的下標(biao)。
從(cong)性能上來說，選擇排序略優(you)于冒泡排序。
四、直接插(cha)入(ru)排序(xu)
撲克牌(pai)是我們(men)(men)都玩過的游戲。那么(me)摸到手的撲克牌(pai)如何理牌(pai)呢?一般情況下(xia)，都是選出(chu)一張(zhang)牌(pai)，將它(ta)放置在(zai)比它(ta)大和比它(ta)小的兩張(zhang)牌(pai)之間(jian)。這里我們(men)(men)用于理牌(pai)的方法就(jiu)是直(zhi)接插入排序。
1、直接插入排序算法
直(zhi)接(jie)插(cha)入(ru)排序(xu)算法(Straight Insertion Sort)的基(ji)本操作是(shi)將一(yi)(yi)個數據插(cha)入(ru)到一(yi)(yi)個已經排好序(xu)的有(you)序(xu)表(biao)(biao)中，從而得到一(yi)(yi)個新的有(you)序(xu)表(biao)(biao)。重復這(zhe)個過程，直(zhi)至所有(you)數據有(you)序(xu)。
//代(dai)碼見附錄
需要(yao)注意的是(shi)，直接插(cha)入排(pai)(pai)序需要(yao)一個(ge)已經有序的序列(lie)作(zuo)為“基準”。代碼中(zhong)，選區r[0]與r[1]作(zuo)為基準，在排(pai)(pai)序前，需要(yao)判斷r[0]與r[1]的關系保證其(qi)是(shi)有序表。可以嘗試省略掉(diao)這(zhe)一步，觀察排(pai)(pai)序后的內容。
從性能上來說，直接插入(ru)排序略(lve)優于冒(mao)泡排序。
五、快速排序
上(shang)文中介紹的的冒泡排(pai)序(xu)(xu)、選(xuan)擇排(pai)序(xu)(xu)、直(zhi)接插入排(pai)序(xu)(xu)及(ji)其改進版本(ben)，都屬于簡單排(pai)序(xu)(xu)算法。因為(wei)它們的時間復(fu)雜度都為(wei)O(n^2)。而(er)改進排(pai)序(xu)(xu)算法(Shell排(pai)序(xu)(xu)、堆排(pai)序(xu)(xu)、歸并排(pai)序(xu)(xu)、快速(su)(su)排(pai)序(xu)(xu))的時間復(fu)雜度都為(wei)O(nlog2n)甚至更快。在這里我們主要學習快速(su)(su)排(pai)序(xu)(xu)。
1、快速(su)排(pai)序(xu)算法
快(kuai)速排序算法(fa)早由(you)圖靈(ling)獎獲得者Tony Hoare于1962年設計出來(lai)，被稱為“20世(shi)紀十大算法(fa)”之一。
快速排序(xu)(xu)相當(dang)于(yu)(yu)冒泡排序(xu)(xu)的升級，二(er)者都(dou)屬(shu)于(yu)(yu)交換排序(xu)(xu)類(lei)。
快速排序(Quick Sort)的(de)基本思想是：通過一(yi)趟排序將待排數(shu)據分(fen)(fen)割成(cheng)獨立的(de)兩部(bu)分(fen)(fen)，其中一(yi)部(bu)分(fen)(fen)的(de)關(guan)鍵字都比另一(yi)部(bu)分(fen)(fen)的(de)關(guan)鍵字小。之后(hou)對這(zhe)兩部(bu)分(fen)(fen)分(fen)(fen)別(bie)進行排序，終達到整體有序。
快速排序算法(fa)的文字描(miao)述是：
1)設置兩個變量i、j，排序開始的時候：i=0，j=N-1;
2)以(yi)第一個(ge)數組(zu)元素作為關鍵數據，賦(fu)值給key，即key=A[0];
3)從j開始向前搜(sou)索(suo)，即(ji)由后開始向前搜(sou)索(suo)(j--)，找(zhao)到第一個小(xiao)于(yu)key的(de)值A[j]，將(jiang)A[j]和A[i]互換;
4)從i開(kai)始向后搜索，即(ji)由前(qian)開(kai)始向后搜索(i++)，找(zhao)到第一個(ge)大于key的A[i]，將A[i]和A[j]互(hu)換;
5)重(zhong)復第3、4步，直到i=j;此時令(ling)循環結束。將key值賦值到i(或j)的位(wei)置。
6)遞歸操作數組A[]在key值左的左半部分。
7)遞歸操作(zuo)數組(zu)A[]在key值右的(de)右半部分。
//代碼見附錄
2、快速(su)排序算法的優缺點
快(kuai)速排(pai)序(xu)算(suan)法(fa)之(zhi)所以叫(jiao)“快(kuai)速”排(pai)序(xu)，意味著目前階(jie)段沒有人找到更(geng)優秀于這個算(suan)法(fa)的(de)排(pai)序(xu)算(suan)法(fa)。如果某一天有人找到了更(geng)好的(de)排(pai)序(xu)算(suan)法(fa)，“快(kuai)速”就會名不副實，不過(guo)，至今為止，Tony Hoare發明的(de)排(pai)序(xu)算(suan)法(fa)經過(guo)多(duo)次優化后，在整(zheng)體性能(neng)上，依然是排(pai)序(xu)算(suan)法(fa)中(zhong)的(de)王(wang)者(zhe)。
不過快(kuai)速(su)排(pai)(pai)(pai)序(xu)(xu)算(suan)法仍有(you)缺(que)陷，快(kuai)速(su)排(pai)(pai)(pai)序(xu)(xu)算(suan)法雖然對大數(shu)(shu)據排(pai)(pai)(pai)序(xu)(xu)十分(fen)擅長，但不擅長數(shu)(shu)據不多(duo)時(shi)進行排(pai)(pai)(pai)序(xu)(xu)。在數(shu)(shu)據不多(duo)時(shi)，快(kuai)速(su)排(pai)(pai)(pai)序(xu)(xu)與冒泡排(pai)(pai)(pai)序(xu)(xu)幾乎看(kan)不出(chu)時(shi)間上(shang)的優(you)勢(shi)，只有(you)數(shu)(shu)據足夠大時(shi)，快(kuai)速(su)排(pai)(pai)(pai)序(xu)(xu)才能發揮(hui)出(chu)它的優(you)勢(shi)。因此我們在對數(shu)(shu)據進行排(pai)(pai)(pai)序(xu)(xu)時(shi)，若數(shu)(shu)據量(liang)不太多(duo)，可以選(xuan)擇(ze)使用三種簡(jian)單排(pai)(pai)(pai)序(xu)(xu)算(suan)法(冒泡排(pai)(pai)(pai)序(xu)(xu)、選(xuan)擇(ze)排(pai)(pai)(pai)序(xu)(xu)、直接插入排(pai)(pai)(pai)序(xu)(xu));若數(shu)(shu)據量(liang)巨大，我們就需要選(xuan)擇(ze)快(kuai)速(su)排(pai)(pai)(pai)序(xu)(xu)。
附錄1：各排序算法代碼實現(C語(yu)言)
#include
#include
#define MAXSIZE 10
typedef struct
{
int r[MAXSIZE];//存儲(chu)待排序數據
int length;//記錄順序表的長度
}Sqlist;
void swap(Sqlist *L,int i,int j)//交(jiao)換數據函數
{
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
void print(Sqlist *L)//打印(yin)數據函數
{
int i;
for(i=0;i
printf("%d ",L->r[i]);
printf("\n");
}
void BubbleSort(Sqlist *L)//冒泡排序
{
int i,j;
for(i=0;i
{
for(j=L->length-1;j>=i;j--)
{
if(L->r[j]>L->r[j+1])
swap(L,j,j+1);
}
}
}
void BubbleSort2(Sqlist *L)//冒(mao)泡排序改進版1：增加標志位
{
int i,j;
int flag = 1;
for(i=0;i
{
flag = 0;
for(j=L->length-1;j>=i;j--)
{
if(L->r[j]>L->r[j+1])
{
swap(L,j,j+1);
flag = 1;
}
}
}
}
void BubbleSort3(Sqlist *L)//冒泡排(pai)序(xu)改(gai)進版(ban)2：雙向移動數據(雞(ji)尾酒(jiu)排(pai)序(xu))
{
int i,j;
for(i=0;i
{
for(j=i;j
{
if(L->r[j]>L->r[j+1])
swap(L,j,j+1);
}
for(j=L->length-1-(i+1);j>i;j--)
{
if(L->r[j]
swap(L,j-1,j);
}
}
}
void SelectSort(Sqlist *L)//直(zhi)接選擇排序
{
int i,j,min;//min是當(dang)次循環的小值的下標(biao)
for(i=0;i
{
min=i;
for(j=i+1;j<=L->length;j++)
{
if(L->r[min]>L->r[j])
min=j;
}
if(i!=min)
swap(L,i,min);
}
}
void InsertSort(Sqlist *L)//直接插入排(pai)序
{
int i,j,tmp;
if(L->r[0]>L->r[1])//首(shou)先保(bao)證前2個(ge)元素有序(xu)，這樣后續元素才(cai)能插(cha)入
swap(L,0,1);
for(i=2;i<=L->length;i++)//插入L->r[i]元(yuan)素
{
if(L->r[i]
{
tmp=L->r[i];
for(j=i-1;L->r[j]>tmp;j--)//將所有大(da)于L->r[i]元素都(dou)后(hou)移，空出位置
L->r[j+1]=L->r[j];
L->r[j+1]=tmp;//插入(ru)正確位置
}
}
}
void QSort1(Sqlist *L,int left,int right)//快速排序
{
int i=left,j=right;
if(left>=right)
return;
int key = L->r[left];
while(i
{
while(L->r[j]>=key && i
j--;
L->r[i]=L->r[j];
while(L->r[i]<=key && i
i++;
L->r[j]=L->r[i];
}
L->r[i]=key;
QSort1(L,left,i-1);
QSort1(L,i+1,right);
}
/*快速排(pai)序算法(fa)第二種寫(xie)法(fa)*/
int Partition(Sqlist *L,int low,int high)
{
int pivotkey,tmp;
pivotkey=L->r[low];
tmp=pivotkey;
while(low
{
while(low
high--;
L->r[low]=L->r[high];
while(low
low++;
L->r[high]=L->r[low];
}
L->r[low]=tmp;
return low;
}
void QSort2(Sqlist *L,int low,int high)
{
int pivot;
if(low
{
pivot = Partition(L,low,high);
QSort2(L,low,pivot-1);
QSort2(L,pivot+1,high);
}
}
/*快速(su)排序(xu)算法第二種寫法end*/
int main()
{
Sqlist data;
data.r[0]=9;data.r[1]=1;data.r[2]=5;data.r[3]=8;data.r[4]=3;data.r[5]=7;data.r[6]=4;data.r[7]=6;data.r[8]=2;data.r[9]=10;
data.length=sizeof(data.r)/sizeof(data.r[0]);
//BubbleSort(&data);
//BubbleSort2(&data);
//BubbleSort3(&data);
//SelectSort(&data);
//InsertSort(&data);
//QSort1(&data,0,data.length-1);
//QSort2(&data,0,data.length-1);
print(&data);
return 0;
}
附錄2：各排序算法(fa)時間復(fu)雜度與空間復(fu)雜度對(dui)比
