链表的快速排序（C/C++实现）

一、前言

大家在做需要排名的项目的时候，需要把各种数据从高到低排序。如果用的快速排序的话，处理数组是十分简单的。因为数组的存储空间的连续的，可以通过下标就可以简单的实现。但如果是链表的话，内存地址是随机分配的，不能像数组那样通过下标就直接实现。所以在这里给大家介绍一个简单实现的快速排序。

二、快速排序简单介绍

快速排序的是交换排序其中的一种，主要是采用分治的思想，每次迭代在当前区间中选取一个数作为哨兵，通过一系列的交换操作将当前区间分为左区间和右区间【使得左区间的值全部小于等于哨兵，右区间的值全部大于等于哨兵】。然后再对左区间、右区间执行这种划分区间的策略操作，当区间的长度为1时停止。等到所有分治的区间长度都为1时，此时的原数组就已经是一个排好序的数组了。代码如下:

void quickSort(int q[], int l, int r)
{// 当前区间的长度小于等于1时停止循环if (l >= r)  return;// 创建哨兵 midint mid = q[l];// 创建i，j指针进行移动int i = l, j = r;// 进行区间数字交换，使得左侧区间全小于等于mid，右侧区间全大于等于midwhile (i < j){// j指针从右向左移动，至到遇到第一个小于哨兵的值while (q[j] >= mid && i < j) j--;// 将该值移动到左区间中q[i] = q[j];// i指针从左向右移动，至到遇到第大个小于哨兵的值while (q[i] <= mid && i < j) i++;// 将该值移动到右区间中q[j] = q[i];}// 交换结束后此时i，j指针指向的同一个位置，即哨兵应该放的位置// 而左区间已经是全部小于等于哨兵的值,右区间已经是全部大于等于哨兵的值了。q[i] = mid;// 对划分出来的左右区间的再一次进行快排quickSort(q, l, i - 1);quickSort(q, i + 1, r);
}

但这只适用于连续存储空间。对于链表来说，不太适用。所以接下来我将介绍一个比较简单的代码来实现链表的快速排序。

三、代码实现：

（该链表是包含有头结点的，即第一个结点不放数据）：

// 自定义的结构体，用来存储链表的内容
typedef struct node
{int data = -1; // 数据域struct node* next = NULL; // 指针域，指向后一个元素struct node* pre = NULL; // 指针域，指向前一个元素
}NODE;//别名
// 函数声明
// 判断l是否走到了r的右边，如果在返回true，如果不在则返回false 【要求l和r在同一个链表上，且定义时l是r左侧的节点】
bool isRight(const NODE* l, const NODE* r);
// 判断l是否还在r的左边，如果在返回true，如果不在则返回false【要求l和r在同一个链表上，且定义时l是r左侧的节点】
bool isLeft(const NODE* l, const NODE* r);
// 在链表中挖出这个节点，即断开这个节点和链表的关系
NODE* dug(NODE* node);
// 在node所属的链表中，在node节点前插入target节点【此时target节点是一个孤立的节点，并没有链接链表】
void insertBefore(NODE* node, NODE* target);
// 在node所属的链表中，在node节点后插入target节点【此时target节点是一个孤立的节点，并没有链接链表】
void insertAfter(NODE* node, NODE* target);
// 进行快速排序
void quickSort(NODE* l, NODE* r) 
{// 如果当前区间的元素已经只剩一个或者不剩了，那么结束递归if (isRight(l, r)) {return;}// 记录当前区间的外的前一个节点和当前区间外的后一个节点，防止进行交换后这个区间的第一个节点和最后一个节点的顺序找不到了// 由于头节点的存在，可以保证该区间外一定存在前一个节点NODE* preL = l->pre;// 但是不一定该区间外是否还有后一个节点NODE* nextR;bool tailDug = false; //标记是否给该区间外创建了后一个节点// 如果该区间外没有后一个节点了if (r->next == NULL) {// 则创建一个新的节点用来记录区间的最后一个节点nextR = (NODE*)malloc(sizeof(NODE));r->next = nextR;nextR->pre = r;nextR->next = NULL;tailDug = true;} // 如果该区间外后面还有一个节点，则直接使用这个节点来帮助记录区间的末尾节点else{nextR = r->next;}// 选择哨兵节点【区间的第一个节点】NODE* mid = dug(l);// 更新左、右指针的位置NODE* i = preL->next, * j = nextR->pre;// 进行快排的交换移动// 当左指针还在右指针的左侧时，进行交换判断while (isLeft(i, j)){// 右指针左移，至到遇到第一个小于哨兵的节点或者i，j指针相遇了，那么就停下while (j->data >= mid->data && isLeft(i, j)) { j = j->pre; }NODE* temp = NULL;// 如果此时i，j指针还未相遇，则右指针当前指向的节点是小于哨兵的节点，需要移动到左区间中。【说明它满足的上面while的 j->data >= mid->data】if (isLeft(i, j)) {// j指针前移一位，因为上面的判断已经知道当前这个节点应该放在左区间了，故下一次判断时j指针不需要判断这个节点了，直接从前一个节点开始判断即可。j = j->pre;// 将刚才j指针找到的节点移动到i节点前面，【因为i节点的左侧都应该是小于等于哨兵值的节点】temp = j->next;dug(temp);insertBefore(i, temp);}// 左指针右移，至到遇到第一个大于哨兵的节点或者i，j指针相遇了，那么就停下while (i->data <= mid->data && isLeft(i, j)) { i = i->next; }// 如果此时i，j指针还未相遇，则左指针当前指向的节点是大于哨兵的节点，需要移动到右区间中。【说明它满足的上面while的 i->data <= mid->data 】if (isLeft(i, j)) {// i指针后移一位，因为上面的判断已经知道当前这个节点应该放在右区间了，故下一次判断时i指针不需要判断这个节点了，直接从后一个节点开始判断即可。i = i->next;// 将刚才i指针找到的节点移动到j节点后面，【因为j节点的右侧都应该是大于等于哨兵值的节点】temp = i->pre;dug(temp);insertAfter(j, temp);}}// 此时的i，j指针已经相遇了，故下面使用到i的地方都可以替换为j// 最后一次填坑,此时只剩哨兵这个节点的位置需要重新放进来了。// 如果当前节点小于哨兵，则代表当前相遇位置的节点【i，j】是左区间的最后一个节点，那么哨兵应该放在该节点的右侧if (i->data < mid->data) {insertAfter(i, mid);//当前相遇的节点【i，j】代表左区间的最后一个元素，故放在该节点后面即代表放在了左区间和右区间的正中间} // 否则代表当前相遇位置的节点【i，j】是右区间的第一个节点，那么哨兵应该放在该节点的左侧else {insertBefore(i, mid);//当前相遇的节点【i，j】代表右区间的第一个元素，故放在该节点前面即代表放在了左区间和右区间的正中间}// 更新这个区间的区间内的第一个节点和最后一个节点l = preL->next;r = nextR->pre;// 如果区间外的后一个节点实际上是不存在的，那么删除这个被我们临时创建出来的节点if (tailDug) {dug(nextR);}// 进行左右区间的快排quickSort(l, mid->pre), quickSort(mid->next, r);
}
// 函数实现
bool isRight(const NODE* l, const NODE* r)
{return l == NULL || r == NULL || l == r || l == r->next;
}
bool isLeft(const NODE* l, const NODE* r)
{return !isRight(l, r);//如果不在右边，则代表在左边
}
NODE* dug(NODE* node)
{// 如果当前节点在链表中是最后一个节点if (node->next == NULL){// 则将前一个节点指向NULL即可NODE* l = node->pre;l->next = NULL;return node;}// 如果当前节点不是最后一个节点else{// 将当前节点在链表中的前一个节点与当前节点在链表中的后一个节点联系起来NODE* l = node->pre;NODE* r = node->next;l->next = r;r->pre = l;// 断开当前节点与链表的联系node->pre = NULL;node->next = NULL;return node;}
}
void insertBefore(NODE* node, NODE* target)
{// 获取链表中node的前一个节点NODE* l = node->pre;// 将target节点插入到 l 节点和 node 节点之间l->next = target;node->pre = target;target->pre = l;target->next = node;
}
void insertAfter(NODE* node, NODE* target)
{// 获取链表中node的后一个节点NODE* r = node->next;// 将target节点插入到 node 节点和 r 节点之间r->pre = target;node->next = target;target->pre = node;target->next = r;
}

四、分析讲解

假设需要排序的链表数据为：2 3 6 1 9。那么链表的结构如下：

4.1 第一个递归过程

4.1.1 数据预处理

4.1.1.1 需要处理的链表结点【区间数据】

4.1.1.2 本次递归的结点介绍【未获取哨兵结点之前】

提示：由于需要处理的区间结点的最后一个结点9 后面不再有结点，故需要 创建一个新的结点nextR 插入在9这个结点后面，这样就可以精准的找到我们这个区间的最后一个数据结点的位置【由于nextR这个结点是不会进行位置交换的，故nextR的前一个结点一定是当前区间的最后一个数据结点】。

4.1.1.3 获取哨兵结点

提示：哨兵结点mid是一般取的是区间的第一个结点，即2这个结点。而本文的快速排序会将哨兵结点从链表中挖出去，这样可以方便后续的处理。故现在区间结点只有四个数据了，即3 6 1 9。

4.1.1.4 本次递归所有结点介绍

结点介绍：
mid：哨兵结点，用于确定其他每个结点的位置，来使得其他结点进行移动。
l：区间的第一个结点，一般只在初始化其他结点的时候用到。
r：区间的最后一个结点，一般只在初始化其他结点的时候用到。
preL：区间第一个结点的前一个结点，由于位置不会发生改变，故用来找区间的第一个结点。
nextR：区间最后一个结点的后一个结点，由于位置不会发生改变，故用来找区间的最后一个结点。
i：从区间的第一个结点向区间的最后一个结点进行移动，用于每一次循环移动数据的结点判断。
j：从区间的最后一个结点向区间的第一个结点进行移动，用于每一次循环移动数据的结点判断。

4.1.2 循环移动数据

4.1.2.1 第一次循环结果

目的：第一次循环，判断j所在的结点是否需要移动位置。
过程：
第一步： j当前所在的结点是9,由于9大于哨兵结点2,故当前结点不需要移动，j结点向左移动，此时j结点成为了1结点。
第二步： j当前所在的结点是1,由于1小于于哨兵结点2,故当前结点需要移动。将当前j所在的结点【1结点】移动到i所在的结点【3结点】前面。让j的位置仍然保持距离区间最后一个结点的距离不变，那么此时j所指向的结点即为6结点。【因为从区间结尾开始处理的话，此时只有9结点正常通过判断确定了位置，但是6结点还未通过判断确定位置，那么j就应该指向区间最后一个未确认位置的结点】

4.1.2.2 第二次循环结果

目的：第二次循环，判断i所在的结点是否需要移动位置。
过程：
第一步： i当前所在的结点是3,由于3大于哨兵结点2,故当前结点需要移动。将当前i所在的结点【3结点】移动到j所在的结点【6结点】后面。让i的位置仍然保持距离区间第一个结点的距离不变，那么此时i所指向的结点即为6结点。【因为从区间开始开始处理的话，此时只有1结点正常通过判断确定了位置，但是6结点还未通过判断确定位置，那么i就应该指向区间第一个未确认位置的结点】

4.1.2.3 第三次循环结果

目的：由于i、j指针已经相遇，那么目前只需要确定哨兵结点的位置，本轮循环就结束了。
过程：由于快排算法的性质决定了，i指针左侧的结点都小于哨兵结点的值，j指针右侧结点的值都大于哨兵结点的值。故我们比较一下当前i结点（或者j结点，因为每次循环到了最后一步的时候，i和j结点都会相遇）的值和哨兵结点的值的大小。由于i结点6大于哨兵结点2，那么哨兵结点2就需要插入到链表中i结点6的左侧。此时本轮位置移动已经完成，哨兵结点2的左侧结点均为小于哨兵结点值的结点，哨兵结点2的右侧结点均为大于哨兵结点值的结点。

4.1.2.4 下一次循环的区间划分

目的：本轮位置移动已经完成了，已经确定了结点2的位置，但其他结点的位置还未确定，还需要继续进行分冶结点2两侧的区间进行快排位置移动。
过程：最开始指向区间头、尾的结点的l和r，在进行了无数次交换了，我们可以发现它们已经不在区间的第一个结点和最后一个结点了。但由于preL和nextR结点始终没有移动过位置，preL的下一个结点一直指向的是区间的第一个结点【目前指向的结点1，即快排结束后区间的第一个结点】，nextR的上一个结点一直指向的是区间的最一个结点【目前指向的结点9，即快排结束后区间的最后一个结点】。故我们可以确定需要继续进行快排的两个区间为：preL->next, mid->pre、mid->next, nextR->pre。【即(preL的下一个结点，哨兵结点的上一个结点)、(哨兵结点的下一个结点，nextR的上一个结点)】。而哨兵结点已经确定好在整个链表的位置了，故不需要参与后续的其他区间迭代的位置移动了。而由于此时nextR结点是创建的新结点，在原因链表中不需要，在最后我们将该结点从链表中删掉即可。
故下一轮的递归区间为：

五、可运行的完整代码：

#include<stdio.h>
#include<stdlib.h>// 自定义的结构体，用来存储链表的内容
typedef struct node
{int data = -1; // 数据域struct node* next = NULL; // 指针域，指向后一个元素struct node* pre = NULL; // 指针域，指向前一个元素
}NODE;//别名// 找到链表的最后一个节点
NODE* findTail(NODE* head) 
{while (head->next != NULL) { //当没有下一个元素的时候，就代表当前元素是链表的最后一个元素head = head->next;}return head;
}// 给链表新增节点
void add(NODE* head, int data)
{NODE* tail = findTail(head); //获取链表的最后一个节点// 创建新节点NODE* p = (NODE*)malloc(sizeof(NODE));// p 为新增的结点p->data = data; // 把值赋给p中的data域p->next = NULL; // 初始化操作，p是最后一个节点，故没有下一个节点了，因此next指针域需要指向NULL// 将新创建的结点与当前链表创建关联p->pre = tail; //新节点左指针域应该指向链表中的最后一个节点tail->next = p; //链表中最后一个节点的右指针域应该指向这个新节点。【至此新节点成功加入到链表中】
}// 判断l是否走到了r的右边，如果在返回true，如果不在则返回false 【要求l和r在同一个链表上，且定义时l是r左侧的节点】
bool isRight(const NODE* l, const NODE* r) 
{return l == NULL || r == NULL || l == r || l == r->next;
}// 判断l是否还在r的左边，如果在返回true，如果不在则返回false【要求l和r在同一个链表上，且定义时l是r左侧的节点】
bool isLeft(const NODE* l, const NODE* r) 
{return !isRight(l, r);//如果不在右边，则代表在左边
}// 在链表中挖出这个节点，即断开这个节点和链表的关系
NODE* dug(NODE* node) 
{// 如果当前节点在链表中是最后一个节点if (node->next == NULL) {// 则将前一个节点指向NULL即可NODE* l = node->pre;l->next = NULL;return node;}// 如果当前节点不是最后一个节点else {// 将当前节点在链表中的前一个节点与当前节点在链表中的后一个节点联系起来NODE* l = node->pre;NODE* r = node->next;l->next = r;r->pre = l;// 断开当前节点与链表的联系node->pre = NULL;node->next = NULL;return node;}
}// 在node所属的链表中，在node节点前插入target节点【此时target节点是一个孤立的节点，并没有链接链表】
void insertBefore(NODE* node, NODE* target)
{// 获取链表中node的前一个节点NODE* l = node->pre;// 将target节点插入到 l 节点和 node 节点之间l->next = target;node->pre = target;target->pre = l;target->next = node;
}// 在node所属的链表中，在node节点后插入target节点【此时target节点是一个孤立的节点，并没有链接链表】
void insertAfter(NODE* node, NODE* target)
{// 获取链表中node的后一个节点NODE* r = node->next;// 将target节点插入到 node 节点和 r 节点之间r->pre = target;node->next = target;target->pre = node;target->next = r;
}// 进行快速排序
void quickSort(NODE* l, NODE* r) 
{// 如果当前区间的元素已经只剩一个或者不剩了，那么结束递归if (isRight(l, r)) {return;}// 记录当前区间的外的前一个节点和当前区间外的后一个节点，防止进行交换后这个区间的第一个节点和最后一个节点的顺序找不到了// 由于头节点的存在，可以保证该区间外一定存在前一个节点NODE* preL = l->pre;// 但是不一定该区间外是否还有后一个节点NODE* nextR;bool tailDug = false; //标记是否给该区间外创建了后一个节点// 如果该区间外没有后一个节点了if (r->next == NULL) {// 则创建一个新的节点用来记录区间的最后一个节点nextR = (NODE*)malloc(sizeof(NODE));r->next = nextR;nextR->pre = r;nextR->next = NULL;tailDug = true;} // 如果该区间外后面还有一个节点，则直接使用这个节点来帮助记录区间的末尾节点else{nextR = r->next;}// 选择哨兵节点【区间的第一个节点】NODE* mid = dug(l);// 更新左、右指针的位置NODE* i = preL->next, * j = nextR->pre;// 进行快排的交换移动// 当左指针还在右指针的左侧时，进行交换判断while (isLeft(i, j)){// 右指针左移，至到遇到第一个小于哨兵的节点或者i，j指针相遇了，那么就停下while (j->data >= mid->data && isLeft(i, j)) { j = j->pre; }NODE* temp = NULL;// 如果此时i，j指针还未相遇，则右指针当前指向的节点是小于哨兵的节点，需要移动到左区间中。【说明它满足的上面while的 j->data >= mid->data】if (isLeft(i, j)) {// j指针前移一位，因为上面的判断已经知道当前这个节点应该放在左区间了，故下一次判断时j指针不需要判断这个节点了，直接从前一个节点开始判断即可。j = j->pre;// 将刚才j指针找到的节点移动到i节点前面，【因为i节点的左侧都应该是小于等于哨兵值的节点】temp = j->next;dug(temp);insertBefore(i, temp);}// 左指针右移，至到遇到第一个大于哨兵的节点或者i，j指针相遇了，那么就停下while (i->data <= mid->data && isLeft(i, j)) { i = i->next; }// 如果此时i，j指针还未相遇，则左指针当前指向的节点是大于哨兵的节点，需要移动到右区间中。【说明它满足的上面while的 i->data <= mid->data 】if (isLeft(i, j)) {// i指针后移一位，因为上面的判断已经知道当前这个节点应该放在右区间了，故下一次判断时i指针不需要判断这个节点了，直接从后一个节点开始判断即可。i = i->next;// 将刚才i指针找到的节点移动到j节点后面，【因为j节点的右侧都应该是大于等于哨兵值的节点】temp = i->pre;dug(temp);insertAfter(j, temp);}}// 此时的i，j指针已经相遇了，故下面使用到i的地方都可以替换为j// 最后一次填坑,此时只剩哨兵这个节点的位置需要重新放进来了。// 如果当前节点小于哨兵，则代表当前相遇位置的节点【i，j】是左区间的最后一个节点，那么哨兵应该放在该节点的右侧if (i->data < mid->data) {insertAfter(i, mid);//当前相遇的节点【i，j】代表左区间的最后一个元素，故放在该节点后面即代表放在了左区间和右区间的正中间} // 否则代表当前相遇位置的节点【i，j】是右区间的第一个节点，那么哨兵应该放在该节点的左侧else {insertBefore(i, mid);//当前相遇的节点【i，j】代表右区间的第一个元素，故放在该节点前面即代表放在了左区间和右区间的正中间}// 更新这个区间的区间内的第一个节点和最后一个节点l = preL->next;r = nextR->pre;// 如果区间外的后一个节点实际上是不存在的，那么删除这个被我们临时创建出来的节点if (tailDug) {dug(nextR);}// 进行左右区间的快排quickSort(l, mid->pre), quickSort(mid->next, r);
}int main()
{NODE* head = (NODE*)malloc(sizeof(NODE));//定义头结点int n;//链表的长度printf("请输入链表的长度: ");scanf("%d", &n);printf("请输入链表中的数字: ");for (int i = 0; i < n; i++){int x;//每一个结点的值scanf("%d", &x);add(head, x);//向链表追加结点}//进行冒泡排序quickSort(head->next, findTail(head));NODE* p = head->next;//因为第一个结点没有存放数据，所以从第二个结点开始输出while (p != NULL){printf("%d\t", p->data);p = p->next;}return 0;
}

**

温馨提示：第一个结点不是用来放数据的，是用来辅助完成排序的。

题目测试地址：C语言网-快速排序题目测试

**

相关文章

快速排序（C/C++实现）—— 简单易懂系列
单链表的冒泡排序（C/C++实现）