目錄
- 選擇排序
- 冒泡排序
- 快速排序
- 合并兩條鏈表并排序
選擇排序
鏈表的選擇排序思想與數(shù)組的排序類似，但是鏈表需要先找到里面最小或者最大的值，然后將這個值用改鏈語句進(jìn)行操作
我們先看這個改鏈語句的操作（min是筆者打錯了應(yīng)該是max，但是圖已經(jīng)畫好了就沒有改）
移動q這個指針找到最大的min，然后利用i保存q的前一個節(jié)點這樣就能找到min_on.
接下來進(jìn)行改鏈語句的操作
min_on->next = min->next; // 1
min->next = tail->next; // 2
tail->next = min; //3
接下來將tail前移一位重復(fù)操作。
void insert(li *head) //傳進(jìn)來一個有頭節(jié)點的鏈表
{
li* tail,*i,*min,*q,*min_on;
/*注意條件是 tail&&tail->next 因為如果tail->next == null
會使程序進(jìn)入里面的for循環(huán)出現(xiàn)問題*/
for(tail = head; tail&&tail->next; tail=tail->next)
{
min = tail->next;
for(q = tail->next,i = tail; q; i=q,q=q->next) //i是p的上一個節(jié)點
{
if(q->digit > min->digit) //尋找最大的數(shù)
{
min = q;
min_on = i; //保存min的上一個節(jié)點
}
}
if(tail->next != min) //如果找到比tail->next更小的 min那么就進(jìn)行插入
{
min_on->next = min->next;
min->next = tail->next;
tail->next = min;
}
}
}
冒泡排序
冒泡排序最重要的一步就是將元素下沉，然后重新判斷循環(huán)次數(shù)
在這里我們首先引入一個tail的變量
#例如2，4， 5，null 三個數(shù)由大到小排序
| 數(shù)字 | 2 | 4 | 5 | null |
|---|---|---|---|---|
| p | 1 | tail |
初始時令tail == null；讓p從1位置開始移動
結(jié)束條件是p ！= tail，
這樣第一次時：就能保證1交換兩次，接下來將tail向前移動，讓tail = null的前一個位置；
此時我們將2下沉到底部；數(shù)據(jù)變?yōu)椋?strong>4，5，2
| 數(shù)字 | 4 | 5 | 2 | null |
|---|---|---|---|---|
| p | 1 | tail |
p繼續(xù)從1 位置開始移動
第二次時就能保證4交換1次；數(shù)據(jù)就變成了5，4，2完成排序。
接下來我們看如何進(jìn)行改鏈操作
p->next = q->next; //1
q->next = q->next->next; //2
p->next->next = q; //3
接下來移動q的位置使得p，q始終相鄰.
q = p->next;
代碼如下：
void bubbling(li *head) //傳進(jìn)來一個有頭節(jié)點的鏈表
{
li *tail,*p,*q;
tail = NULL;
/*假定如果三個數(shù)排序，第二個數(shù)確定了那么
第一個也就確定了，不需要對第一個數(shù)排序*/
while((head->next->next) != tail)
{
p = head;
q = head->next;
/*冒泡排序的本質(zhì)將所找到的數(shù)都下沉，所以內(nèi)層循環(huán)比外層小一個節(jié)點*/
while((q->next) != tail)
{
if((q->digit) > (q->next->digit)) //不停判斷兩個相鄰的數(shù)并且交換順序
{
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
q = p->next; //始終保存p，q是相鄰的位置
}
q = q->next;
p = p->next;
}
/*最重要的一步，將tail不停向前移動*/
tail = q;
}
}
快速排序
數(shù)組快速排序的思想和鏈表的一樣，主要問題就是存在改鏈的操作。
首先我們還是做一個類似二分法的遞歸操作，叫做"分", 接下來分別給兩邊節(jié)點排序
void quick_sort(node *head, node *tail) //傳進(jìn)來一個有頭節(jié)點的鏈表，初始時tail為NULL
{
//頭結(jié)點是空的或者表是空的或者表只有一個節(jié)點時候不用排
//tail是鏈表的結(jié)束點，一開始等于NULL,后面等于privot
if(!head || head->next == tail || head->next->next == tail)
{
return ;
}
//baisc前的節(jié)點都比basic小，baisc后的節(jié)點都比baisc大
node *privot = partition(head, tail);
/*因為在"治"的操作中privot會變成下一個節(jié)點，
所以此時和數(shù)組時不一樣，不需要類似privot-1/+1的操作*/
quick_sort(head, privot); //把head->next到privot前一個進(jìn)行遞歸排序
quick_sort(privot, tail); //從privot->next到tail前一個進(jìn)行遞歸排序
}
接下來我們進(jìn)行排序，首先選取一個基準(zhǔn)點，如何將比基準(zhǔn)點大/小的值放左邊，比基準(zhǔn)點小/大的放右邊。
例如2，1，4，null的改鏈操作
先得到一個基準(zhǔn)點 privot = head->next
privot->digit = 2；
接下來進(jìn)行改鏈操作，假定為由小到大排序
i->next = p->next; //1 p->next = head->next; //2 head->next = p; //3
此時改鏈完成我們得到
那么如果后面的4還需要排序的話我們可以將 p = i->next 然后重復(fù)以上步驟進(jìn)行排序。
"治"的代碼如下：
node *partition(node *head, node *tail) //結(jié)構(gòu)體指針類型函數(shù)，需要一個結(jié)構(gòu)體指針的返回值
{
//頭結(jié)點是空的或者表是空的或者表只有一個節(jié)點時候不用排
//已經(jīng)在調(diào)用函數(shù)前判斷好了，進(jìn)來的鏈表都是至少有兩個元素的
node *p, *i, *privot;
privot = head->next; //privot是基準(zhǔn)點
//從privot后面開始遍歷，找到比privot小的就插入到head后面，直到tail結(jié)束，i是p的前驅(qū)節(jié)點
//這里head可以理解為本次待劃分的鏈表的頭結(jié)點，tail是鏈表的最后一個節(jié)點的下一個可以理解為NULL
for(i = privot, p = privot->next; p && p != tail; p = i->next)
{
if(privot->digit < p->digit) //用頭插入法把所有比privot小插入到head后面
{
i->next = p->next;
p->next = head->next;
head->next = p;
}
else //沒有找到比privot小的就一直后移，i與p同時后移
{
i = i->next;
}
}
return privot;
}
合并兩條鏈表并排序
接下來我們練習(xí)一道例題，將兩個鏈表合成為一個鏈表并使它有序
輸出：
1 3 5 5 6
4 2 5 1 9
輸出：
1 1 2 3 4 5 5 5 6 9
我們首先將兩個鏈表連接文章來源：http://www.zghlxwxcb.cn/news/detail-759821.html
void sum(mlist *a,mlist *b) //傳入兩個帶有頭節(jié)點的鏈表
{
mlist *p;
p = a;
while(p->next)
{
p = p->next;
}
//釋放掉b鏈表的表頭
mlist *t = b;
b = b->next;
free(t);
p->next = b; //連接a,b鏈表
}
然后我們就可以將鏈表進(jìn)行排序了，完整的代碼如下文章來源地址http://www.zghlxwxcb.cn/news/detail-759821.html
#include <stdio.h>
#include <stdlib.h>
typedef struct _lis{
int digit;
struct _lis *next;
}mlist;
typedef struct _ls{
mlist *head;
}helist;
void make(mlist *meter); //制作鏈表
void sum(mlist *a,mlist *b); //鏈表合成
void output(mlist *meter); //輸出鏈表
void bubbling(mlist *head); //冒泡排序
int main()
{
helist a,b;
a.head = (mlist*)malloc(sizeof(mlist));
a.head->next = NULL;
b.head = (mlist*)malloc(sizeof(mlist));
b.head->next = NULL;
printf("請輸入a鏈表\n");
make(a.head); //制作鏈表
printf("請輸入b鏈表\n");
make(b.head);
sum(a.head,b.head); //鏈表連接
bubbling(a.head); //鏈表排序
output(a.head); //輸出鏈表
}
void make(mlist *meter) //制作
{
int number;
mlist *t;
t = meter;
while(scanf("%d",&number) != EOF) //尾插法制作一個鏈表
{
mlist *p = (mlist*)malloc(sizeof(mlist));
p->digit = number;
p->next = NULL;
t->next = p;
t = p;
}
}
void output(mlist *meter) //輸出
{
for(mlist *i = meter->next; i; i=i->next)
{
printf("%d\t",i->digit); //輸出節(jié)點的值
}
printf("\n");
}
void sum(mlist *a,mlist *b) //連接
{
mlist *p;
p = a;
while(p->next)
{
p = p->next;
}
//釋放掉b鏈表的表頭
mlist *t = b;
b = b->next;
free(t);
p->next = b; //連接a,b鏈表
}
void bubbling(mlist *head) //排序，傳進(jìn)來一個有頭節(jié)點的鏈表
{
mlist *tail,*p,*q;
tail = NULL;
/*假定如果三個數(shù)排序，第二個數(shù)確定了那么
第一個也就確定了，不需要對第一個數(shù)排序*/
while((head->next->next) != tail)
{
p = head;
q = head->next;
/*冒泡排序的本質(zhì)將所找到的數(shù)都下沉，所以內(nèi)層循環(huán)比外層小一個節(jié)點*/
while((q->next) != tail)
{
if((q->digit) > (q->next->digit)) //不停判斷兩個相鄰的數(shù)并且交換順序
{
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
q = p->next; //始終保存p，q是相鄰的位置
}
q = q->next;
p = p->next;
}
/*最重要的一步，將tail不停向前移動*/
tail = q;
}
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】單鏈表的排序算法(選擇，冒泡，遞歸）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
