1. 首页
  2. 文章中心
  3. C语言

详解C++实现链表的排序算法

183 阅读 0 评论
我是靠谱客的博主 殷勤哈密瓜，这篇文章主要介绍详解C++实现链表的排序算法，现在分享给大家，希望可以做个参考。

一、链表排序

最简单、直接的方式（直接采用冒泡或者选择排序，而且不是交换结点，只交换数据域）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//线性表的排序,采用冒泡排序,直接遍历链表
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;
            //如果前面的那个比后面的那个大，就交换它们之间的是数据域
            if (p->value > p1->value) {
                Elemtype temp = p->value;
                p->value = p1->value;
                p1->value = temp;
            }
            L = L->next;
        }
    }
}

因为排序中速度比较快的如快速排序是要求它们的数据域的地址是相连接的，它比较适合于顺序结构，而链式结构的时候，我们就只有使用只会进行前后两个比较多排序算法，比如冒泡排序等。我们这里是没有交换结点的一种排序方式，这种方式简单，明了，这样就是数组排序的时候是一样的。后面我会写通过交换结点的方式的排序。

下面我们就讨论讨论这个排序算法的时间复杂度了，因为它是使用冒泡排序的，它的时间只要消耗在那两重循环，所以时间复杂度为：O(n*n),这个效率实在是太低，下面我们对这个想(ˇˍˇ) 想～通过另外一种方式来实现链表的排序

二、另外一种链表排序方式

我们在讨论排序算法的时候，都是把数据存放在数组中进行讨论的，在顺序结构下，我们可以采取很多高效的排序算法，那么这个就是我们另外一种对链表排序的方式，先把链表的内容存放到数组中（时间为O(n)），然后，我们在对那个数组进行排序（最快为nlog(n)），最后，存放链表中（时间为O(n)）。通过计算，我们可以得到它的时间复杂为（O(nlogn)）,这个速度已经和顺序结构下差不多了，可以接受

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
    //变量链表，存放数组
    for (i = 0; i < head->value; i++) {
        L = L->next;
        copy[i] = L->value;
    }
    //调用STL中的sort函数
    sort(copy, copy + head->value);
    L = head;
    //存放回链表中
    for (i = 0; i < head->value; i++) {
        L = L->next;
          L->value= copy[i];
    }
}

三、比较两种排序的效率

这里写图片描述

如图所示，在数据量为10000的时候，明显第二种排序算法消耗的时间比第一种快了28倍左右。

四、下面通过交换结点实现链表的排序

首先我们编写交换结点的函数，结点的交换主要就是考虑结点的指针域的问题，其中相邻两个结点是一种特殊的情况，要拿出来特别考虑。我们先画出结点交换的思路图，如下图

首先我们给出相邻两个结点交换的思路：

这里写图片描述

下面是普通情况下的交换如下图

这里写图片描述

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//参数为头结点和需要交换的两个结点的位置（起点为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) {
        //位置靠前的那个结点的前一个结点
        Node * pre;
        if (i < j)
            pre = getitem(head, i);
        else
            pre = getitem(head, j);

        //保存第一个结点
        Node * a = pre->next;
        //保存第二结点
        Node * b = a->next;
        //改变pre下一个结点的值
        pre->next = b;
        //必须先把b的下一个结点值给a先
        a->next = b->next;
        //让b的下一个结点等于a
        b->next = a;
        return;
    }

    //第一个结点前一个结点
    Node * a = getitem(head, i);
    //第二个结点的前一个结点
    Node * b = getitem(head, j);
    //第一个结点
    Node * p = a->next;
    //第二个结点
    Node * q = b->next;
    //第一个结点的下一个结点
    Node * p_next = p->next;
    //第二结点的下一个结点
    Node * q_next = q->next;

    //a的下一个结点指向第二个结点q
    a->next = q;
    //第二结点的下一个结点指向第一个结点的下一个结点
    q->next = p_next;
    //b的下一个结点指向第一个结点p
    b->next = p;
    //第一个结点的下一个结点指向第二个结点的下一个结点
    p->next = q_next;

}

排序时候的代码，切记交换结点都是前后结点交换，所以交换完成后，L就已经被移动到下一个结点了，故不要再执行：L=L->next

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//线性表的排序，交换结点
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++) {
            //如果我们交换了结点，那么我们就已经在交换结点的时候，把L移动到下一个结点了，所以不要
            //再执行：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;
            }

        }   
    }
}

好了，今天的就写到这里了，今天通过写交换结点，发现链表真的很容易忽悠人，我就被忽悠了一个小时，才知道那个结点已经被移动到下一个结点了。

最后，补充一个实现链表反转的好方法（感觉你在头文件里面计算一下链表的长度可以带来很多遍历的）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void rollback(Node * & head) {
    //先知道了最后一个元素和第一个元素的位置
    int end = head->value;
    int start = 1;
    //两边同时开工
    //进行调换
    while (1) {
        if (end == start)
            return;
        swap_node(head, end, start);
        --end;
        ++start;
    }
}

希望大家，对我写的代码做出一些评价。我想想还是直接贴个完成的代码出来好了，调转代码也在里面了

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
include<iostream>
#include<ctime>
#include<cstdlib>
#include<windows.h>
#include<algorithm>
using namespace std;
typedef int Elemtype;

//链式结构，我们打算在链表中添加一个
//保存长度的头结点，加入这个结点可以方便我们对结点做一些
//基本的操作，结点保存的是线性表的长度
struct Node
{
    //结点的值,如果是头结点，保存是链表的长度
    Elemtype value;
    //下一个结点的地址
    Node * next;

};

//创建一个空链表，每个头结点就代表一个链表
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;
}

//插入函数
bool Listinsert(Node * & head, int i, Elemtype value) {

    //插入到前面的方法
    int j = 0;
    Node * L = head;
    //如果插入的位置不合法，直接返回错误提示
    if (i<1 || i>head->value + 1)return false;

    //得到插入位置的前一个结点
    while (j < i - 1) {
        L = L->next;
        ++j;
    }

    //s是一个临时结点
    Node * s = new Node();
    s->value = value;    //先对临时结点赋值
    s->next = L->next;   //让临时结点下一个位置指向当前需要插入前一个结点的下一个位置
    L->next = s;          //让前一个结点下一个位置指向临时结点，完成
                          //线性表的长度加一
    ++head->value;
    return true;
}
//得到某个位置上的值
Node * getitem(Node * & head, int i) {
    //我们要求程序返回特定位置上的值
    //我们一样是从头结点开始寻找该位置
    int j = 0;
    Node * L = head;
    //想要的那个位置是否合法
    if (i<1 || i >head->value)return NULL;

    //同样是先得到前一个结点
    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;
            //如果前面的那个比后面的那个大，就交换它们之间的是数据域
            if (p->value > p1->value) {
                Elemtype temp = p->value;
                p->value = p1->value;
                p1->value = temp;
            }
            L = L->next;
        }
    }
}
//通过数组来完成我的排序
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];
    //变量链表，存放数组
    for (i = 0; i < head->value; i++) {
        L = L->next;
        copy[i] = L->value;
    }
    //调用STL中的sort函数
    sort(copy, copy + head->value);
    L = head;
    //存放回链表中
    for (i = 0; i < head->value; i++) {
        L = L->next;
        L->value = copy[i];
    }
}

//参数为头结点和需要交换的两个结点的位置（起点为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) {
        //位置靠前的那个结点的前一个结点
        Node * pre;
        if (i < j)
            pre = getitem(head, i);
        else
            pre = getitem(head, j);

        //保存第一个结点
        Node * a = pre->next;
        //保存第二结点
        Node * b = a->next;
        //改变pre下一个结点的值
        pre->next = b;
        //必须先把b的下一个结点值给a先
        a->next = b->next;
        //让b的下一个结点等于a
        b->next = a;
        return;
    }

    //第一个结点前一个结点
    Node * a = getitem(head, i);
    //第二个结点的前一个结点
    Node * b = getitem(head, j);
    //第一个结点
    Node * p = a->next;
    //第二个结点
    Node * q = b->next;
    //第一个结点的下一个结点
    Node * p_next = p->next;
    //第二结点的下一个结点
    Node * q_next = q->next;

    //a的下一个结点指向第二个结点q
    a->next = q;
    //第二结点的下一个结点指向第一个结点的下一个结点
    q->next = p_next;
    //b的下一个结点指向第一个结点p
    b->next = p;
    //第一个结点的下一个结点指向第二个结点的下一个结点
    p->next = q_next;

}
//反转
void rollback(Node * & head) {
    //先知道了最后一个元素和第一个元素的位置
    int end = head->value;
    int start = 1;
    //两边同时开工
    //进行调换
    while (1) {
        if (end <= start)
            return;
        swap_node(head, end, start);
        --end;
        ++start;
    }
}
void print(Node * & head);
//线性表的排序,采用冒泡排序,直接遍历链表
//线性表的排序，交换结点
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++) {
            //如果我们交换了结点，那么我们就已经在交换结点的时候，把L移动到下一个结点了，所以不要
            //再执行：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) {
    //输出我们只需要传入头结点，然后循环判断当前结点下一个结点是否为空，
    //这样就可以输出所有内容
    Node * L = head;
    while (L->next) {
        L = L->next;
        cout << L->value << " ";
    }
    cout << endl;
}
int main() {
    //链表的头结点，不存放任何值，首先初始化头结点
    Node * head;

    Node * head_array;
    Node * head_node;
    Node * head_roll;
    srand((int)time(NULL));     //每次执行种子不同，生成不同的随机数
    //创建一个链表

    InitList(head); 
    InitList(head_array);
    InitList(head_node);
    InitList(head_roll);

    int i;
    cout << "请输入需要插入元素个数" << 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 << "初始化结果" << endl;
    print(head);
    cout << "反转结果" << endl;
    rollback(head_roll);
    print(head_roll);
    cout << "冒泡排序（数据域交换）" << endl;
    Listsort(head);
    print(head);
    cout << "借数组为媒介进行排序（数据域交换）" << endl;
    Listsort_by_array(head_array);
    print(head_array);
    cout << "冒泡排序（结点交换）" << endl;
    Listsort_node(head_node);
    print(head_node);
    system("pause");
    return 0;

}

运行环境：vs2015

输出结果：

这里写图片描述

以上就是详解C++实现链表的排序算法的详细内容，更多关于C++ 链表排序算法的资料请关注靠谱客其它相关文章！

最后

以上就是殷勤哈密瓜最近收集整理的关于详解C++实现链表的排序算法的全部内容，更多相关详解C++实现链表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(121)

相关文章

详解Dijkstra算法之最短路径问题
详解Dijkstra算法之最短路径问题
详解c++良好的编程习惯与编程要点
详解c++良好的编程习惯与编程要点
详解C++实现拓扑排序算法
详解C++实现拓扑排序算法
浅谈C++性能榨汁机之伪共享
浅谈C++性能榨汁机之伪共享
详解C++实现链表的排序算法
详解C++实现链表的排序算法
详解windows下C/C++的内存泄露检测
详解windows下C/C++的内存泄露检测
C语言实现三子棋小游戏(vs2013多文件)
C语言实现三子棋小游戏(vs2013多文件)
C++中cout的格式使用详细介绍
C++中cout的格式使用详细介绍

评论列表共有 0 条评论

立即
投稿
返回
顶部