单链表的冒泡,快排,选择,插入,归并5种排序算法详解(多图+代码实现) |
您所在的位置:网站首页 › python单链表快速排序 › 单链表的冒泡,快排,选择,插入,归并5种排序算法详解(多图+代码实现) |
上节介绍了链表的基本操作史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言) https://cloud.tencent.com/developer/article/1826524 这节介绍链表的5种排序算法。 0.稳定排序和原地排序的定义稳定排序: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。像冒泡排序,插入排序,基数排序,归并排序等都是稳定排序 原地排序: 基本上不需要额外辅助的的空间,允许少量额外的辅助变量进行的排序。就是在原来的排序数组中比较和交换的排序。像选择排序,插入排序,希尔排序,快速排序,堆排序等都会有一项比较且交换操作(swap(i,j))的逻辑在其中,因此他们都是属于原地(原址、就地)排序,而合并排序,计数排序,基数排序等不是原地排序 1.冒泡排序基本思想: 把第一个元素与第二个元素比较,如果第一个比第二个大,则交换他们的位置。接着继续比较第二个与第三个元素,如果第二个比第三个大,则交换他们的位置… 我们对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样一趟比较交换下来之后,排在最右的元素就会 是最大的数。除去最右的元素,我们对剩余的元素做同样的工作,如此重复下去,直到排序完成。 具体步骤: 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。 3.针对所有的元素重复以上的步骤,除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 时间复杂度:O(N2) 空间复杂度:O(1) 稳定排序:是 原地排序:是 ![]() 基本思想 我们从数组中选择一个元素,我们把这个元素称之为中轴元素吧,然后把数组中所有小于中轴元素的元素放在其左边, 所有大于或等于中轴元素的元素放在其右边,显然,此时中轴元素所处的位置的是有序的。也就是说,我们无需再移动中轴 元素的位置。 从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素),接着我们通过递归的方式,让中轴元素 左边的数组和右边的数组也重复同样的操作,直到数组的大小为1,此时每个元素都处于有序的位置。 具体步骤: 1.从数列中挑出一个元素,称为 “基准”(pivot); 2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作; 3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序; 时间复杂度:O(NlogN) 空间复杂度:O(logN) 稳定排序:否 原地排序:是 ![]() 基本思想:每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。 具体步骤: 1.将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列; 2.取出下一个元素,在已经排序的元素序列中从后向前扫描; 3.如果该元素(已排序)大于新元素,将该元素移到下一位置; 4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置; 5.将新元素插入到该位置后; 6.重复步骤2~5。 时间复杂度:O(N2) 空间复杂度:O(1) 稳定排序:是 原地排序:是 防止恶意转载 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/qq_16933601/article/details/105255686 ![]() 基本思想:首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。这种方法我们称之为选择排序。 具体步骤: 1.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。 2.再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。 3.重复第二步,直到所有元素均排序完毕。 时间复杂度:O(N2) 空间复杂度:O(1) 稳定排序:否 原地排序:是 ![]() SwapNode相关代码如下。当时考虑只需要理解排序思想就好了,就没有把这个函数的代码放出来。这个代码写的太长太复杂了,有时间我会重新精简下。(说实话,我都快忘了怎么写的了) 代码语言:javascript复制/*交换相邻节点*/ 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)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) 稳定排序:是 原地排序:否 ![]() 以上代码均为测试后的代码。如有错误和不妥的地方,欢迎指出。 图片来自网络,侵权请联系我删除 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |