上节介绍了链表的基本操作 [史上最全单链表的增删改查反转等操作汇总以及 5 种排序算法(C 语言)]()
这节介绍链表的 5 种排序算法。
@[TOC]
0. 稳固排序和原地排序的定义
稳固排序 ：
假设在待排序的记录序列中，存在多个具备雷同的关键字的记录，若通过排序，这些记录的 绝对秩序放弃不变 ，即在原序列中，ri=rj，且 ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之前，则称这种排序算法是稳固的；否则称为不稳固的。像 冒泡排序 ， 插入排序 ， 基数排序 ， 归并排序 等都是稳固排序
原地排序 ：
基本上 不须要额定辅助的的空间，容许大量额定的辅助变量 进行的排序。就是在原来的排序数组中比拟和替换的排序。像 抉择排序 ， 插入排序 ， 希尔排序 ， 疾速排序 ， 堆排序 等都会有一项比拟且替换操作 (swap(i,j)) 的逻辑在其中，因而他们都是属于原地 (旧址、就地) 排序，而合并排序，计数排序，基数排序等不是原地排序
1. 冒泡排序
根本思维:
把第一个元素与第二个元素比拟，如果第一个比第二个大，则替换他们的地位。接着持续比拟第二个与第三个元素，如果第二个比第三个大，则替换他们的地位 ….
咱们对每一对相邻元素作同样的工作，从开始第一对到结尾的最初一对，这样一趟比拟替换下来之后，排在最右的元素就会
是最大的数。除去最右的元素，咱们对残余的元素做同样的工作，如此反复上来，直到排序实现。
具体步骤 ：
1. 比拟相邻的元素。如果第一个比第二个大，就替换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最初一对。这步做完后，最初的元素会是最大的数。
3. 针对所有的元素反复以上的步骤，除了最初一个。
4. 继续每次对越来越少的元素反复下面的步骤，直到没有任何一对数字须要比拟。
工夫复杂度 ：O(N2)
空间复杂度 ：O(1)
稳固排序 : 是
原地排序: 是
Node *BubbleSort(Node *phead)
{
Node * p = phead;
Node * q = phead->next;
/* 有几个数据就 -1；比方 x 个 i <x-1*/
for(int i=0;i<5;i++)
{while((q!=NULL)&&(p!=NULL))
{if(p->data>q->data)
{
/* 头结点和下一节点的替换，要非凡解决，更新新的头 head*/
if (p == phead)
{
p->next = q->next;
q->next = p;
head = q;
phead = q;
/* 这里切记要把 p,q 换回来，失常的话 q 应该在 p 的后面，进行的是 p,q 的比拟
* 然而通过指针域替换之后就变成 q,p. 再次进行下一次比拟时，* 就会变成 q,p 的数据域比拟。如果本来 p ->data > q->data, 则进行替换。变成 q ->data 和 p ->data 比拟，* 不会进行替换，所以排序就会谬误。有趣味的能够调试下。*/
Node*temp=p;
p=q;
q=temp;
}
/* 解决两头过程，其余数据的替换状况，要寻找前驱节点 if (p != phead)*/
else
{
/*p，q 的那个在前，那个在后。指针域的连贯画图好了解一点 */
if (p->next == q)
{
/* 寻找 p 的前驱节点 */
Node *ppre = FindPreNode(p);
/* 将 p 的下一个指向 q 的下一个 */
p->next = q->next;
/* 此时 q 为头结点，让 q 的下一个指向 p，连接起来 */
q->next = p;
/* 将原来 p 的前驱节点指向当初的 q，当初的 q 为头结点 */
ppre->next = q;
Node*temp=p;
p=q;
q=temp;
}
else if (q->next == p)
{Node *qpre = FindPreNode(q);
q->next = p->next;
p->next = q;
qpre->next = p;
Node*temp=p;
p=q;
q=temp;
}
}
}
/* 地址挪动 */
p = p->next;
q = q->next;
}
/* 进行完一轮比拟后，从头开始进行第二轮 */
p = phead;
q = phead->next;
}
head = phead;
return head;
}2. 疾速排序
根本思维
咱们从数组中抉择一个元素，咱们把这个元素称之为中轴元素吧，而后把数组中所有小于中轴元素的元素放在其右边，
所有大于或等于中轴元素的元素放在其左边，显然，此时中轴元素所处的地位的是有序的。也就是说，咱们无需再挪动中轴
元素的地位。
从中轴元素那里开始把大的数组切割成两个小的数组 (两个数组都不蕴含中轴元素)，接着咱们通过递归的形式，让中轴元素
右边的数组和左边的数组也反复同样的操作，直到数组的大小为 1，此时每个元素都处于有序的地位。
具体步骤 ：
1. 从数列中挑出一个元素，称为 “ 基准 ”（pivot）;
2. 从新排序数列，所有元素比基准值小的摆放在基准后面，所有元素比基准值大的摆在基准的前面（雷同的数能够到任一边）。在这个分区退出之后，该基准就处于数列的两头地位。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
工夫复杂度 ：O(NlogN)
空间复杂度 ：O(logN)
稳固排序 ：否
原地排序：是
int *QuickSort(Node* pBegin, Node* pEnd)
{if(pBegin == NULL || pEnd == NULL || pBegin == pEnd)
return 0;
// 定义两个指针
Node* p1 = pBegin;
Node* p2 = pBegin->next;
int pivot = pBegin->data;
// 每次只比拟小的，把小的放在后面。通过一轮比拟后，被分成左右两局部。其中 p1 指向中值处，pbegin 为 pivot。while(p2 != NULL)/* && p2 != pEnd->next */
{if(p2->data < pivot)
{
p1 = p1->next;
if(p1 != p2)
{SwapData(&p1->data, &p2->data);
}
}
p2 = p2->next;
}
/* 此时 pivot 并不在两头，咱们要把他放到两头，以他为基准，把数据分为左右两边 */
SwapData(&p1->data, &pBegin->data);
// 此时 p1 是中值节点
//if(p1->data >pBegin->data)
QuickSort(pBegin, p1);
//if(p1->data < pEnd->data)
QuickSort(p1->next, pEnd);
}3. 插入排序
根本思维 : 每一步将一个待排序的记录，插入到后面曾经排好序的有序序列中去，直到插完所有元素为止。
具体步骤 ：
1. 将待排序序列第一个元素看做一个有序序列，把第二个元素到最初一个元素当成是未排序序列；
2. 取出下一个元素，在曾经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一地位；
4. 反复步骤 3，直到找到已排序的元素小于或者等于新元素的地位；
5. 将新元素插入到该地位后；
6. 反复步骤 2~5。
工夫复杂度 ：O(N2)
空间复杂度 ：O(1)
稳固排序 ：是
原地排序：是
/* 不好了解能够调试下看下具体过程 */
Node *InsertSort(Node *phead)
{
/* 为原链表剩下用于间接插入排序的节拍板指针 */
Node *unsort;
/* 长期指针变量：插入节点 */
Node *t;
/* 长期指针变量 */
Node *p;
/* 长期指针变量 */
Node *sort;
/* 原链表剩下用于间接插入排序的节点链表：可依据图 12 来了解。*/
unsort = phead->next;
/* 只含有一个节点的链表的有序链表：可依据图 11 来了解。*/
head->next = NULL;
/* 遍历剩下无序的链表 */
while (unsort != NULL)
{
/* 留神：这里 for 语句就是体现间接插入排序思维的中央 */
/* 无序节点在有序链表中找插入的地位 */
/* 跳出 for 循环的条件：*1.sort 为空，此时，sort->data < t->data，p 存下地位，应该放在有序链表的前面
*2.sort->data > t->data，跳出循环时，t->data 放在有序链表 sort 的后面
*3.sort 为空 sort->data > t->data，也插入在 sort 后面的地位
*/
/* q 为有序链表 */
for (t = unsort, sort = phead; ((sort != NULL) && (sort->data < t->data)); p = sort, sort = sort->next);
/* 退出 for 循环，就是找到了插入的地位插入地位要么在后面，要么在前面 */
/* 留神：按情理来说，这句话能够放到上面正文了的那个地位也应该对的，然而就是不能。起因：你若了解了下面的第 3 条，就晓得了。*/
/* 无序链表中的第一个节点来到，以便它插入到有序链表中。*/
unsort = unsort->next;
/* 插在第一个节点之前 */
/*sort->data > t->data*/
/*sort 为空 sort->data > t->data*/
if (sort == phead)
{
/* 整个无序链表给 phead*/
phead = t;
}
/* p 是 sort 的前驱，这样说不太确切，当 sort 到最初时，for 外面有个 sort = sort->next，* 就会把 sort 置空，所以要用 p 暂存上一次 sort 的值。而且执行判断 sort->data < t->data 时，用的也是上一次的 sort
*/
/*sort 前面插入 */
/*sort 遍历到了最初，此时，sort->data < t->data,sort 和 p 都为最初一个元素。*/
else
{p->next = t;}
/*if 解决之后，t 为无序链表，因为要在 phead 前插入。这里先把 t 赋值给 phead，再把 t 的 next 指向 sort，* 就实现了在 sort 之前插入小的元素，很奇妙的一种办法
*else 解决完之后，sort 寄存的是 sort 的下一次，真正的 sort 寄存在 p 中。不满足条件跳出循环时，判断的是下一次的 sort，然而咱们要用的插入的地位为上一次的 sort，所以要记录下 sort 上一次的地位
*/
/* 实现插入动作 */
/* 当 sort 遍历实现为空时，t->next 就是断开前面的元素（sort 为空）*/
/* 当 sort 不为空时，sort->data > t->data，sort 寄存的元素比 t 要大，放在前面，t->next 就是再链接起来 sort*/
t->next = sort;
/*unsort = unsort->next;*/
}
head = phead;
return phead;
} 4. 抉择排序
根本思维 ：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素替换地位(如果第一个元素就是最小元素那么它就和本人替换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素替换地位。如此往返，直到将整个数组排序。这种办法咱们称之为抉择排序。
具体步骤 ：
1. 首先在未排序序列中找到最小（大）元素，寄存到排序序列的起始地位。
2. 再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端。
3. 反复第二步，直到所有元素均排序结束。
工夫复杂度 ：O(N2)
空间复杂度 ：O(1)
稳固排序 ：否
原地排序：是
Node* SelectSort(Node* phead)
{
Node *temp;
Node *temphead = phead;
/* 将第一次的最大值设置为头结点 */
int max = phead->data;
/* 替换变量 */
for(int i = 0;i<LengthList(phead);i++)
{
/* 每次遍历开始前都要把最大值设置为头结点 */
max = phead->data;
while (temphead->next !=NULL)
{
/* 寻找最大值 */
if(max < temphead->next->data)
{max = temphead->next->data;}
/* 挪动指针地位 */
temphead = temphead->next;
}
/* 找到最大值的地位 */
temp = FindList(max);
/* 判断最大值是否和头节点雷同 */
if(phead != temp)
{SwapNode(phead,temp);
}
/* 更新下一次遍历的头结点 */
temphead = temp->next;
phead = temphead;
}
} SwapNode 相干代码如下。过后思考只须要了解排序思维就好了，就没有把这个函数的代码放进去。这个代码写的太长太简单了，有工夫我会从新精简下。（说实话，我都快忘了怎么写的了）
/* 替换相邻节点 */
void Swanext(Node *p,Node *q)
{
/* 两头相邻节点 */
if ((p != head)&&(q != head))
{
// /* p 为前一个节点，q 的前驱为 p */
// /* 寻找 p 的前驱结点 */
// Node *ppre = FindPreNode(p);
// Node *temp;
// /* 暂存 p 节点的后继结点，指向 q */
// temp = p->next;
// /* 将 q 节点的后继节点赋值给 p 的后继结点，行将 p 节点放到了 q 地位（此时 q 的前驱节点的 next 指针还指向的是 q）*/
// p->next = q->next;
// /* 将 p 节点给 q 的 next，行将实现了 q 与 p 的从新连贯 */
// q->next =p;
// /* 找到原来 p 的前驱节点，指向 q，即实现了原来 p 的前驱结点和 q 节点的连贯 */
// ppre->next =q;
if (p->next == q)
{Node *ppre = FindPreNode(p);
p->next = q->next;
q->next = p;
ppre->next = q;
// PrintList(head);
}
else if (q->next == p)
{Node *qpre = FindPreNode(q);
q->next = p->next;
p->next = q;
qpre->next = p;
}
}
/* 头结点相邻的替换 */
else
{if(p == head)
{
p->next = q->next;
q->next = p;
head = q;
}
else
{
q->next = p->next;
p->next = q;
head = p;
}
}
}
/* 替换头结点和任意节点(除尾节点外)*/
void SwapHeadAnother(Node *tmphead,Node *p)
{
/* 寻找 p 的前驱节点 */
Node *ppre = FindPreNode(p);
Node *temp;
if(p!=tmphead->next)
{
/* 暂存 p 节点 */
temp = p->next;
/* 将 tmphead 节点的后继节点赋值给 p 的后继结点，行将 tmphead 节点放到了 p 地位（此时 p 的前驱节点的 next 指针还未断开）*/
p->next = tmphead->next;
/* 将 p 的后继结点赋值给 tmphead 的后继结点，同时连贯 p 的前驱和 tmphead*/
tmphead->next = temp;
ppre->next =tmphead;
/* 新的头结点返回给全局 head*/
head = p;
}
else
{
/* 头结点和下一节点 */
tmphead->next = p->next;
p->next = tmphead;
head = p;
}
}
/* 替换尾结点和任意节点(除头节点外)*/
void SwapEndAnother(Node *tmpend,Node *p)
{
/* 寻找 p 的前驱节点 */
Node *ppre = FindPreNode(p);
Node *endpre = FindPreNode(tmpend);
Node *temp;
if((tmpend==end)&&(p!=tmpend))
{
/* 暂存 p 节点 */
temp = p->next;
/* 将 tmpend 节点的后继节点赋值给 p 的后继结点，行将 tmpend 节点放到了 p 地位（此时 p 的前驱节点的 next 指针还未断开）*/
p->next = tmpend->next;
endpre->next = p;
/* 将 p 的后继结点赋值给 tmpend 的后继结点，同时连贯 p 的前驱和 tmpend（断开了之前的连贯）*/
tmpend->next = temp;
ppre->next =tmpend;
/* 新的头结点返回给全局 head*/
end = p;
}
else
{
p->next = tmpend->next;
tmpend->next = p;
end = p;
}
}
/* 替换头结点和尾节点 */
void SwapHeadEnd(Node *tmphead,Node *tmpend)
{
/* 寻找 tmpend 的前驱节点 */
Node *endpre = FindPreNode(tmpend);
Node *temp;
/* 暂存 tmpend 节点 */
temp = tmpend->next;
/* 将 tmphead 节点的后继节点赋值给 tmpend 的后继结点，行将 tmpend 节点放到了 tmphead 地位（此时 tmpend 的前驱节点的 next 指针还未断开）*/
tmpend->next = tmphead->next;
/* 将 p 的后继结点赋值给 tmpend 的后继结点，同时连贯 p 的前驱和 tmpend（断开了之前的连贯）*/
tmphead->next = temp;
endpre->next =tmphead;
/* 新的头结点返回给全局 head*/
head = tmpend;
end = tmphead;
// PrintList(tmpend);
}
void SwapRandom(Node *p,Node *q)
{
/* 除了首尾节点，两头不相邻的两个节点 */
if((p->next != q)||(q->next != p))
{
/* 寻找前驱结点 */
Node *ppre = FindPreNode(p);
Node *qpre = FindPreNode(q);
/* 借助一个两头节点传递数据域 */
Node *temp;
temp = p->next;
/* 替换 p 和 q */
/*2、p 的新后继结点要变成 q 的原后继结点 */
p->next = q->next;
/*3、q 的原前趋结点（qpre）的新后继结点要变成 p */
qpre->next = p;
/*4、q 的新后继结点要变成 p 的原后继结点（p->next）*/
q->next = temp;
/*1、p 的原前趋结点（ppre）的新后继结点要变成 q */
ppre->next = q;
}
/* 两头相邻节点的解决 */
else if (p->next == q)
{Node *ppre = FindPreNode(p);
p->next = q->next;
q->next = p;
ppre->next = q;
}
else if (q->next == p)
{Node *qpre = FindPreNode(q);
q->next = p->next;
p->next = q;
qpre->next = p;
}
}
/* 替换任意两个节点 */
void SwapNode(Node*p, Node*q)
{// if(LengthList(head)<2)
// printf("Can not swap!The Length of list is:%d\r\n",LengthList(head));
/* 查看是否是头尾节点 */
/* 对于头尾节点有四种状况
*1.p 头节点和 q 为两头节点
*2.p 尾节点和 q 为两头节点
*3.q 头节点和 p 为两头节点
*4.q 尾节点和 p 为两头节点
*5.p 头结点和 q 尾节点
*6.q 头结点和 p 尾节点
*7. 其余两头替换的状况
*/
/*2. 两个节点是否相邻 除去头结点和下一节点相邻的状况，放在 headanother 解决 */
if((p->next == q)&&(p !=head)&&(q !=head))
Swanext(p,q);
else if((q->next == p)&&(p !=head)&&(q !=head))
Swanext(q,p);
/*1.p 头节点和 q 为两头节点 */
else if((p == head)&&(q != end))
SwapHeadAnother(p,q);
/*2.p 尾节点和 q 为两头节点 */
else if ((p == end)&&(q != head))
SwapEndAnother(p,q);
/*3.q 头节点和 p 为两头节点 */
else if((q == head)&&(p != end))
SwapHeadAnother(q,p);
/*4.q 尾节点和 p 为两头节点 */
else if((q == end)&&(p != head))
SwapEndAnother(q,p);
/*5.p 头结点和 q 尾节点 */
else if((p == head)&&(q == end))
SwapHeadEnd(p,q);
/*6.q 头结点和 p 尾节点 */
else if((q == head)&&(p == end))
SwapHeadEnd(q,p);
/*7. 其余两头替换的状况 */
else
SwapRandom(p,q);
}5. 归并排序
根本思维 ：归并排序是建设在归并操作上的一种无效的排序算法。该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用。
作为一种典型的分而治之思维的算法利用，归并排序的实现由两种办法：
自上而下的递归（所有递归的办法都能够用迭代重写，所以就有了第 2 种办法）；
自下而上的迭代；
具体步骤 ：
1. 申请空间，使其大小为两个曾经排序序列之和，该空间用来寄存合并后的序列；
2. 设定两个指针，最后地位别离为两个曾经排序序列的起始地位；
3. 比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间，并挪动指针到下一地位；
4. 反复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素间接复制到合并序列尾。
工夫复杂度 ：O(NlogN)
空间复杂度 ：O(N)
稳固排序 ：是
原地排序：否
/* 获取链表两头元素 */
Node *getMiddleNode(Node *pList)
{if (pList == NULL)
{return NULL;}
Node *pfast = pList->next;
Node *pslow = pList;
while (pfast != NULL)
{
pfast = pfast->next;
if (pfast != NULL)
{
pfast = pfast->next;
pslow = pslow->next;
}
}
return pslow;
}
/* 合并有序链表，合并之后升序排列 */
Node *MergeList(Node *p1, Node *p2)
{if (NULL == p1)
{return p2;}
if (NULL == p2)
{return p1;}
Node *pLinkA = p1;
Node *pLinkB = p2;
Node *pTemp = NULL;
/* 较小的为头结点，pTemp 存下头结点 */
if (pLinkA->data <= pLinkB->data)
{
pTemp = pLinkA;
pLinkA = pLinkA->next;
}
else
{
pTemp = pLinkB;
pLinkB = pLinkB->next;
}
/* 初始化头结点，即头结点指向不为空的结点 */
Node *pHead = pTemp;
while (pLinkA && pLinkB)
{
/* 合并先放小的元素 */
if (pLinkA->data <= pLinkB->data)
{
pTemp->next = pLinkA;
/* 保留下上一次节点。如果下一次为 NULL，保留的上一次的节点就是链表最初一个元素 */
pTemp = pLinkA;
pLinkA = pLinkA->next;
}
else
{
pTemp->next = pLinkB;
pTemp = pLinkB;
pLinkB = pLinkB->next;
}
}
/* 跳出循环时，有一个为空。把不为空的剩下的局部插入链表中 */
pTemp->next = pLinkA ? pLinkA:pLinkB;
head = pHead;
return pHead;
}
Node *MergeSort(Node *pList)
{if (pList == NULL || pList->next == NULL)
{return pList;}
/* 获取两头结点 */
Node *pMiddle = getMiddleNode(pList);
/* 链表前半部分，包含两头结点 */
Node *pBegin = pList;
/* 链表后半局部 */
Node *pEnd = pMiddle->next;
/* 必须赋值为空 相当于断开操作。pBegin--pMiddle pEnd--- 最初 */
pMiddle->next = NULL;
/* 排序前半部分数据，只有一个元素的时候进行，即有序 */
pBegin = MergeSort(pBegin);
/* 排序后半局部数据 递归了解能够参考 PrintListRecursion;*/
pEnd = MergeSort(pEnd);
/* 合并有序链表 */
return MergeList(pBegin, pEnd);
} 大家的激励是我持续创作的能源，如果感觉写的不错，欢送关注，点赞，珍藏，转发，谢谢！
以上代码均为测试后的代码。如有谬误和不妥的中央，欢送指出。
图片来自网络，侵权请分割我删除
如遇到排版错乱的问题，能够通过以下链接拜访我的 CSDN。
CSDN:CSDN 搜寻“嵌入式与 Linux 那些事”
欢送欢送关注我的公众号：嵌入式与 Linux 那些事，支付秋招口试面试大礼包（华为小米等大厂面经，嵌入式知识点总结，口试题目，简历模版等）和 2000G 学习材料。