开发者社区> yexx> 正文

Java单链表实现快速排序

简介: 普通快排的思路 选择1个结点为中心点,保证中心点左边比中心点小,中心点右边比中心点大即可。这就是一次快排,确定一个数的正确位置,然后进行递归。 单链表的实现为 使第一个节点为中心点 创建2个指针(p,q),p指向头结点,q指向p的下一个节点 q开始遍历,如果发现q的值比中心点的值小,则此时p=p->next,并且执行当前p的值和q的值交换,q遍历到链表尾即可
+关注继续查看

普通快排的思路

选择1个结点为中心点,保证中心点左边比中心点小,中心点右边比中心点大即可。这就是一次快排,确定一个数的正确位置,然后进行递归。

单链表的实现为

  1. 使第一个节点为中心点
  2. 创建2个指针(p,q),p指向头结点,q指向p的下一个节点
  3. q开始遍历,如果发现q的值比中心点的值小,则此时p=p->next,并且执行当前p的值和q的值交换,q遍历到链表尾即可
  4. 把头结点的值和p的值执行交换。此时p节点为中心点,并且完成1轮快排
  5. 使用递归的方法即可完成排序

具体函数实现

public void quickSort(ListNode begin, ListNode end) {
        //判断为空,判断是不是只有一个节点
        if (begin == null || end == null || begin == end)
            return;
        //从第一个节点和第一个节点的后面一个几点
        ListNode first = begin;
        ListNode second = begin.next;

        int nMidValue = begin.val;
        //结束条件,second到最后了
        while (second != end.next && second != null) {
            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);
    }

在main函数是这样的

public static void main(String[] args) {
        ListNode head = new ListNode(2);
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(5);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(8);
        ListNode l5 = new ListNode(4);
        ListNode l6 = new ListNode(2);
        ListNode l7 = new ListNode(1);

        /*ListNode p = l1;
        System.out.println(p.equals(head));
        System.out.println(p == head);*/

        head.next = l1;
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        l6.next = l7;
        l7.next = null;

        ListNode p = head;
        while (p.next != null) {
            System.out.print(p.val);
            p = p.next;
        }
        System.out.print(p.val);
        System.out.println();

        ListNode begin = head, end = p;
        new SingleLinkedListSorting().quickSort(begin, end);

        p = head;
        while (p != null) {
            System.out.print(p.val);
            p = p.next;
        }

测试结果

这里写图片描述

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java算法基础 - 单链表详解(文末有配套视频)
咳咳,我是小白,没错,主线剧情又回来了。现在我遇到麻烦了,老板要我设计一个类,可以用来保存多个客户的资料。
18 0
【Java基础】 建立一个单链表(增删查改)
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
17 0
《Java数据结构基础》单链表的手动实现
《Java数据结构基础》单链表的手动实现
11 0
【Java数据结构】实现单链表
【Java数据结构】实现单链表
21 0
Java单链表的应用实例
Java单链表的应用实例
22 0
Java数据结构之单链表(配图详解,简单易懂)
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的,看着这段文字抽象不,生硬不(本笔记主要介绍单向不带头节点非循环链表)
36 0
java语言实现单链表---不含头结点
java实现单链表—含头结点,且该篇文章与另一篇含头结点的实现单链表的文章第一部分均是重复的,若看可忽略,说到这里必须要写下含不含头结点的区别,带有头结点是为了更好的实现单链表的功能,带有头结实现的insert、remove等方法相比于不带头结点的单链表会更简洁一些,此外,学习不带头结点的和带有头结点的单链表是没有区别的。
22 0
java语言实现单链表--含头结点
线性表是我们最常用的一种数据结构,线性表包含顺序表和链表,顺序表典型应用就是我们常用的ArrayList,链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结单链表的实现以及使用并且对比单链表与顺序表的优缺点,确定其使用功能场景。
34 0
单链表的基本操作(Java实现)
单链表的基本操作(Java实现)
81 0
通用版!完整代码,单链表SingleLinkedList增删改查,反转,逆序,有效数据等Java实现
通用版!完整代码,单链表SingleLinkedList增删改查,反转,逆序,有效数据等Java实现
34 0
+关注
yexx
CSDN博客地址---http://blog.csdn.net/bug_moving GitHub地址---https://github.com/androidwolf
文章
问答
视频
文章排行榜
最热
最新
相关课程
更多
相关电子书
更多
JAVA开发手册1.5.0
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
相关实验场景
更多