冒泡排序(Bubble Sort)??種交換排序,它的基本思想就是:?兩兩?較相鄰的記錄的關(guān)鍵字,如果反序則交換,直到?jīng)]有反序的記錄為?
兩兩比較，往上移動 -> 第二層遍歷是從 尾部開始的
遍歷中， 沒有任何數(shù)據(jù)的交換動作 -> 數(shù)據(jù)是有序的
void BubbleSort(SqList *L){
? ? int?i,j;
? ? //flag用作標(biāo)記
? ? Status flag =TRUE;
? ? //I 從[1,L->length) 遍歷;
? ? //如果flag為False退出循環(huán). 表示已經(jīng)出現(xiàn)過一次j從L->Length-1 到 i的過程,都沒有交換的狀態(tài);
? ? for(i =1; i < L->length&& flag; i++) {
? ? ? ? //flag 每次都初始化為FALSE
? ? ? ? flag =FALSE;
? ? ? ? for(j = L->length-1; j>=i; j--) {
? ? ? ? ? ? if(L->r[j] > L->r[j+1]){
? ? ? ? ? ? //交換L->r[j]和L->r[j+1]值;
? ? ? ? ? ? swap(L, j, j+1);
? ? ? ? ? ? //如果有任何數(shù)據(jù)的交換動作,則將flag改為true;
? ? ? ? ? ? flag =?TRUE;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if?(!flag)?break;
? ? }
}
直接插?排序算法(Stight Inserton Sort)的基本操作是將?個記錄插?到已經(jīng)排好序的有序表中,從?得到?個新的,記錄數(shù)增1的有序表
從第二個元素開始，往已經(jīng)排好序的數(shù)據(jù)中插入
void InsertSort(SqList *L){
? ? int?i,j;
? ? int?temp=0;
? ? //假設(shè)排序的序列集是{0,5,4,3,6,2};
? ? //i從2開始的意思是我們假設(shè)5已經(jīng)放好了. 后面的牌(4,3,6,2)是插入到它的左側(cè)或者右側(cè)
? ? for(i=2;i<=L->length;i++)
? ? {
? ? ? ? //需將L->r[i]插入有序子表
? ? ? ? if(L->r[i]r[i-1])
? ? ? ? {
? ? ? ? ? ? //設(shè)置哨兵 可以把temp改為L->r[0]
? ? ? ? ? ? temp = L->r[i];
? ? ? ? ? ? for(j=i-1;L->r[j]>temp;j--)
? ? ? ? ? ? ? ? ? ? //記錄后移
? ? ? ? ? ? ? ? ? ? L->r[j+1]=L->r[j];
? ? ? ? ? ? //插入到正確位置 可以把temp改為L->r[0]
? ? ? ? ? ? L->r[j+1]=temp;
? ? ? ? }
? ? }
}
簡單排序算法(Simple Selecton Sort)?就是通過n-i次關(guān)鍵詞?較,從n-i+1個記錄中找出關(guān)鍵
字最?的記錄,并和第i(1<=i<=n)?個記錄進(jìn)?交換
找出最小值，放在第一位，依此類推...
void SelectSort(SqList *L){
? ? int?i,j,min;
? ? for(i =1; i < L->length; i++) {
? ? ? ? //① 將當(dāng)前下標(biāo)假設(shè)為最小值的下標(biāo)
? ? ? ? min = i;
? ? ? ? //② 循環(huán)比較i之后的所有數(shù)據(jù)
? ? ? ? for(j = i+1; j <= L->length; j++) {
? ? ? ? ? ? //③ 如果有小于當(dāng)前最小值的關(guān)鍵字,將此關(guān)鍵字的下標(biāo)賦值給min
? ? ? ? ? ? if(L->r[min] > L->r[j]) {
? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //④ 如果min不等于i,說明找到了最小值,則交換2個位置下的關(guān)鍵字
? ? ? ? if(i!=min)
? ? ? ? ? ? swap(L, i, min);
? ? }
}
堆排序
堆結(jié)構(gòu)：堆是一個的完全?叉樹。具備完全?叉樹的特點(diǎn)，左結(jié)點(diǎn)，右結(jié)點(diǎn)，父節(jié)點(diǎn)，樹結(jié)點(diǎn)個數(shù)的 特點(diǎn)
?每個結(jié)點(diǎn)的值都?于或等于其左右孩?結(jié)點(diǎn)的值,稱為?頂堆
每個結(jié)點(diǎn)的值都小于或等于其左右孩?結(jié)點(diǎn)的值,稱為小頂堆
堆排序思路：
1. 將數(shù)據(jù)按照層序遍歷形成一個完全二叉樹， 按照?頂堆或?頂堆需求，對完全二叉樹進(jìn)行調(diào)整，調(diào)整的是非葉子結(jié)點(diǎn)
2. 將堆頂元素與末尾元素交換，將最?元素”沉"到數(shù)組末端;?
3. 重新調(diào)整結(jié)構(gòu)，使其滿?堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)?調(diào)整+交換步驟，直到整個序列有序
大頂堆調(diào)整函數(shù)
?條件: 在L.r[s...m] 記錄中除了下標(biāo)s對應(yīng)的關(guān)鍵字L.r[s]不符合大頂堆定義,其他均滿足;
?結(jié)果: 調(diào)整L.r[s]的關(guān)鍵字,使得L->r[s...m]這個范圍內(nèi)符合大頂堆定義.
void?HeapAjust(SqList *L,int?s,int?m){
? ? int?temp,j;
? ? //① 將L->r[s] 存儲到temp ,方便后面的交換過程;
? ? temp = L->r[s];
? ? //② j 為什么從2*s 開始進(jìn)行循環(huán),以及它的遞增條件為什么是j*2
? ? //因?yàn)檫@是顆完全二叉樹,而s也是非葉子根結(jié)點(diǎn). 所以它的左孩子一定是2*s,而右孩子則是2s+1;(二叉樹性質(zhì)5)
? ? for(j =2* s; j <=m; j*=2) {
? ? ? ? //③ 判斷j是否是最后一個結(jié)點(diǎn), 并且找到左右孩子中最大的結(jié)點(diǎn);
? ? ? ? //如果左孩子小于右孩子,那么j++; 否則不自增1. 因?yàn)樗旧砭捅扔液⒆哟?
? ? ? ? if(j < m && L->r[j] < L->r[j+1])
? ? ? ? ? ? ++j;
? ? ? ? //④ 比較當(dāng)前的temp 是不是比較左右孩子大; 如果大則表示我們已經(jīng)構(gòu)建成大頂堆了;
? ? ? ? if(temp >= L->r[j])
? ? ? ? ? ? break;
? ? ? ? //⑤ 將L->[j] 的值賦值給非葉子根結(jié)點(diǎn)
? ? ? ? L->r[s] = L->r[j];
? ? ? ? //⑥ 將s指向j; 因?yàn)榇藭rL.r[4] = 60, L.r[8]=60. 那我們需要記錄這8的索引信息.等退出循環(huán)時,能夠把temp值30 覆蓋到L.r[8] = 30. 這樣才實(shí)現(xiàn)了30與60的交換;
? ? ? ? s = j;
? ? }
? ? //⑦ 將L->r[s] = temp. 其實(shí)就是把L.r[8] = L.r[4] 進(jìn)行交換;
? ? L->r[s] = temp;
}
堆排序--對順序表進(jìn)行堆排序
void HeapSort(SqList *L){
? ? int?i;
? ? //1.將現(xiàn)在待排序的序列構(gòu)建成一個大頂堆;
? ? //將L構(gòu)建成一個大頂堆;
? ? //i為什么是從length/2.因?yàn)樵趯Υ箜敹训恼{(diào)整其實(shí)是對非葉子的根結(jié)點(diǎn)調(diào)整.
? ? for(i=L->length/2; i>0;i--){
? ? ? ? HeapAjust(L, i, L->length);
? ? }
? ? //2.逐步將每個最大的值根結(jié)點(diǎn)與末尾元素進(jìn)行交換,并且再調(diào)整成大頂堆
? ? for(i = L->length; i >1; i--){
? ? ? ? //① 將堆頂記錄與當(dāng)前未經(jīng)排序子序列的最后一個記錄進(jìn)行交換;
? ? ? ? swap(L,1, i);
? ? ? ? //② 將L->r[1...i-1]重新調(diào)整成大頂堆;
? ? ? ? HeapAjust(L,1, i-1);
? ? }
}
堆排序的時間復(fù)雜度為：O(nlogn)
堆排序是就地排序，空間復(fù)雜度為常數(shù)：O(1)
歸并排序
合并
//③ 將有序的SR[i..mid]和SR[mid+1..n]歸并為有序的TR[i..n]
void?Merge(intSR[],intTR[],inti,intm,intn)
{
? ? int?j,k,l;
? ? //1.將SR中記錄由小到大地并入TR
? ? for(j=m+1,k=i;i<=m && j<=n;k++)
? ? {
? ? ? ? if?(SR[i]<SR[j])
? ? ? ? ? ? TR[k]=SR[i++];
? ? ? ? else
? ? ? ? ? ? TR[k]=SR[j++];
? ? }
? ? //2.將剩余的SR[i..mid]復(fù)制到TR
? ? if(i<=m)
? ? {
? ? ? ? for(l=0;l<=m-i;l++)
? ? ? ? ? ? TR[k+l]=SR[i+l];
? ? }
? ? //3.將剩余的SR[j..mid]復(fù)制到TR
? ? if(j<=n)
? ? {
? ? ? ? for(l=0;l<=n-j;l++)
? ? ? ? ? ? TR[k+l]=SR[j+l];
? ? }
}
1.遞歸實(shí)現(xiàn)： 將數(shù)據(jù) 拆成長度1的子序列， 再將子序列兩兩進(jìn)行合并且排序
先拆分，后合并
//② 將SR[s...t] 歸并排序?yàn)?TR1[s...t];
void?MSort(int?SR[],int?TR1[],int?low,int?hight){
? ? int?mid;
? ? int?TR2[MAXSIZE+1];
? ? if(low == hight)
? ? ? ? TR1[low] = SR[low];
? ? else{
? ? ? ? //1.將SR[low...hight] 平分成 SR[low...mid] 和 SR[mid+1,hight];
? ? ? ? mid = (low + hight)/2;
? ? ? ? //2. 遞歸將SR[low,mid]歸并為有序的TR2[low,mid];
? ? ? ? MSort(SR, TR2, low, mid);
? ? ? ? //3. 遞歸將SR[mid+1,hight]歸并為有序的TR2[mid+1,hight];
? ? ? ? MSort(SR, TR2, mid+1, hight);
? ? ? ? //4. 將TR2[low,mid] 與 TR2[mid+1,hight], 歸并到TR1[low,hight]中
? ? ? ? Merge(TR2, TR1, low, mid, hight);
? ? }
}
//① 對順序表L進(jìn)行歸并排序
void MergeSort(SqList *L){
? ? MSort(L->r,L->r,1,L->length);
}
2.非遞歸實(shí)現(xiàn)：
邊拆分，邊合并
//對SR數(shù)組中相鄰長度為s的子序列進(jìn)行兩兩歸并到TR[]數(shù)組中;
void?MergePass(int?SR[],int?TR[],int?s,int?length){
? ? int?i =1;
? ? int?j;
? ? //①合并數(shù)組
? ? //s=1 循環(huán)結(jié)束位置:8 (9-2*1+1=8)
? ? //s=2 循環(huán)結(jié)束位置:6 (9-2*2+1=6)
? ? //s=4 循環(huán)結(jié)束位置:2 (9-2*4+1=2)
? ? //s=8 循環(huán)結(jié)束位置:-6(9-2*8+1=-6) s = 8時,不會進(jìn)入到循環(huán);
? ? while(i<= length-2*s+1) {
? ? ? ? //兩兩歸并(合并相鄰的2段數(shù)據(jù))
? ? ? ? Merge(SR, TR, i, i+s-1, i+2*s-1);
? ? ? ? i = i+2*s;
? ? ? ? /*
?? ? ? ? s = 1,i = 1,Merge(SR,TR,1,1,2);
?? ? ? ? s = 1,i = 3,Merge(SR,TR,3,3,4);
?? ? ? ? s = 1,i = 5,Merge(SR,TR,5,5,6);
?? ? ? ? s = 1,i = 7,Merge(SR,TR,7,7,8);
?? ? ? ? s = 1,i = 9,退出循環(huán);
?? ? ? ? */
? ? ? ? /*
?? ? ? ? s = 2,i = 1,Merge(SR,TR,1,2,4);
?? ? ? ? s = 2,i = 5,Merge(SR,TR,5,6,8);
?? ? ? ? s = 2,i = 9,退出循環(huán);
?? ? ? ? */
? ? ? ? /*
?? ? ? ? s = 4,i = 1,Merge(SR,TR,1,4,8);
?? ? ? ? s = 4,i = 9,退出循環(huán);
?? ? ? ? */
? ? }
? ? //②如果i
? ? // 1 < (9-8+1)(2)
? ? //s = 8時, 1 < (9-8+1)
? ? if(i < length-s+1){
? ? ? ? //Merge(SR,TR,1,8,9)
? ? ? ? Merge(SR, TR, i, i+s-1, length);
? ? }else{
? ? ? ? //③只剩下一個子序列;
? ? ? ? for(j = i; j <=length; j++) {
? ? ? ? ? ? TR[j] = SR[j];
? ? ? ? }
? ? }
}
void MergeSort2(SqList *L){
? ? int?*TR = (int?*)malloc(sizeof(int) * L->length);
? ? int?k =1;
? ? //k的拆分變換是 1,2,4,8;
? ? while(k < L->length) {
? ? ? ? //將SR數(shù)組按照s=2的長度進(jìn)行拆分合并,結(jié)果存儲到TR數(shù)組中;
? ? ? ? //注意:此時經(jīng)過第一輪的歸并排序的結(jié)果是存儲到TR數(shù)組了;
? ? ? ? MergePass(L->r, TR, k, L->length);
? ? ? ? k =2*k;
? ? ? ? //將剛剛歸并排序后的TR數(shù)組,按照s = 2k的長度進(jìn)行拆分合并. 結(jié)果存儲到L->r數(shù)組中;
? ? ? ? //注意:因?yàn)樯弦惠喌呐判虻慕Y(jié)果是存儲到TR數(shù)組,所以這次排序的數(shù)據(jù)應(yīng)該是再次對TR數(shù)組排序;
? ? ? ? MergePass(TR, L->r, k, L->length);
? ? ? ? k =2*k;
? ? }
}
排序總結(jié)
穩(wěn)定性解釋：排序后的元素相同元素的順序依然是排序之前的順序
