【数据结构】（单链表）单链表冒泡排序

谁践踏了优雅 2021-10-29 22:10 414阅读 0赞

> **算法思想：冒泡排序的核心思想为 内存循环每次冒泡出一个最大的数到尾端**

void BubbleSort(LNode *&head){
        
    
     	if(head->next==NULL||head->next->next==NULL)  //若链表为空或者链表中只有一个元素 返回
    		return ;
    	int flag=0;
    	LNode *cur;             //游标节点
     	LNode *pre;             //游标节点的前驱节点 用户交互时进行链接
     	LNode *tail=NULL;      //尾指针节点
    	LNode *temp;           //临时节点
    	/**
    	while(pre->next!=NULL){  //首先找到最后一个节点 并将 tail指向最后一个节点作为 外层循环退出条件
    		pre=pre->next;
    	}
    	 pre=p;
    	*/
     	while(head->next!=tail){
         //当头节点的下一个 节点为尾节点是跳出循环因为当前链表为排序的元素只剩下一个时候无需排序
    		cur=head->next;
    		pre=head;
     		while(cur->next != tail  ){
        
     			if(cur->data > cur->next->data){
        
     				temp=cur->next;         //首先将临时指针指向需要交换位置的节点防止断链
     				cur->next=temp->next;   //节点位置交换
     				temp->next=cur;	    	//节点位置交换
     				pre->next=temp;	        //节点位置交换
     				pre=temp;
    				 flag=1;				//调整前驱节点的位置 使pre为cur的前驱节点
    			 }else{
        
    			 	pre=pre->next;
    			 	cur=cur->next;
    			 }
    		}
    
    		if(flag==0)  //设置一个flag 来检测 当前 链表是否有序 提高效率
    			return;
    		tail=cur;         //使尾节点 使尾节点 指向每一次冒泡出来的最大节点；尾节点的前面的节点是无序的
    	}
     }

发表评论取消回复

表情：

评论列表（有 0 条评论，414人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构 - 单链表

文章目录目录文章目录一、什么是链表? 线性表: 顺序表: 二、链表的分类和实现分类: 实现: 1.创建节点类 2.创建单链表 1.addTa

小咪咪/ 2024年03月08日 04:56/ 0 赞/ 149 阅读

相关【数据结构】-循环链表(单链表）

循环单链表-带头结点 1.头文件及类型定义 2.循环单链表结点类型定义 3.函数声明 4.基本操作 4.1 初始化循环单链表

末蓝、/ 2023年02月27日 14:59/ 0 赞/ 53 阅读

相关数据结构单链表

\ifndef LINKLIST\_H \define LINKLIST\_H \include<iostream> using namespace std

野性酷女/ 2022年08月13日 12:50/ 0 赞/ 265 阅读

相关数据结构——单链表

链表也是一种常用的数据结构，机制灵活用途广泛，适用于许多通用数据库。讨论一下数组的使用缺陷：1.无序数组搜索效率比较低，有序数组插入效率比较低。无论哪一种删除效率都很低。2。

落日映苍穹つ/ 2022年07月18日 01:11/ 0 赞/ 238 阅读

相关数据结构单链表

做一个豁达而努力的自己。单链表的定义:单链表连式存储的数据结构，是用任意的存储位置存储数据。线性表的单链表存储结构： typedef struct Node \{

Myth丶恋晨/ 2022年05月28日 23:40/ 0 赞/ 319 阅读

相关数据结构-链表之单链表

单链表即每个节点都存在数据域和指针域（特殊节点除外），每个节点都一个直接前驱节点和直接后继节点（头节点无前驱，尾节点无后继），简单来说就是上一个节点的指针域中存放了下一

╰+攻爆jí腚メ/ 2022年05月25日 05:20/ 0 赞/ 353 阅读

相关【数据结构】（单链表）单链表选择排序

> 算法思想：每次选择最大的或者最小的进行尾插或者头插。本例选择每次找到最小的数进行尾插 void SelectSort(LNode &head){

朱雀/ 2021年10月29日 22:14/ 0 赞/ 447 阅读

相关【数据结构】（单链表）单链表冒泡排序

> 算法思想：冒泡排序的核心思想为内存循环每次冒泡出一个最大的数到尾端 void BubbleSort(LNode &head){

谁践踏了优雅/ 2021年10月29日 22:10/ 0 赞/ 415 阅读

相关【数据结构】（单链表）单链表插入排序

> 算法思想：将链表分为两个链表（逻辑上）一个链表默认有序（只含有一个有效节点）另为无序链表/ 大循环为每次循环从无序链表拿出一个元素将其插入有序链表中 vo

逃离我推掉我的手/ 2021年10月29日 22:08/ 0 赞/ 501 阅读

相关数据结构--可排序单链表

可排序单链表 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9

淡淡的烟草味﹌/ 2021年08月13日 21:05/ 0 赞/ 517 阅读