当前位置： 首页 > article >正文

26从零开始学Java之如何对数组进行排序与二分查找？

article 2024/11/15 5:57:39

作者：孙玉昌，昵称【一一哥】，另外【壹壹哥】也是我哦

千锋教育高级教研员、CSDN博客专家、万粉博主、阿里云专家博主、掘金优质作者

配套开源项目资料

https://github.com/SunLtd/LearnJava
https://gitee.com/sunyiyi/LearnJava

前言

在上一篇文章中，壹哥给大家讲解了数组的扩容、缩容及拷贝方式。接下来在今天的文章中，壹哥会给大家讲解更重要的数组排序及查找方法。今天的内容会有点难，希望你不要因此而退缩，挺过这一关，你会向上突破的！

------------------------------------------------前戏已做完，精彩即开始----------------------------------------------

全文大约【3500】字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考......

配套开源项目资料

Github：

GitHub - SunLtd/LearnJavaContribute to SunLtd/LearnJava development by creating an account on GitHub.https://github.com/SunLtd/LearnJava

Gitee：

Gitee - 从零开始学Javahttps://gitee.com/sunyiyi/LearnJava

一. 数组排序

1. 简介

Java中的数组是一种数据集合，里面可以存储若干数据元素。有时我们需要对这些数据元素进行排序，找出数组中的最大值、最小值，或者是按降序或升序对数组进行排列，这些需求都需要我们能够对数组进行排序。但我们要注意，对数组排序会修改数组本身，即数组里元素的内存指向会发生改变。

对数组进行排序是程序中很常见的需求。如果我们想要实现数组排序，可以利用数据结构中的某些排序算法来进行实现，比如著名的冒泡排序、选择排序等，当然也可以利用Java自带的Arrays.sort()方法来实现。接下来壹哥就针对这几种实现方案，给大家设计几个实现案例。

2. 冒泡排序(重点)

2.1 简介

冒泡排序的核心实现思路，就是把数据元素按照从下到上，两两进行比较。所以冒泡排序的特点是，每一轮循环后，最大的一个数被交换到末尾。因此，下一轮循环可以“刨除”最后的数，每一轮循环都比上一轮循环的结束位置靠前一位。冒泡排序整体可以分为两种情况，即升序排列和降序排列。

升序排列的实现思想：

  1. 将数组中相邻的两个数据元素进行比较，如果前面一个元素比后面的大，就把两者交换位置(一轮比较)；
  2. 然后将上面的操作进行循环(比较n-1轮)。

排列过程如下图所示：

降序排列的实现思想：

  1. 将数组中相邻的两个数据元素进行比较，如果前面一个元素比后面的小，就把两者交换位置(一轮比较)；
  2. 然后将上面的操作进行循环(比较n-1轮)。

2.2 基本实现

大家要注意，面试时经常会让我们手写冒泡排序和选择排序等算法，你必须牢牢地记住相关的代码实现哦。

/**
 * @author 一一哥Sun
 * QQ：2312119590
 * CSDN、掘金、知乎找我哦
 * 千锋教育
 */
public class Demo09 {
	public static void main(String[] args) {
		// 冒泡排序--基本实现
		//待排序的数组
		int[] arr = { 1, 3, 46, 22, 11 };

		//控制需要比较几轮
		for (int i = 0; i < arr.length; i++) {
			//控制每一轮的比较次数
			for (int j = 0; j < arr.length - 1; j++) {
				//如果前面的比后面的数字大，则两者就进行交换
				if (arr[j] > arr[j + 1]) {
					//两数交换，需要一个“第三方”，好比两杯水互换，需要第三个杯子。

                    //交换两个变量的值，必须借助一个临时变量。
					//定义一个新的临时变量，将数组中的前面的元素先赋值给临时变量
					int temp = arr[j];
					//后面的值赋值到前面的位置上
					arr[j] = arr[j + 1];
					//再将临时变量的值赋值到后面的位置上
					arr[j + 1] = temp;
				}
			}
		}
		
		//遍历排序后的数组
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
	}
}

这种实现方式比较容易理解，但并不是最优的实现方案，因为这种方案需要比较的次数较多。我们可以进一步对该方案进行优化，将比较的次数降下来，请继续往下看。

2.3 优化次数

在本案例中，壹哥会对比较次数进行优化。

/**
 * @author 一一哥Sun
 * QQ：2312119590
 * CSDN、掘金、知乎找我哦
 * 千锋教育
 */
public class Demo10 {
	public static void main(String[] args) {
		// 冒泡排序--优化比较次数
		// 待排序数组
		int[] arr = { 1, 3, 46, 22, 11 };

		for (int j = 0; j < arr.length; j++) {   //控制轮数
	        for (int i = 0; i < arr.length - 1 - j; i++) {//控制每一轮的次数
	            if(arr[i] > arr[i+1]) {
	                int temp = arr[i];
	                arr[i] = arr[i+1];
	                arr[i+1] = temp;
	            }
	        }
	    }
		
		//遍历排序后的数组
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
	}
}

本案例同样也不是最优的实现方案，我们也可以对该实现方案进行优化。

2.4 优化轮数

在本案例中，壹哥会对比较的轮数进行优化。

/**
 * @author 一一哥Sun
 * QQ：2312119590
 * CSDN、掘金、知乎找我哦
 * 千锋教育
 */
public class Demo11 {
	public static void main(String[] args) {
		// 冒泡排序--优化比较轮数
		// 待排序数组
		int[] arr = { 1, 3, 46, 22, 11 };

		for (int j = 0; j < arr.length - 1; j++) { //轮数
	        //假设这一轮已经拍好序，设置一个标签进行记录
	        boolean flag = true;
	        
	        for (int i = 0; i < arr.length - 1 - j; i++) {//每一轮比较的次数
	            if(arr[i] > arr[i+1]) {
	            	//更改是否比较过的标签
	                flag = false;
	                int temp = arr[i];
	                arr[i] = arr[i+1];
	                arr[i+1] = temp;
	            }
	        }
	        
	        //如果本轮已排序好，则直接跳过，避免没必要的比较。
	        if(flag) {
	            break;
	        }
	    }
		
		//遍历排序后的数组
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
	}
}

这种实现方案，可以说是三种方案中最优的一种，但对初学者来说，理解起来确实不容易。当然，在我们的线下课程中，我们的讲师会对实现的每一个步骤详细讲解，不用怕自己理解不了。

2.5 配套视频

为了方便大家更好地理解冒泡排序，壹哥这里有对应的视频哦，链接如下：

bilibili html5 player

3. 选择排序(重点)

3.1 简介

选择排序的核心实现思路，是随机确定一个标志位(一般为第一个数字)作为最小数，然后向后遍历，找到比标志位更小的数字后，便与标志位互换位置，并更新最小数。选择排序同样可以进行升序或降序排列。

选择排序升序思路：

  1. 将当前位置上的数，与它后面的每个数进行比较，选择出最小的那个数，交换到当前位置；
  2. 循环选择当前位置上的数。

选择排序降序思路：

  1. 将当前位置上的数，与它后面的每个数进行比较，选择出最大的那个数，交换到当前位置；
  2. 循环选择当前位置上的数。

3.2 实现案例

以下是以升序的方式实现的选择排序代码，供大家参考。

/**
 * @author 一一哥Sun
 * QQ：2312119590
 * CSDN、掘金、知乎找我哦 
 * 千锋教育
 */
public class Demo12 {
	public static void main(String[] args) {
		// 选择排序
		// 待排序的数组
		int[] arr = { 1, 3, 46, 22, 11 };

		for (int j = 0; j < arr.length-1; j++) {
	        //选择下标为0的位置
	        int min = j;
	        
	        //将当前这个数与后面的每个数进行比较
	        for (int i = j+1; i < arr.length; i++) {
	        	//如果当前数字小于标记的最小值，则将当前数字标记为最小值
	            if(arr[min] > arr[i]) {
	                min = i;
	            }
	        }
	        
	        //如果当前数字不是最小的，则进行交换
	        if(min != j) {
	            int temp = arr[j];
	            arr[j] = arr[min];
	            arr[min] = temp;
	        }
	    }
		
		//遍历排序后的数组
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+"\t");
		}
	}
}

3.3 配套视频

为了方便大家更好地理解选择排序，壹哥这里有对应的视频哦，链接如下：

bilibili html5 player

4. Arrays.sort方法

以上两种排序算法，实现起来是比较复杂的，但在面试时，基本上都要求我们能够手写出冒泡排序和选择排序，大家一定要把代码看懂哦。但如果我们想快速实现排序，其实可以使用Java自带的API方法进行实现，这个会更简单。

4.1 简介

Arrays工具类主要用于对数组进行排序、查找、填充、比较等的操作，该类存在于java.util包下，所以我们使用的第一步就是要先进行导包: import java.util.Arrays;

其中Arrays.sort()是Arrays类中的一个静态方法，用于对数组进行排序，我们可以直接调用。该方法有如下几种重载形式：

  • sort(T[] a)：对指定T型数组按数字升序排序；
  • sort(T[] a, int formIndex, int toIndex)：对指定T型数组中[formIndex,toIndex)数据按数字升序排序；
  • sort(T[] a, Comparator<? supre T> c): 依据比较器对T型数组进行排序；
  • sort(T[] a, int formIndex, int toIndex, Comparator<? supre T> c): 依据比较器产生的顺序对T型数组中的[formIndex,toIndex)进行排序。

4.2 实现案例

接下来壹哥再给大家设计一个利用Arrays.sort方法实现的排序案例。

/**
 * @author 一一哥Sun
 * QQ：2312119590
 * CSDN、掘金、知乎找我哦
 * 千锋教育
 */
public class Demo13 {
	public static void main(String[] args) {
		// 选择排序
		//遍历排序后的数组
		String[] names = { "cxk", "rose", "lihua", "lilei", "zhaosi" };
		
		//直接利用Arrays类提供的数组排序的方法，内部是基于“快速排序”实现的。
		Arrays.sort(names);

		for (int i = 0; i < names.length; i++) {
			System.out.print(names[i] + "\t");
		}
	}
}

二. 二分查找法(重点)

1. 简介

我们对数组除了可以进行排序之外，还能对数组中的元素进行查找，其中一个比较经典的方案是利用二分查找法，也叫做折半查找法进行实现，可以缩小查找范围，提高查找效率。

二分查找是一种效率较高的查找方法，要求数据表须采用顺序存储结构，且数组是有序(升序或者降序)的。核心思路就是将待查找的元素与中间下标对应的元素进行比较，如果大于中间下标对应的元素，则去右半部分查找，否则就去左半部分进行查找。基本实现流程如下：

  • 首先，我们假设数组中的元素是按升序排列的；
  • 然后将数组中间位置记录的关键字与查找关键字进行比较，如果两者相等，则查找成功；
  • 否则就利用中间的位置记录，将数组分成前、后两个子部分。如果中间位置记录的关键字大于查找关键字，则进一步查找前一子部分，否则进一步查找后一子部分；
  • 重复以上过程，直到找到满足条件的记录为止。或直到子部分不存在为止，此时查找不成功。

2. 实现案例

然后壹哥就按照上述思路，给大家设计了如下案例，大家可以对照练习，好好琢磨该案例。

/**
 * @author 一一哥Sun
 * QQ：2312119590
 * CSDN、掘金、知乎找我哦
 * 千锋教育
 */
public class Demo14 {
	public static void main(String[] args) {
		// 二分查找法--折半查找法

		// 遍历排序后的数组
		int[] arr = { 1, 3, 46, 22, 11 };

		int index = search(arr,46);
		System.out.println("46所在的索引位置="+index);
	}
	
	//定义一个方法，实现二分查找
	public static int search(int[] arr,int num) {
	    //1. 获取最小、大值的下标
	    int min = 0;
	    int max = arr.length -1;

	    while(min <= max) {
	        //2. 获取中间值的下标
	        int middle = (min + max) / 2;

	        //3. 将要查找的数字与中间值做比较
	        if(num > arr[middle]) {
	            min = middle +1;
	        }else if(num < arr[middle]) {
	            max = middle -1;
	        }else {
	            return middle;
	        }
	    }
	    return -1;
	}
}

3. 配套视频

为了方便大家更好地理解二分查找法，壹哥这里有对应的视频哦，链接如下：

bilibili html5 player

------------------------------正片已结束，来根事后烟----------------------------

三. 结语

至此，壹哥就把一维数组的内容给大家介绍完毕了，现在你知道数组有什么作用了吗？今日重点：

  • 常用的排序算法有冒泡排序、插入排序和快速排序等；
  • 冒泡排序使用两层for循环实现排序；
  • 交换两个变量的值需要借助一个临时变量。
  • 可以直接使用Java标准库提供的Arrays.sort()进行排序；
  • 对数组排序会直接修改数组本身。

对于数组，我们要掌握其基本用法，明白数组的扩容原理，并掌握数组的排序算法。如果你独自学习觉得有很多困难，可以加入壹哥的学习互助群，大家一起交流学习。

四. 今日作业

1. 第一题

录入班级学员的人数，然后循环给学员的名字赋值。之后输入一个名字，查找该学员是否在此班级中。


http://www.kler.cn/a/16539.html

相关文章：

  • C获取程序名称的方法
  • ubuntu ros 解决建完图后 保存的地图非常小的问题
  • 如何提高自动驾驶中惯性和卫星组合导航pbox的精度？
  • C#程序开发，检测当前电脑已经安装的软件目录
  • LLMs之Code：Github Spark的简介、安装和使用方法、案例应用之详细攻略
  • GitHub Org
  • scratch比大小 中国电子学会图形化编程 少儿编程 scratch编程等级考试三级真题和答案解析2023年3月
  • gRPC入门教程
  • 【Java笔试强训 25】
  • 时序预测 | MATLAB实现BO-CNN-BiLSTM贝叶斯优化卷积双向长短期记忆网络时间序列预测
  • Java 基础入门篇（四）—— 方法的重载与参数传递机制
  • 11.string，stringbuilder，stringbuffer的区别和联系。
  • 5. 操作系统基础
  • windows下定时备份mysql数据库
  • 第 02 章 OSPF实验
  • 【AI前沿】chatgpt还有哪些不足？
  • Python操作PostgreSQL数据库
  • 【学习视频】阅读开源工业软件和工业智能实战上线B站
  • 数字设计小思 - D触发器与死缠烂打的亚稳态
  • 五种最危险的新兴网络攻击技术
  • 《***生态文明思想学习纲要》学习辅导
  • git alias
  • 【Python】【进阶篇】16、settings.py配置文件详解
  • 登录关键字封装
  • 使用树莓派（zero2w + Camera Module 3 支持自动对焦 1200 万像素）拍照
  • JavaSE第三章 访问修饰符，Collection，List