> 文档中心 > 07_星仔带你学Java之数组算法篇

07_星仔带你学Java之数组算法篇


 大家好,我是星仔。本博客收录于华星详谈-学习中心。本学习中心收集了Java整个技术体系的所有技术要点。每篇博客后面或者知识点结尾都附带有面试题,提供给大家巩固本章内容

为各位同胞们能够系统性的掌握整个Java技术体系而建立的学习中心。星仔正在努力的更新学习中心中的内容。望诸君共勉!!!

资料和代码存放地址:《华星详谈-学习中心》。开源项目持续更新中

GitHub - 17666555910/HuaXing-learningCenter: 华星详谈-学习中心。收集了Java目前市面上主要流行的技术细节以及对应的实现华星详谈-学习中心。收集了Java目前市面上主要流行的技术细节以及对应的实现. Contribute to 17666555910/HuaXing-learningCenter development by creating an account on GitHub.https://github.com/17666555910/HuaXing-learningCenterhttps://github.com/17666555910/HuaXing-learningCentericon-default.png?t=M3K6https://github.com/17666555910/HuaXing-learningCenter

目录

一、排序算法

1.1、排序的分类:

1.2、冒泡排序(Bubble Sort):

1.3、选择排序(Selection Sort):

二、数组的搜索算法

2.1、搜索算法实践

三、Java自带数组工具类Arrays


一、排序算法

排序:按照指定的顺序排列出来。共分为升序(从小到大)降序(从大到小)两种方式。

1.1、排序的分类

选择排序(直接选择排序、堆排序)

交换排序(冒泡排序、快速排序)

插入排序(直接插入排序、二分法插入排序、Shell排序)

归并排序等。

接再来星仔主要讲解冒泡,选择插入排序,当然在开发中因为性能问题,我们都不会自己写排序算法,不过排序在笔试题里却是常客。

我们都以以下这个需求为背景:若有下列int类型数组需要排序

int[] arr = {2,9,6,7,4,1};

1.2、冒泡排序(Bubble Sort)

这是最简单的排序法,基本思路:对未排序的各元素从头到尾依次比较相邻的两个元素大小关系,若大于则交换位置,经过第一轮比较排序后可得出最大值,然后使用同样的方法把剩下的元素逐个比较即可。

可以看出若有N个元素,那么一共要进行N-1轮比较,第M轮要进行N-M次比较。(若6个元素,要进行6-1轮比较,第一轮比较6-1次,第三轮比较6-3次)。

🍋冒泡排序算法分析

🍋冒泡排序Java代码

    /**     * 冒泡算法     *     * @param arr     * @return     */    public static int[] bubbleSort(int[] arr) { int temp; for (int i = 1; i <= arr.length - 1; i++) {     for (int j = 1; j  arr[j]) {      temp = arr[j - 1];      arr[j - 1] = arr[j];      arr[j] = temp;  }     } } return arr;    }

1.3、选择排序(Selection Sort)

基本思路:选择某个索引位置的元素,然后和后面元素依次比较,若大于则交换位置,经过第一轮比较排序后可得出最小值,然后使用同样的方法把剩下的元素逐个比较即可。

可以看出选择排序,第一轮会选出最小值,第二轮会选出第二小的值,直到最后。

第一轮从arr[0]和后面元素相比较,第二轮从arr[1]和后面的元素相比较,依次类推。N个数要进行N-1轮。选择排序每一轮只进行一次交换,相对于冒泡排序效率高一些。

🍋选择排序分析

 

🍋选择排序代码

    /**     * 选择排序     *     * @param arr     * @return     */    public static int[] electionSort(int[] arr) { int temp; for (int i = 1; i <= arr.length - 1; i++) {     for (int j = 1; j <= arr.length - i; j++) {  if (arr[j] < arr[j - 1]) {      temp = arr[j - 1];      arr[j - 1] = arr[j];      arr[j] = temp;  }     } } return arr;    }

ps:总的来说,冒泡排序的和选择排序实现方式基本上都是一样的,他们之前的区别在于冒泡排序是比较的最大值,而选择排序比较的是最小值。

二、数组的搜索算法

数组的搜索算法从指定数组中去搜索某一个元素的索引是多少.

  方式1:线性搜索(从头搜到尾/从尾搜到头)。调用indexOf/lastIndexOf方法。

              对于元素过多的数组性能极低;当有N个元素时,循环次数= (N + 1) / 2;

  方式2二分搜索法/二分查找法/折半查找

               前提:数组元素必须有顺序,当数据量很大时适宜采用该方法。采用二分法查找时,数据需是排好序的。

2.1、搜索算法实践

猜数游戏

一个朋友让你猜他正在想的一个从1到100之间的数,等你猜了,他会告诉你三种结果中的一个:你猜的比他想的大,或小,或猜中了。

为了能用最少的次数猜中,必须从50开始猜。如果他说你猜的小了,那么就能推出哪个数在50到100之间,所以马上猜75。但如果他说猜大了,你也能明白哪个说在1到50之间,所以马上猜25。如此重复,范围越来越小,直到猜到为止。

 

实现代码如下:

    /**     * 从arr数组中搜索key的元素,找到返回其索引,否则返回-1     *     * @param arr 排序后的数组     * @param key 需要查询的元素     * @return     */    public static int binarySearch(int[] arr, int key) { int low = 0;//最小的索引 int high = arr.length - 1;//最大的索 引 while (low > 1;//中间索引     int midVal = arr[mid];//中间的元索,猜测的值     if (midVal > key) {//猪大了  high = mid - 1;     } else if (midVal < key) {//猪小了  low = mid + 1;     } else {  return mid;     } } return -1;    }

三、Java自带数组工具类Arrays

数组的算法操作使用太频繁了,所以SUN公司就直接在JDK中提供了一个数组的工具类(Arrays)。

 

java.util.Arrays类:

1、int binarySearch(type[] arr,type key)  使用二分法查找数组里某元素并返回其索引,若找不到返回负数。

2、void sort(type[] arr)  使用调优后的快速法对指定数组排序。

3、String toString(type[] arr)  返回指定数组内容的字符串表示形式。

4、public static type[] copyOf(type[] original, int newLength)  复制指定的数组,截取或用 0 填充(如有必要),以使副本具有指定的长度。

使用注意:必须java.util.Arrays.方法(参数);

郁金香导航