詳解C++實現(xiàn)鏈表的排序算法
更新時間：2021年06月11日 16:40:52 作者：Ouyang_Lianjun
鏈表排序思想和數(shù)組排序類似，區(qū)別就是數(shù)組遍歷容易，數(shù)據(jù)交換也容易；鏈表(單項鏈表)只能一個方向遍歷，不能逆序遍歷，且不能隨機(jī)訪問，所以排序比較麻煩。本文將詳細(xì)介紹鏈表排序的方式，并且用C++來實現(xiàn)
一、鏈表排序
最簡單、直接的方式（直接采用冒泡或者選擇排序，而且不是交換結(jié)點(diǎn)，只交換數(shù)據(jù)域）
//線性表的排序,采用冒泡排序,直接遍歷鏈表
void Listsort(Node* & head) {
int i = 0;
int j = 0;
//用于變量鏈表
Node * L = head;
//作為一個臨時量
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++) {
//得到兩個值
p = L;
p1 = L->next;
//如果前面的那個比后面的那個大，就交換它們之間的是數(shù)據(jù)域
if (p->value > p1->value) {
Elemtype temp = p->value;
p->value = p1->value;
p1->value = temp;
}
L = L->next;
}
}
}
因為排序中速度比較快的如快速排序是要求它們的數(shù)據(jù)域的地址是相連接的，它比較適合于順序結(jié)構(gòu)，而鏈?zhǔn)浇Y(jié)構(gòu)的時候，我們就只有使用只會進(jìn)行前后兩個比較多排序算法，比如冒泡排序等。我們這里是沒有交換結(jié)點(diǎn)的一種排序方式，這種方式簡單，明了，這樣就是數(shù)組排序的時候是一樣的。后面我會寫通過交換結(jié)點(diǎn)的方式的排序。
下面我們就討論討論這個排序算法的時間復(fù)雜度了，因為它是使用冒泡排序的，它的時間只要消耗在那兩重循環(huán)，所以時間復(fù)雜度為：O(n*n),這個效率實在是太低，下面我們對這個想(ˇˍˇ) 想～通過另外一種方式來實現(xiàn)鏈表的排序
二、另外一種鏈表排序方式
我們在討論排序算法的時候，都是把數(shù)據(jù)存放在數(shù)組中進(jìn)行討論的，在順序結(jié)構(gòu)下，我們可以采取很多高效的排序算法，那么這個就是我們另外一種對鏈表排序的方式，先把鏈表的內(nèi)容存放到數(shù)組中（時間為O(n)），然后，我們在對那個數(shù)組進(jìn)行排序（最快為nlog(n)），最后，存放鏈表中（時間為O(n)）。通過計算，我們可以得到它的時間復(fù)雜為（O(nlogn)）,這個速度已經(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的時候，明顯第二種排序算法消耗的時間比第一種快了28倍左右。
四、下面通過交換結(jié)點(diǎn)實現(xiàn)鏈表的排序
首先我們編寫交換結(jié)點(diǎn)的函數(shù)，結(jié)點(diǎn)的交換主要就是考慮結(jié)點(diǎn)的指針域的問題，其中相鄰兩個結(jié)點(diǎn)是一種特殊的情況，要拿出來特別考慮。我們先畫出結(jié)點(diǎn)交換的思路圖，如下圖
首先我們給出相鄰兩個結(jié)點(diǎn)交換的思路：
下面是普通情況下的交換如下圖
//參數(shù)為頭結(jié)點(diǎn)和需要交換的兩個結(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 << "請檢查位置是否合法" << endl;
return;
}
//同一個位置不用交換
if (i == j)
{
return;
}
//相鄰兩個交換比較簡單
if (abs(i - j) == 1) {
//位置靠前的那個結(jié)點(diǎn)的前一個結(jié)點(diǎn)
Node * pre;
if (i < j)
pre = getitem(head, i);
else
pre = getitem(head, j);
//保存第一個結(jié)點(diǎn)
Node * a = pre->next;
//保存第二結(jié)點(diǎn)
Node * b = a->next;
//改變pre下一個結(jié)點(diǎn)的值
pre->next = b;
//必須先把b的下一個結(jié)點(diǎn)值給a先
a->next = b->next;
//讓b的下一個結(jié)點(diǎn)等于a
b->next = a;
return;
}
//第一個結(jié)點(diǎn)前一個結(jié)點(diǎn)
Node * a = getitem(head, i);
//第二個結(jié)點(diǎn)的前一個結(jié)點(diǎn)
Node * b = getitem(head, j);
//第一個結(jié)點(diǎn)
Node * p = a->next;
//第二個結(jié)點(diǎn)
Node * q = b->next;
//第一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)
Node * p_next = p->next;
//第二結(jié)點(diǎn)的下一個結(jié)點(diǎn)
Node * q_next = q->next;
//a的下一個結(jié)點(diǎn)指向第二個結(jié)點(diǎn)q
a->next = q;
//第二結(jié)點(diǎn)的下一個結(jié)點(diǎn)指向第一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)
q->next = p_next;
//b的下一個結(jié)點(diǎn)指向第一個結(jié)點(diǎn)p
b->next = p;
//第一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)指向第二個結(jié)點(diǎn)的下一個結(jié)點(diǎn)
p->next = q_next;
}
排序時候的代碼，切記交換結(jié)點(diǎn)都是前后結(jié)點(diǎn)交換，所以交換完成后，L就已經(jīng)被移動到下一個結(jié)點(diǎn)了，故不要再執(zhí)行：L=L->next
//線性表的排序，交換結(jié)點(diǎn)
void Listsort_Node(Node* & head) {
int i = 0;
int j = 0;
//用于變量鏈表
Node * L = head;
//作為一個臨時量
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)的時候，把L移動到下一個結(jié)點(diǎn)了，所以不要
//再執(zhí)行：L = L->next;，否則會報錯的
if (L->value > L->next->value) {
flag = 1;
swap_node(head, j + 1, j + 2);
}
if (flag == 1) {
flag = 0;
}
else {
L = L->next;
}
}
}
}
好了，今天的就寫到這里了，今天通過寫交換結(jié)點(diǎn)，發(fā)現(xiàn)鏈表真的很容易忽悠人，我就被忽悠了一個小時，才知道那個結(jié)點(diǎn)已經(jīng)被移動到下一個結(jié)點(diǎn)了。
最后，補(bǔ)充一個實現(xiàn)鏈表反轉(zhuǎn)的好方法（感覺你在頭文件里面計算一下鏈表的長度可以帶來很多遍歷的）
void rollback(Node * & head) {
//先知道了最后一個元素和第一個元素的位置
int end = head->value;
int start = 1;
//兩邊同時開工
//進(jìn)行調(diào)換
while (1) {
if (end == start)
return;
swap_node(head, end, start);
--end;
++start;
}
}
希望大家，對我寫的代碼做出一些評價。我想想還是直接貼個完成的代碼出來好了，調(diào)轉(zhuǎn)代碼也在里面了
include<iostream>
#include<ctime>
#include<cstdlib>
#include<windows.h>
#include<algorithm>
using namespace std;
typedef int Elemtype;
//鏈?zhǔn)浇Y(jié)構(gòu)，我們打算在鏈表中添加一個
//保存長度的頭結(jié)點(diǎn)，加入這個結(jié)點(diǎn)可以方便我們對結(jié)點(diǎn)做一些
//基本的操作，結(jié)點(diǎn)保存的是線性表的長度
struct Node
{
//結(jié)點(diǎn)的值,如果是頭結(jié)點(diǎn)，保存是鏈表的長度
Elemtype value;
//下一個結(jié)點(diǎn)的地址
Node * next;
};
//創(chuàng)建一個空鏈表，每個頭結(jié)點(diǎn)就代表一個鏈表
void InitList(Node * & head) {
head = new Node();
head->value = 0;
head->next = NULL;
}
//銷毀一個鏈表
void DestroyList(Node * & head) {
delete head;
head = NULL;
}
//清空整個列表
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;
//如果插入的位置不合法，直接返回錯誤提示
if (i<1 || i>head->value + 1)return false;
//得到插入位置的前一個結(jié)點(diǎn)
while (j < i - 1) {
L = L->next;
++j;
}
//s是一個臨時結(jié)點(diǎn)
Node * s = new Node();
s->value = value; //先對臨時結(jié)點(diǎn)賦值
s->next = L->next; //讓臨時結(jié)點(diǎn)下一個位置指向當(dāng)前需要插入前一個結(jié)點(diǎn)的下一個位置
L->next = s; //讓前一個結(jié)點(diǎn)下一個位置指向臨時結(jié)點(diǎn)，完成
//線性表的長度加一
++head->value;
return true;
}
//得到某個位置上的值
Node * getitem(Node * & head, int i) {
//我們要求程序返回特定位置上的值
//我們一樣是從頭結(jié)點(diǎn)開始尋找該位置
int j = 0;
Node * L = head;
//想要的那個位置是否合法
if (i<1 || i >head->value)return NULL;
//同樣是先得到前一個結(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;
//作為一個臨時量
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++) {
//得到兩個值
p = L;
p1 = L->next;
//如果前面的那個比后面的那個大，就交換它們之間的是數(shù)據(jù)域
if (p->value > p1->value) {
Elemtype temp = p->value;
p->value = p1->value;
p1->value = temp;
}
L = L->next;
}
}
}
//通過數(shù)組來完成我的排序
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)和需要交換的兩個結(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 << "請檢查位置是否合法" << endl;
return;
}
//同一個位置不用交換
if (i == j)
{
return;
}
//相鄰兩個交換比較簡單
if (abs(i - j) == 1) {
//位置靠前的那個結(jié)點(diǎn)的前一個結(jié)點(diǎn)
Node * pre;
if (i < j)
pre = getitem(head, i);
else
pre = getitem(head, j);
//保存第一個結(jié)點(diǎn)
Node * a = pre->next;
//保存第二結(jié)點(diǎn)
Node * b = a->next;
//改變pre下一個結(jié)點(diǎn)的值
pre->next = b;
//必須先把b的下一個結(jié)點(diǎn)值給a先
a->next = b->next;
//讓b的下一個結(jié)點(diǎn)等于a
b->next = a;
return;
}
//第一個結(jié)點(diǎn)前一個結(jié)點(diǎn)
Node * a = getitem(head, i);
//第二個結(jié)點(diǎn)的前一個結(jié)點(diǎn)
Node * b = getitem(head, j);
//第一個結(jié)點(diǎn)
Node * p = a->next;
//第二個結(jié)點(diǎn)
Node * q = b->next;
//第一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)
Node * p_next = p->next;
//第二結(jié)點(diǎn)的下一個結(jié)點(diǎn)
Node * q_next = q->next;
//a的下一個結(jié)點(diǎn)指向第二個結(jié)點(diǎn)q
a->next = q;
//第二結(jié)點(diǎn)的下一個結(jié)點(diǎn)指向第一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)
q->next = p_next;
//b的下一個結(jié)點(diǎn)指向第一個結(jié)點(diǎn)p
b->next = p;
//第一個結(jié)點(diǎn)的下一個結(jié)點(diǎn)指向第二個結(jié)點(diǎn)的下一個結(jié)點(diǎn)
p->next = q_next;
}
//反轉(zhuǎn)
void rollback(Node * & head) {
//先知道了最后一個元素和第一個元素的位置
int end = head->value;
int start = 1;
//兩邊同時開工
//進(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;
//作為一個臨時量
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)的時候，把L移動到下一個結(jié)點(diǎn)了，所以不要
//再執(zhí)行：L = L->next;，否則會報錯的
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)下一個結(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)建一個鏈表
InitList(head);
InitList(head_array);
InitList(head_node);
InitList(head_roll);
int i;
cout << "請輸入需要插入元素個數(shù)" << endl;
int n;
cin >> n;//5
//cout << "請輸入" << n << "個值" << 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é)果：
以上就是詳解C++實現(xiàn)鏈表的排序算法的詳細(xì)內(nèi)容，更多關(guān)于C++ 鏈表排序算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Qt?10進(jìn)制和16進(jìn)制轉(zhuǎn)換的使用示例
在編程過程中,處理16進(jìn)制字符串與10進(jìn)制數(shù)字之間的轉(zhuǎn)換是很常見的需求,本文主要介紹了Qt?10進(jìn)制和16進(jìn)制轉(zhuǎn)換的使用示例，具有一定的參考價值，感興趣的可以了解一下2023-09-09
在C語言中,邏輯或運(yùn)算符（||）是一種常用的邏輯運(yùn)算符,用于組合多個條件表達(dá)式,C語言中的邏輯或運(yùn)算符具有短路機(jī)制,這是一種非常重要的概念,本文將深入解釋C語言中的||短路機(jī)制以及其在編程中的應(yīng)用,感興趣的朋友跟隨小編一起看看吧2024-01-01
C++實現(xiàn)LeetCode(92.倒置鏈表之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(倒置鏈表之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C++ 詳解數(shù)據(jù)結(jié)構(gòu)中的搜索二叉樹
搜索二叉樹是一種具有良好排序和查找性能的二叉樹數(shù)據(jù)結(jié)構(gòu)，包括多種操作，本篇只介紹插入，排序（遍歷），和刪除操作，重點(diǎn)是刪除操作比較復(fù)雜2022-04-04
這篇文章主要為大家詳細(xì)介紹了C語言的預(yù)處理，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要為大家詳細(xì)介紹了如何利用C++實現(xiàn)重載矩陣的部分運(yùn)算符，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下2022-10-10
這篇文章主要介紹了C++輸入輸出注意事項總結(jié),對C++的輸入輸出各個注意事項進(jìn)行了很好的總結(jié),需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實現(xiàn)簡易的方塊游戲，文中的示例代碼講解詳細(xì)，具有一定的參考價值，感興趣的小伙伴可以了解一下2023-03-03
這篇文章主要介紹了C++獲取文件大小的4種常見技巧分享，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
VS2019添加引用出錯：對COM組件的調(diào)用返回了錯誤HRESULT E_FAIL（未能完成操作未指定的錯誤）
這篇文章主要介紹了VS2019添加引用出錯：對COM組件的調(diào)用返回了錯誤HRESULT E_FAIL（未能完成操作。未指定的錯誤）,需要的朋友可以參考下2020-07-07