排序算法汇总(数组+链表)

news/2024/10/30 21:27:01/
  1. 冒泡排序

算法核心:
相邻节点两两交换,重复进行(n-1)轮。
时间复杂度为
空间复杂度为
是否稳定:稳定

1.1 数组排序

图1 冒泡排序算法(数组)

public class BubbleSortArray {public static void main(String[] args) {BubbleSortArray sort = new BubbleSortArray();sort.sortByBubble(new int[]{4, 2, 1, 3});}public void sortByBubble(int[] nums){int n = nums.length; // 数组大小for (int i = n-1; i > 0; i--) { // 循环n-1次for (int j = 0; j < i; j++) {if(nums[j] > nums[j+1]) { // 最大的值放最后,依次两两交换int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;}}}// 输出结果for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(nums[i]);continue;}System.out.print(nums[i]+"->");}}
}

1.2 链表排序

图2 冒泡排序核心交换图

public class BubbleSortByLinkedList {public static void main(String[] args) {// 创建链表ListNode head = new ListNode();ListNode temp = new ListNode();temp = head;ListNode node4 = new ListNode(4);temp.next = node4;temp = temp.next;ListNode node2 = new ListNode(2);temp.next = node2;temp = temp.next;ListNode node1 = new ListNode(1);temp.next = node1;temp = temp.next;ListNode node3 = new ListNode(3);temp.next = node3;temp = temp.next;BubbleSortByLinkedList sort = new BubbleSortByLinkedList();sort.sortByLinkedList(head.next);}public void sortByLinkedList(ListNode head){ListNode dummy = new ListNode();dummy.next = head;ListNode temp = head;int n = 0; // 统计链表节点个数while (temp != null){n++;temp = temp.next;}for (int i = 0; i < n-1; i++) {int num = n-i-1; // 统计内循环需要多少次ListNode pre = dummy; // 最前一个节点ListNode p = pre.next; // 第一个内循环节点ListNode q = p.next; // 第二个内循环节点for (int j = 0; j < num; j++) {if(p.val > q.val){ // 前一个比后一个大,两两交换p.next = q.next;q.next = p;pre.next = q;}// 下一次内循环指针指向pre = pre.next;p = pre.next;q = p.next;}}// 输出链表dummy = dummy.next;for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(dummy.val);continue;}System.out.print(dummy.val+"->");dummy = dummy.next;}}
}// 链表节点元素
class ListNode{ListNode next;int val;ListNode(){}ListNode(int val){this.val = val;}
}

2. 插入排序

2.1 数组排序

算法核心:
首先,每一轮都假定待插入元素之前的数组元素是排好序的(算法也的确如此,没问题);
其次,找到大于待插入元素的下标;
紧接着,将待插入位置至待插入元素之前的上一个下标都后移一位;
最后,将待插入元素插入到找到的下标位置。
时间复杂度为
空间复杂度为
是否稳定:稳定
public class InsertSortByArray {public static void main(String[] args) {InsertSortByArray sort = new InsertSortByArray();sort.sortByInsert(new int[]{4, 2, 1, 3});}public void sortByInsert(int[] nums){// 统计数组元素个数int n = nums.length;for (int i = 1; i < n; i++) {int insertNum = nums[i];int j = 0;while (j<i && nums[j] < insertNum){ // 寻找比插入元素大的下标j++;}for (int k = i-1; k >= j; k--) { // 插入元素的后面元素都后移nums[k+1] = nums[k];}nums[j] = insertNum; // 插入元素}// 输出结果for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(nums[i]);continue;}System.out.print(nums[i]+"->");}}}

2.2 链表排序

算法核心:
添加虚拟节点dummy,有利于找到修改节点的上一个节点,做移除操作。
接下来只需三步:
1. 定位待插入节点和待插入节点的前一个节点;
2. 定位大于待插入节点和大于待插入节点的前一个节点;
3. 移除待插入节点,将待插入节点插入到相应位置。

public class InsertByLinkedList {public static void main(String[] args) {// 创建链表ListNode head = new ListNode();ListNode temp = new ListNode();temp = head;ListNode node4 = new ListNode(4);temp.next = node4;temp = temp.next;ListNode node2 = new ListNode(2);temp.next = node2;temp = temp.next;ListNode node1 = new ListNode(1);temp.next = node1;temp = temp.next;ListNode node3 = new ListNode(3);temp.next = node3;temp = temp.next;InsertByLinkedList sort = new InsertByLinkedList();sort.sortByLinkedList(head.next);}public void sortByLinkedList(ListNode head) {// 统计链表节点个数int n = 0;ListNode temp = head;while (temp != null){n++;temp = temp.next;}ListNode dummy = new ListNode();dummy.next = head;for (int i = 2; i <= n; i++) {int j = 1;ListNode pre = dummy; // 扫面链表节点的前一个节点ListNode p = pre.next; // 扫描链表节点ListNode pre_q = dummy; // 待插入节点的上一个节点ListNode q = dummy.next; // 待插入节点while (j < i){ j++;pre_q = pre_q.next;q = q.next;}pre_q.next = q.next; // 移除待插入节点while (p != q && p.val <= q.val) { // 查找大于待插入节点的节点位置pre = pre.next;p = p.next;}// 插入待插入节点q.next = p; pre.next = q;}// 输出链表dummy = dummy.next;for (int i = 0; i < n; i++) {if(i == n-1){System.out.println(dummy.val);continue;}System.out.print(dummy.val+"->");dummy = dummy.next;}}// 链表节点定义static class ListNode{ListNode next;int val;ListNode(){}ListNode(int val){this.val = val;}}}


http://www.ppmy.cn/news/32540.html

相关文章

Android开发 View属性

1. View View的子类及子类的子类都有View的属性&#xff0c;都可以设置下述介绍的属性。 2.View宽高 View及其派生类的宽高共有三类值&#xff1a; match_parent&#xff1a;匹配父控件的宽高 wrap_content: 匹配内容的长度&#xff0c;例如TextView是包裹文字 fixed numb…

JavaScript的事件传播机制

你在学习和编写JavaScript时可能听说过事件冒泡&#xff08;event bubbling&#xff09;。它会发生在多个元素存在嵌套关系&#xff0c;并且这些元素都注册了同一事件(例如click)的监听器时。 但是事件冒泡只是事件机制的一部分。它经常与事件捕获(event capturing)和事件传播…

【微信小程序】-- 全局数据共享 - MobX(四十三)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…

Mysql常用命令

mysql连接&#xff1a; [roothost]# mysql -u root -p Enter password:******创建数据库&#xff1a; CREATE DATABASE 数据库名&#xff1b; 删除数据库&#xff1a; drop database 数据库名; 使用mysqladmin删除数据库&#xff1a; [roothost]# mysqladmin -u root -p dr…

面试了一个32岁的程序员,一个细节就看出来是培训班的····

首先&#xff0c;我说一句&#xff1a;培训出来的&#xff0c;优秀学员大有人在&#xff0c;我不希望因为带着培训的标签而无法达到用人单位和候选人的双向匹配&#xff0c;是非常遗憾的事情。 最近&#xff0c;在网上看到这样一个留言&#xff0c;引发了程序员这个圈子不少的…

【pygame游戏】Python实现蔡徐坤大战篮球游戏【附源码】

前言 话说在前面&#xff0c;我不是小黑子~&#x1f60f; 本文章纯属技术交流~娱乐 前几天我获得了一个坤坤打篮球的游戏&#xff0c;也给大家分享一下吧~ 好吧&#xff0c;其实并不是这样的游戏&#xff0c;往下慢慢看吧。 准备工作 开发环境 Python版本&#xff1a;3.7.8 …

响应式编程详解,带你熟悉Reactor响应式编程

文章目录一、什么是响应式编程1、Java的流和响应式流2、Java中响应式的使用3、Reactor中响应式流的基本接口4、Reactor中响应式接口的基本使用二、初始Reactor1、Flux和Mono的基本介绍2、引入Reactor依赖3、响应式类型的创建4、响应式类型的组合&#xff08;1&#xff09;使用m…

http协议 - 笔记

1 http协议 -- post,get,delete 如何使用http协议post - /api/v1/User/1 要使用 HTTP 协议 POST 方法向 /api/v1/User/1 发送请求,您可以使用一个 HTTP 客户端(例如 Postman、cURL 或浏览器扩展程序)并按照以下步骤操作: 打开您的 HTTP 客户端。在 URL 地址栏中输入 /a…