Cherish_MFX-CSDN博客

原创 Java实现对二分查找(折半查找)改进

一、二分查找(折半查找)改进的思路：1.问题提出：在一个有序数组数组{1,8, 10, 89, 1000, 1000,1000,1234} 当中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000，我们利用之前的二分查找只能查找到一个1000的位置，这个时候我们就需要对我们之前写的二分查找进行一个改进了！2.改进的思路分析：（1）在我们利用二分查找(折半查找)，找到mid值的时候，我们需要马上return；（2）向mid索引值的左边扫描，将所有满足条件得元素下标，加入到集合Array

2020-10-16 22:59:43 215

原创 Java实现二分查找(折半查找)

一、二分查找(折半查找)的思路分析：注意：二分查找(折半查找)是有条件的，就是要求数组是有序的！注意：我们在思路分析中假定数组是升序的也就是从小到大的1、首先确定该数组arr的中间的下标mid=(left+right)/2left表示数组的首个元素的下标，right表示数组最后一个元素的下标2.然后让查找的的数findVal和arr[mid]比较（1）如果findVal>arr[mid]，那么说明你要查找的数在mid的右边，因此需要向右递归查找（2）如果findVal<arr[mi

2020-10-16 22:29:39 556

原创 Java实现顺序查找(线性查找)

一、顺序查找(线性查找)的查找思路：1.顺序查找(线性查找)就是遍历整个数组，在遍历数组的时候用需要查找的数与数组元素一一比对，找到就返回该元素在数组中的下标，没有找到就返回-1二、代码实现：public class SequenceSearch { public static void main(String[] args) { int arr[]={1,9,11,-1,34,89};//一组无序序列 int index=sequenceSearch(arr,

2020-10-16 21:59:13 615

原创 Java实现基数排序(桶排序)

一、基数排序(桶排序)排序的基本介绍和排序思路：1.基数排序(桶排序)基本介绍：（1）基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用（2）基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法（3）基数排序(Radix Sort)是桶排序的扩展（4）基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现

2020-10-15 23:37:34 322 1

原创 Java实现归并排序

一、归并排序的基本介绍和排序思想：1.基本介绍：归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的答案“修补”在一起，即分而治之)。2.归并排序的排序思想示意图：二、代码实现：import java.util.Arrays;public class MergeSort { public static void main(String[] args) {

2020-10-12 21:03:33 224 3

原创 Java实现快速排序

一、快速排序的基本介绍和算法思路1.基本介绍：快速排序（Quick Sort）概念:是由冒泡排序改进而得到的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可以消除多个逆序。2.快速排序的算法思路：在待排序的n个记录中任取一个记录（通常取第一个记录）作为枢轴（或支点），设其关键字为pivotkey。经过一趟排序后，把所有关键字小于pivotkey的记录交换到前

2020-10-12 11:08:44 212 3

原创 Java实现希尔排序(缩小增量排序)

一、简单插入排序存在问题：1.我们来看简单插入排序可能存在的问题：数组arr={2，3，4，5，6，1}，这时需要插入的数1(最小)，这个过程是：{2，3，4，5，6，6}{2，3，4，5，5，6}{2，3，4，4，5，6}{2，3，3，4，5，6}{2，2，3，4，5，6}{1，2，3，4，5，6}结论：当需要插入的数是最小数并且它在数组比较靠后的位置时，后移的次数明显增多，对排序的效率有很大的影响。二、希尔排序(缩小增量排序)的介绍及其排序的基本思想：1.希尔排序法的介绍：希尔排序

2020-10-12 10:47:46 153

原创 Java实现插入排序

一、插入排序的基本介绍及排序思想：1.基本介绍：插入排序输入内部排序，是对欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。2.排序思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一元素，把它依次与有序表中的元素进行比较，在有序表中找到合适的位置并将其插入到有序表中合适的位置上，使之成为新的有序表。3.插入排序的思路图：二、代码实现：import java.util.Arrays;//插

2020-10-10 22:18:47 292

原创 Java实现选择排序及其优化

一、选择排序的基本介绍及其排序思想：1.基本介绍：选择排序(SelectSort)是一种简单的排序方法，也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一个元素，再依规定交换位置后达到排序的目的。2.排序思想：第一趟排序：我们假定数组的首个元素就是最小值，让其与数组的后面元素进行比较，直到找到一个最小值，让其与数组的首个元素进行交换，第二趟排序：我们假定数组的第二个元素是最小值，让其与数组的后面元素进行比较，直到找到一个最小的值，让其与数组的第二个元素进行交换，以此类推，直到假定数组倒数第二个数

2020-10-10 21:54:09 307

原创 Java实现冒泡排序及其优化

一、冒泡排序的概念、排序的思想以及排序的过程：1.冒泡排序（Bubble Sort）是一种简单的交换排序，它是通过两两比较相邻记录的关键字，如果发生逆序就进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”（左移），或者使关键字大的记录如石块一样向下“坠落”（右移）。2.冒泡排序的思想：就是将关键字进行两两比较，如果发生逆序就进行交换。第一趟排序之后会得到一个最大值，将其放到数组的最后，第二趟排序之后会得到一个次最大值，将其放在数组的倒数第二的位置，以此类推，直到数组的Length-1趟结束3.冒

2020-10-10 09:10:24 1093

原创 Java递归回溯思想解决八皇后问题

一、八皇后问题介绍及算法思路分析：1.八皇后问题，是一个古老而著名的问题，是递归回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列、或同一斜线上，问有多少中摆法。2.八皇后问题算法思路：（1）第一个皇后放在第一行第一列（2）第二个皇后放在第二行第一列，然后判断是否OK，如果不OK，继续放在这行的第二列、第三列、依次把所有的列都放完，找到一个合适的位置（3）继续第三个皇后，还是第一列、

2020-10-09 22:53:51 1387 2

原创 Java使用递归回溯思想解决迷宫问题

一、递归需要遵守重要规则：1.执行一个方法时，就创建–个新的受保护的独立空间(栈空间)2.执行一个方法时，就创建–个新的受保护的独立空间(栈空间)3.如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.4.递归必须向退出递归的条件逼近，否则就是无线递归，出现StackOverflowError，死递归5.当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。二、迷宫问题代码实现：说明：迷宫寻路的结果

2020-10-09 22:02:26 258

原创 Java实现中缀表达式转后缀表达式(逆波兰表达式)

一、中缀表达式转后缀表达式的思路：1.初始化连个栈：运算符栈s1和存储中间结果的栈s22.从左到右扫描遍历中缀表达式3.遇到操作数时，直接将其压入s2中4.遇到运算符时，比较其与当前s1栈顶元素运算符的优先级：4.1)如果s1为空，或者栈顶运算符为左括号"("，则直接将其入栈4.2)否则，若优先级比栈顶元素运算符高，也将运算符压入s14.3)否则，将s1栈顶运算符弹出并压入s2中，再次转到4.1与s1中新栈顶运算符进行比较5.遇到括号时5.1)如果是左括号“(”，就直接压入s1中5.2)

2020-10-09 21:36:38 191

原创 Java使用栈实现对表达式的计算

一、使用栈完成对表达式计算的思路1.首先我们需要两个栈，一个是数栈用于存放数，另一个是符号栈用于存放操作符2.通过一个索引值index，来遍历我们需要计算的表达式3.当我们遍历表达式的时候，如果我们发现当前遍历到的是数字就将其放入数栈中4.如果我们发现当前遍历到的是符号，就分如下的情况：（1）如果符号栈为空，就将当前的操作符入符号栈中（2）如果符号栈有操作符，就进行比较，如果当前操作符的优先级小于或等于栈中操作符，就需要从数栈中pop出两个数，再从符号栈中pop出一个操作符，进行运算，将得到的结

2020-10-08 23:27:41 1019

原创 Java使用链表来模拟栈

Java使用链表来模拟栈关于栈和链表的相关介绍在我之前的博客里面，不懂的可以去看我的相关栈和链表的博客！1.使用链表来模拟栈，首先需要构建一个链表，构建一个链表之前我们需要创建链表的节点——Node类//定义链表的节点class Node { private int value; private Node next; public Node(int value) { this.value = value; } public int getV

2020-09-27 23:03:38 926 1

原创 Java使用数组来模拟栈

一、栈的介绍1.栈的英文为stack。2.栈是一个先入后出(FILO-First In Last Out)的有序列表。3.栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特俗线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。4.根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。5.出栈(pop)和入栈(push)的概念(如图所示)

2020-09-27 22:46:40 425

原创 Java使用单向循环链表解决Josephu(约瑟夫、约瑟夫环)问题

一、Josephu(约瑟夫、约瑟夫环)问题的介绍：1.Josephu(约瑟夫、约瑟夫环)问题为：设编号为1，2，3，…n-1，n的n个人围坐一圈，约定编号为k的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人又出列，以此类推，知道所有的人都出列为止，由此产生一个出列编号2.问题解决思路：用一个不带头结点的单向循环链表来处理JosePhu问题：先构成用一个单向循环链表，然后由K节点起从1开始计数，计数到m时，将对应的节点从链表中删除，然后再从被删除的节点的下一个节点起从1开始计

2020-09-25 23:08:55 720

原创 Java实现双向链表

Java实现双向链表一、双向链表和单链表的比较：1.双向链表比单链表多一个变量pre，该变量指向的是前一个节点2.单向链表，查找的方向只能是一个方向，而双向链表可以向前或向后查找3.单向链表不能自我删除，需要辅助节点帮助其删除一个节点，而双向链表则可以自我删除，所以单链表删除的时候我们找到的是待删除节点的前一个节点。二、双链表的实现1.首先需要定义双向链表的节点——定义一个HeroNode2类：//定义一个HeroNode2，每一个HeroNode2对象就是一个节点class HeroNo

2020-09-25 22:40:05 496 4

原创 Java解决单链表中一些常见的问题：求链表节点个数、查找链表中倒数第k个节点、链表的反转、链表的逆序打印

Java解决单链表中一些常见的问题：求链表节点个数、查找链表中倒数第k个节点、链表的反转、链表的逆序打印完整的测试代码在最后面，下面是求解各个问题的方法的代码：一、求单链表中有效节点的个数：思路：1.首先你需要判断这个链表是不是为空，如果为空就返回02.如果链表不为空，就遍历这个链表每遍历到一个节点就让length++，在遍历链表的时候注意需要定义个辅助指针也就是赋值变量cur用于遍历链表，最后返回length就可以了。public static int getLength(HeroNode h

2020-09-25 22:20:03 607

原创 Java实现单链表——水浒英雄排行榜

Java实现单链表用于存储水浒英雄的信息一、链表(LinkedList)介绍1.链表是有序的列表，但是它在内存中是如下存储的：2.小结：（1）链表是以节点的方式来存储的，是链式存储（2）每个节点包含data域：保存数据信息，next域：指向下一个节点（3）如上图：可以发现链表的各个节点不一定是连续存储的（4）链表分带头结点的链表和不带头结点的链表，根据实际的需求来确定3.单链表(带头结点)逻辑示意图如下所示：二、实现单链表1.实现链表的节点——写一个HeroNode节点类：//定义

2020-09-25 20:53:00 555

原创 Java使用数组模拟环形队列

一、数组模拟环形队列说明1.这是对前面的数组模拟队列的优化，充分利用数组。因此将数组看看成一个环形的(通过取模的方式来实现即可)。2.对环形队列进行分析说明：（1）尾索引的下一个为头索引时表示队列已满，即将队列容量空出一个作为一个约定，这个在做队列满的时候需要注意(rear+1)%maxSize=front为队列满的判定条件（2）rear=front还是环形队列为空的判定条件二、代码实现import java.util.Scanner;public class CircleArrayQueu

2020-09-23 23:00:01 265 1

原创 Java使用数组模拟队列

Java使用数组模拟队列public class ArrayQueueDemo { public static void main(String[] args) { // 测试一下 // 创建一个数组队列 ArrayQueue arrayQueue = new ArrayQueue(3); char key = ' ';// 接收用户输入 Scanner scanner = new Scanner(System.in); boolean loop = true; // 输出一

2020-09-20 21:59:43 122

原创稀疏数组(稀疏矩阵)和二维数组相互转换

一、稀疏数组的相关介绍：1.稀疏数组转二维数组的条件：当一个二维数组中大部分的元素为0或者为同一个值时，就可以使用稀疏数组来保存该二维数组。2.为什么要将二维数组转换为稀疏数组的原因：因为二维数组中的很多值是相同的默认值0或其他相同的数值，因此记录了很多没有意义的数据，所以可以使用稀疏数组将其压缩存储起来。3.稀疏数组行列的介绍：稀疏数组同样也是一个二维数组，稀疏数组有三列分别记录着二维数组的行、列和数值，另外稀疏数组的第一行表示的就是原来二维数组的行数、列数以及该二维数组中除大部分相同数值外的其他数

2020-09-20 21:42:52 2683

mfx7700429的博客