共计 10141 个字符,预计需要花费 26 分钟才能阅读完成。
上节介绍了链表的基本操作 [史上最全单链表的增删改查反转等操作汇总以及 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 学习材料。