单链表排序java_快速排序链表

单链表排序java_快速排序链表难易程度:★★重要性:★★★链表的排序相对数组的排序更为复杂些,也是考察求职者是否真正理解了排序算法(而不是“死记硬背”) 链表的插入排序 publicclassLinkedInsertSort{staticclassListNode{intval;ListNodenext;Lis…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

难易程度:★★

重要性:★★★

 

     链表的排序相对数组的排序更为复杂些,也是考察求职者是否真正理解了排序算法(而不是“死记硬背”)

  1. 链表的插入排序

    public  class LinkedInsertSort {
        static class ListNode {
            int val;
            ListNode next;
            ListNode(int x) {
                val = x;
                next = null;
            }
        }
    
        public static ListNode insertionSortList(ListNode head) {
            if(head==null||head.next==null)    return head;
    
            ListNode pre = head;//pre指向已经有序的节点
            ListNode cur = head.next;//cur指向待排序的节点
    
            ListNode aux = new ListNode(-1);//辅助节点
            aux.next = head;
    
            while(cur!=null){
                if(cur.val<pre.val){
                  //先把cur节点从当前链表中删除,然后再把cur节点插入到合适位置
                    pre.next = cur.next;
    
                    //从前往后找到l2.val>cur.val,然后把cur节点插入到l1和l2之间
                    ListNode l1 = aux;
                    ListNode l2 = aux.next;
                    while(cur.val>l2.val){
                        l1 = l2;
                        l2 = l2.next;
                    }
                    //把cur节点插入到l1和l2之间
                    l1.next = cur;
                    cur.next = l2;//插入合适位置
    
                    cur = pre.next;//指向下一个待处理节点
    
                }else{
                    pre = cur;
                    cur = cur.next;
                }
            }
            return aux.next;
        }
    }
  2. 链表的快速排序
    public static ListNode quickSort(ListNode begin, ListNode end) {
            //判断为空,判断是不是只有一个节点
            if (begin == null || end == null || begin == end)
                return begin;
            //从第一个节点和第一个节点的后面一个几点
            //begin指向的是当前遍历到的最后一个<= nMidValue的节点
            ListNode first = begin;
            ListNode second = begin.next;
    
            int nMidValue = begin.val;
            //结束条件,second到最后了
            while (second != end.next && second != null) {//结束条件
              //一直往后寻找<=nMidValue的节点,然后与fir的后继节点交换
                if (second.val < nMidValue) {
                    first = first.next;
                    //判断一下,避免后面的数比第一个数小,不用换的局面
                    if (first != second) {
                        int temp = first.val;
                        first.val = second.val;
                        second.val = temp;
                    }
                }
                second = second.next;
            }
            //判断,有些情况是不用换的,提升性能
            if (begin != first) {
                int temp = begin.val;
                begin.val = first.val;
                first.val = temp;
            }
            //前部分递归
            quickSort(begin, first);
            //后部分递归
            quickSort(first.next, end);
            return begin;
        }

     

  3. 链表的归并排序

    public ListNode mergeSort(ListNode head){
            if(head==null || head.next==null)    return head;
    
            ListNode mid = getMid(head);//获取链表中间节点
    
            //把链表从之间拆分为两个链表:head和second两个子链表
            ListNode second = mid.next;
            mid.next = null;
    
            //对两个子链表排序
            ListNode left = mergeSort(head);
            ListNode right = mergeSort(second);
    
            return merge(right,left);      
        }
    
        //两个有序链表的归并
        private ListNode merge(ListNode l1,ListNode l2){
          //辅助节点,排好序的节点将会链接到dummy后面
            ListNode dummy = new ListNode(0);
    
            ListNode tail = dummy;//tail指向最后一个排好序的节点
            while(l1!=null&&l2!=null){
                if(l1.val<=l2.val){
                    tail.next = l1;
                    l1 = l1.next;
                }else{
                    tail.next = l2;
                    l2 = l2.next;
                }
                tail = tail.next; //移动tail指针        
            }
    
            if(l1!=null)
                tail.next = l1;
            else
                tail.next = l2;
    
            return dummy.next;
    
        }
    
        //返回链表之间节点
        private ListNode getMid(ListNode head){
            if(head==null ||head.next==null)    return head;
    
            ListNode slow = head;
            ListNode faster = head.next;
            while(faster!=null&&faster.next!=null){
                slow = slow.next;
                faster = faster.next.next;
            }
            return slow;
        }

     


扫描下方二维码,及时获取更多互联网求职面经javapython爬虫大数据等技术,和海量资料分享
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务;
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料java面试考点java面经总结,以及几十个java、大数据项目资料很全,你想找的几乎都有

扫码关注,及时获取更多精彩内容。(博主今日头条大数据工程师)

扫码关注,及时获取更多精彩内容。(博主今日头条大数据工程师)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183359.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 用GDB调试程序(一)

    用GDB调试程序(一)

    2021年12月10日
  • 关于用户态和内核态的理解和认识_计算机内核态和用户态

    关于用户态和内核态的理解和认识_计算机内核态和用户态究竟什么是用户态,什么是内核态,这两个基本概念以前一直理解得不是很清楚,根本原因个人觉得是在于因为大部分时候我们在写程序时关注的重点和着眼的角度放在了实现的功能和代码的逻辑性上,先看一个例子:1)例子C代码1.     void testfork(){  2.     if(0 = = fork()){  3.     printf(“create new process su

  • 线扫激光算法原理「建议收藏」

    线扫激光算法原理「建议收藏」一:线扫激光算法原理激光器发出的激光束经准直聚焦后垂直入射到物体表面上,表面的散射光由接收透镜成像于探测器的阵列上。光敏面于接收透镜的光轴垂直。如图:当被测物体表面移动x,反应到光敏面上像点位移为x’。a为接收透镜到物体的距离(物距),b为接收后主面到成像面中心的距离(一般取焦距f),θ为激光束光轴与接收透镜之间的夹角。D为激光光束轴到透镜中心的距离。接收透镜的焦距为f,其余的参数如下图:…

  • sbc音频编解码是什么_人工智能fpga算法工程师

    sbc音频编解码是什么_人工智能fpga算法工程师转自:https://blog.csdn.net/wzz4420381/article/details/48676921原作者:wzz44203811.SBC算法简介SBC是subbandcode的缩写,也可称为子带编码 在A2DP协议中,SBC算法是默认支持的 蓝牙SBC算法是一种以中等比特率传递高质量音频数据的低计算复杂度的音频编码算法1.1算法基本框图SB…

  • 网页数据如何实现实时刷新?

    网页数据如何实现实时刷新?本文仅为学技术而简单举例,后端框架是Django,具体业务逻辑是否合理可以不用管,下方是工作中需要实现的需求。

  • 5g端到端网络切片技术_5G网络切片的特征

    5g端到端网络切片技术_5G网络切片的特征1、网络切片的一些概念网络切片(Slice):基于客户化需求,可以被设计、部署、维护的逻辑网络,旨在满足特定的客户、业务、商业场景的业务特点及商业模式。网络切片实例(E2ESliceInstance-ESI):网络切片实例(Instance)是一个临时逻辑网络,跨多个技术域,包含:(1)组网络:”功能”(Function)即虚拟网元(终端、接入网、回传网、核心网、业务网络)及网管系统对应的资源;(2)存储、运算;(3)连接关系。2、网络切片原因:未来业务需求差异

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号