本篇內(nèi)容主要講解“C++中怎么實(shí)現(xiàn)鏈表的排序算法”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“C++中怎么實(shí)現(xiàn)鏈表的排序算法”吧!
最簡(jiǎn)單、直接的方式（直接采用冒泡或者選擇排序，而且不是交換結(jié)點(diǎn)，只交換數(shù)據(jù)域）
重慶分公司
重慶分公司
//線性表的排序,采用冒泡排序,直接遍歷鏈表
void Listsort(Node* & head) {
int i = 0;
int j = 0;
//用于變量鏈表
Node * L = head;
//作為一個(gè)臨時(shí)量
Node * p;
Node * p1;
//如果鏈表為空直接返回
if (head->value == 0)return;
for (i = 0; i < head->value - 1; i++) {
L = head->next;
for (j = 0; j < head->value - i - 1; j++) {
//得到兩個(gè)值
p = L;
p1 = L->next;
//如果前面的那個(gè)比后面的那個(gè)大，就交換它們之間的是數(shù)據(jù)域
if (p->value > p1->value) {
Elemtype temp = p->value;
p->value = p1->value;
p1->value = temp;
}
L = L->next;
}
}
}因?yàn)榕判蛑兴俣缺容^快的如快速排序是要求它們的數(shù)據(jù)域的地址是相連接的，它比較適合于順序結(jié)構(gòu)，而鏈?zhǔn)浇Y(jié)構(gòu)的時(shí)候，我們就只有使用只會(huì)進(jìn)行前后兩個(gè)比較多排序算法，比如冒泡排序等。我們這里是沒(méi)有交換結(jié)點(diǎn)的一種排序方式，這種方式簡(jiǎn)單，明了，這樣就是數(shù)組排序的時(shí)候是一樣的。后面我會(huì)寫(xiě)通過(guò)交換結(jié)點(diǎn)的方式的排序。
下面我們就討論討論這個(gè)排序算法的時(shí)間復(fù)雜度了，因?yàn)樗鞘褂妹芭菖判虻模臅r(shí)間只要消耗在那兩重循環(huán)，所以時(shí)間復(fù)雜度為：O(n*n),這個(gè)效率實(shí)在是太低，下面我們對(duì)這個(gè)想(ˇ?ˇ) 想～通過(guò)另外一種方式來(lái)實(shí)現(xiàn)鏈表的排序
我們?cè)谟懻撆判蛩惴ǖ臅r(shí)候，都是把數(shù)據(jù)存放在數(shù)組中進(jìn)行討論的，在順序結(jié)構(gòu)下，我們可以采取很多高效的排序算法，那么這個(gè)就是我們另外一種對(duì)鏈表排序的方式，先把鏈表的內(nèi)容存放到數(shù)組中（時(shí)間為O(n)），然后，我們?cè)趯?duì)那個(gè)數(shù)組進(jìn)行排序（最快為nlog(n)），最后，存放鏈表中（時(shí)間為O(n)）。通過(guò)計(jì)算，我們可以得到它的時(shí)間復(fù)雜為（O(nlogn)）,這個(gè)速度已經(jīng)和順序結(jié)構(gòu)下差不多了，可以接受
void Listsort_1(Node* & head) {
int i = 0;
int j = 0;
//用于變量鏈表
Node * L = head;
//如果鏈表為空直接返回
if (head->value == 0)return;
Elemtype * copy = new Elemtype[head->value];
//變量鏈表，存放數(shù)組
for (i = 0; i < head->value; i++) {
L = L->next;
copy[i] = L->value;
}
//調(diào)用STL中的sort函數(shù)
sort(copy, copy + head->value);
L = head;
//存放回鏈表中
for (i = 0; i < head->value; i++) {
L = L->next;
L->value= copy[i];
}
}
如圖所示，在數(shù)據(jù)量為10000的時(shí)候，明顯第二種排序算法消耗的時(shí)間比第一種快了28倍左右。
首先我們編寫(xiě)交換結(jié)點(diǎn)的函數(shù)，結(jié)點(diǎn)的交換主要就是考慮結(jié)點(diǎn)的指針域的問(wèn)題，其中相鄰兩個(gè)結(jié)點(diǎn)是一種特殊的情況，要拿出來(lái)特別考慮。我們先畫(huà)出結(jié)點(diǎn)交換的思路圖，如下圖
首先我們給出相鄰兩個(gè)結(jié)點(diǎn)交換的思路：
下面是普通情況下的交換如下圖
//參數(shù)為頭結(jié)點(diǎn)和需要交換的兩個(gè)結(jié)點(diǎn)的位置（起點(diǎn)為1）
void swap_node(Node * & head,int i,int j) {
//位置不合法
if (i<1 || j<1 || i>head->value || j >head->value) {
cout << "請(qǐng)檢查位置是否合法" << endl;
return;
}
//同一個(gè)位置不用交換
if (i == j)
{
return;
}
//相鄰兩個(gè)交換比較簡(jiǎn)單
if (abs(i - j) == 1) {
//位置靠前的那個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
Node * pre;
if (i < j)
pre = getitem(head, i);
else
pre = getitem(head, j);
//保存第一個(gè)結(jié)點(diǎn)
Node * a = pre->next;
//保存第二結(jié)點(diǎn)
Node * b = a->next;
//改變pre下一個(gè)結(jié)點(diǎn)的值
pre->next = b;
//必須先把b的下一個(gè)結(jié)點(diǎn)值給a先
a->next = b->next;
//讓b的下一個(gè)結(jié)點(diǎn)等于a
b->next = a;
return;
}
//第一個(gè)結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)
Node * a = getitem(head, i);
//第二個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
Node * b = getitem(head, j);
//第一個(gè)結(jié)點(diǎn)
Node * p = a->next;
//第二個(gè)結(jié)點(diǎn)
Node * q = b->next;
//第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
Node * p_next = p->next;
//第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
Node * q_next = q->next;
//a的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)q
a->next = q;
//第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
q->next = p_next;
//b的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)p
b->next = p;
//第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
p->next = q_next;
}排序時(shí)候的代碼，切記交換結(jié)點(diǎn)都是前后結(jié)點(diǎn)交換，所以交換完成后，L就已經(jīng)被移動(dòng)到下一個(gè)結(jié)點(diǎn)了，故不要再執(zhí)行：L=L->next
//線性表的排序，交換結(jié)點(diǎn)
void Listsort_Node(Node* & head) {
int i = 0;
int j = 0;
//用于變量鏈表
Node * L = head;
//作為一個(gè)臨時(shí)量
Node * p;
Node * p1;
//如果鏈表為空直接返回
if (head->value == 0)return;
int flag = 0;
cout << head->value << endl;
for (i = 0; i < head->value - 1; i++) {
L = head->next;
for (j = 0; j < head->value - 1 - i; j++) {
//如果我們交換了結(jié)點(diǎn)，那么我們就已經(jīng)在交換結(jié)點(diǎn)的時(shí)候，把L移動(dòng)到下一個(gè)結(jié)點(diǎn)了，所以不要
//再執(zhí)行：L = L->next;，否則會(huì)報(bào)錯(cuò)的
if (L->value > L->next->value) {
flag = 1;
swap_node(head, j + 1, j + 2);
}
if (flag == 1) {
flag = 0;
}
else {
L = L->next;
}
}
}
}好了，今天的就寫(xiě)到這里了，今天通過(guò)寫(xiě)交換結(jié)點(diǎn)，發(fā)現(xiàn)鏈表真的很容易忽悠人，我就被忽悠了一個(gè)小時(shí)，才知道那個(gè)結(jié)點(diǎn)已經(jīng)被移動(dòng)到下一個(gè)結(jié)點(diǎn)了。
最后，補(bǔ)充一個(gè)實(shí)現(xiàn)鏈表反轉(zhuǎn)的好方法（感覺(jué)你在頭文件里面計(jì)算一下鏈表的長(zhǎng)度可以帶來(lái)很多遍歷的）
void rollback(Node * & head) {
//先知道了最后一個(gè)元素和第一個(gè)元素的位置
int end = head->value;
int start = 1;
//兩邊同時(shí)開(kāi)工
//進(jìn)行調(diào)換
while (1) {
if (end == start)
return;
swap_node(head, end, start);
--end;
++start;
}
}希望大家，對(duì)我寫(xiě)的代碼做出一些評(píng)價(jià)。我想想還是直接貼個(gè)完成的代碼出來(lái)好了，調(diào)轉(zhuǎn)代碼也在里面了
include#include #include #include #include using namespace std; typedef int Elemtype; //鏈?zhǔn)浇Y(jié)構(gòu)，我們打算在鏈表中添加一個(gè) //保存長(zhǎng)度的頭結(jié)點(diǎn)，加入這個(gè)結(jié)點(diǎn)可以方便我們對(duì)結(jié)點(diǎn)做一些 //基本的操作，結(jié)點(diǎn)保存的是線性表的長(zhǎng)度 struct Node { //結(jié)點(diǎn)的值,如果是頭結(jié)點(diǎn)，保存是鏈表的長(zhǎng)度 Elemtype value; //下一個(gè)結(jié)點(diǎn)的地址 Node * next; }; //創(chuàng)建一個(gè)空鏈表，每個(gè)頭結(jié)點(diǎn)就代表一個(gè)鏈表 void InitList(Node * & head) { head = new Node(); head->value = 0; head->next = NULL; } //銷(xiāo)毀一個(gè)鏈表 void DestroyList(Node * & head) { delete head; head = NULL; } //清空整個(gè)列表 void ClearList(Node * & head) { head->value = 0; head->next = NULL; } //插入函數(shù) bool Listinsert(Node * & head, int i, Elemtype value) { //插入到前面的方法 int j = 0; Node * L = head; //如果插入的位置不合法，直接返回錯(cuò)誤提示 if (i<1 || i>head->value + 1)return false; //得到插入位置的前一個(gè)結(jié)點(diǎn) while (j < i - 1) { L = L->next; ++j; } //s是一個(gè)臨時(shí)結(jié)點(diǎn) Node * s = new Node(); s->value = value; //先對(duì)臨時(shí)結(jié)點(diǎn)賦值 s->next = L->next; //讓臨時(shí)結(jié)點(diǎn)下一個(gè)位置指向當(dāng)前需要插入前一個(gè)結(jié)點(diǎn)的下一個(gè)位置 L->next = s; //讓前一個(gè)結(jié)點(diǎn)下一個(gè)位置指向臨時(shí)結(jié)點(diǎn)，完成 //線性表的長(zhǎng)度加一 ++head->value; return true; } //得到某個(gè)位置上的值 Node * getitem(Node * & head, int i) { //我們要求程序返回特定位置上的值 //我們一樣是從頭結(jié)點(diǎn)開(kāi)始尋找該位置 int j = 0; Node * L = head; //想要的那個(gè)位置是否合法 if (i<1 || i >head->value)return NULL; //同樣是先得到前一個(gè)結(jié)點(diǎn) while (j < i - 1) { L = L->next; ++j; } //value = L->next->value; return L; } //線性表的排序,采用冒泡排序,直接遍歷鏈表 void Listsort(Node* & head) { int i = 0; int j = 0; //用于變量鏈表 Node * L = head; //作為一個(gè)臨時(shí)量 Node * p; Node * p1; //如果鏈表為空直接返回 if (head->value == 0)return; for (i = 0; i < head->value - 1; i++) { L = head->next; for (j = 0; j < head->value - i - 1; j++) { //得到兩個(gè)值 p = L; p1 = L->next; //如果前面的那個(gè)比后面的那個(gè)大，就交換它們之間的是數(shù)據(jù)域 if (p->value > p1->value) { Elemtype temp = p->value; p->value = p1->value; p1->value = temp; } L = L->next; } } } //通過(guò)數(shù)組來(lái)完成我的排序 void Listsort_by_array(Node* & head) { int i = 0; int j = 0; //用于變量鏈表 Node * L = head; //如果鏈表為空直接返回 if (head->value == 0)return; Elemtype * copy = new Elemtype[head->value]; //變量鏈表，存放數(shù)組 for (i = 0; i < head->value; i++) { L = L->next; copy[i] = L->value; } //調(diào)用STL中的sort函數(shù) sort(copy, copy + head->value); L = head; //存放回鏈表中 for (i = 0; i < head->value; i++) { L = L->next; L->value = copy[i]; } } //參數(shù)為頭結(jié)點(diǎn)和需要交換的兩個(gè)結(jié)點(diǎn)的位置（起點(diǎn)為1） void swap_node(Node * & head,int i,int j) { //位置不合法 if (i<1 || j<1 || i>head->value || j >head->value) { cout << "請(qǐng)檢查位置是否合法" << endl; return; } //同一個(gè)位置不用交換 if (i == j) { return; } //相鄰兩個(gè)交換比較簡(jiǎn)單 if (abs(i - j) == 1) { //位置靠前的那個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) Node * pre; if (i < j) pre = getitem(head, i); else pre = getitem(head, j); //保存第一個(gè)結(jié)點(diǎn) Node * a = pre->next; //保存第二結(jié)點(diǎn) Node * b = a->next; //改變pre下一個(gè)結(jié)點(diǎn)的值 pre->next = b; //必須先把b的下一個(gè)結(jié)點(diǎn)值給a先 a->next = b->next; //讓b的下一個(gè)結(jié)點(diǎn)等于a b->next = a; return; } //第一個(gè)結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn) Node * a = getitem(head, i); //第二個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) Node * b = getitem(head, j); //第一個(gè)結(jié)點(diǎn) Node * p = a->next; //第二個(gè)結(jié)點(diǎn) Node * q = b->next; //第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) Node * p_next = p->next; //第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) Node * q_next = q->next; //a的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)q a->next = q; //第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) q->next = p_next; //b的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)p b->next = p; //第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) p->next = q_next; } //反轉(zhuǎn) void rollback(Node * & head) { //先知道了最后一個(gè)元素和第一個(gè)元素的位置 int end = head->value; int start = 1; //兩邊同時(shí)開(kāi)工 //進(jìn)行調(diào)換 while (1) { if (end <= start) return; swap_node(head, end, start); --end; ++start; } } void print(Node * & head); //線性表的排序,采用冒泡排序,直接遍歷鏈表 //線性表的排序，交換結(jié)點(diǎn) void Listsort_node(Node* & head) { int i = 0; int j = 0; //用于變量鏈表 Node * L = head; //作為一個(gè)臨時(shí)量 Node * p; Node * p1; //如果鏈表為空直接返回 if (head->value == 0)return; int flag = 0; for (i = 0; i < head->value - 1; i++) { L = head->next; for (j = 0; j < head->value - 1 - i; j++) { //如果我們交換了結(jié)點(diǎn)，那么我們就已經(jīng)在交換結(jié)點(diǎn)的時(shí)候，把L移動(dòng)到下一個(gè)結(jié)點(diǎn)了，所以不要 //再執(zhí)行：L = L->next;，否則會(huì)報(bào)錯(cuò)的 if (L->value > L->next->value) { flag = 1; swap_node(head, j + 1, j + 2); } if (flag == 1) { flag = 0; } else { L = L->next; } } } } void print(Node * & head) { //輸出我們只需要傳入頭結(jié)點(diǎn)，然后循環(huán)判斷當(dāng)前結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)是否為空， //這樣就可以輸出所有內(nèi)容 Node * L = head; while (L->next) { L = L->next; cout << L->value << " "; } cout << endl; } int main() { //鏈表的頭結(jié)點(diǎn)，不存放任何值，首先初始化頭結(jié)點(diǎn) Node * head; Node * head_array; Node * head_node; Node * head_roll; srand((int)time(NULL)); //每次執(zhí)行種子不同，生成不同的隨機(jī)數(shù) //創(chuàng)建一個(gè)鏈表 InitList(head); InitList(head_array); InitList(head_node); InitList(head_roll); int i; cout << "請(qǐng)輸入需要插入元素個(gè)數(shù)" << endl; int n; cin >> n;//5 //cout << "請(qǐng)輸入" << n << "個(gè)值" << endl; for (i = 0; i < n; i++) { Elemtype temp; temp = rand(); if (!Listinsert(head, i + 1, temp)) { cout << "插入元素失敗" << endl; } if (!Listinsert(head_array, i + 1, temp)) { cout << "插入元素失敗" << endl; } if (!Listinsert(head_node, i + 1, temp)) { cout << "插入元素失敗" << endl; } if (!Listinsert(head_roll, i + 1, temp)) { cout << "插入元素失敗" << endl; } } cout << "初始化結(jié)果" << endl; print(head); cout << "反轉(zhuǎn)結(jié)果" << endl; rollback(head_roll); print(head_roll); cout << "冒泡排序（數(shù)據(jù)域交換）" << endl; Listsort(head); print(head); cout << "借數(shù)組為媒介進(jìn)行排序（數(shù)據(jù)域交換）" << endl; Listsort_by_array(head_array); print(head_array); cout << "冒泡排序（結(jié)點(diǎn)交換）" << endl; Listsort_node(head_node); print(head_node); system("pause"); return 0; }
運(yùn)行環(huán)境：vs2015
輸出結(jié)果：
到此，相信大家對(duì)“C++中怎么實(shí)現(xiàn)鏈表的排序算法”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)建站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！
