likes
comments
collection
share

数组中这些常用算法你掌握了吗?

作者站长头像
站长
· 阅读数 33

今天继续Java系列,上篇讲了Java数组,今天来看下数组的常见算法。

算法概述

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷不适合于某个问题,那么执行这个算法将不会解决问题。

算法效率的两个重要衡量指标是时间复杂度和空间复杂度。

时间复杂度

时间复杂度是指执行算法所需要的计算工作量,可以通过分析算法中的循环次数来得到。

常见的算法时间复杂度由小到大依次为:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

:经常将以2为底n的对数简写成logn。

空间复杂度

空间复杂度是指执行这个算法所需要的内存空间,它也是问题规模n的函数,可以通过分析算法中的变量个数来得到。

时间复杂度和空间复杂度都是用O表示的,例如O(n)、O(n^2) 等等。

常见算法

数组特征值统计

这里的特征值是指:平均值、最大值、最小值、总和等。

下面举个例子:找最值及其第一次出现的下标。

public class TestMaxIndex {
    public static void main(String[] args) {
        int[] arr = {4,5,6,1,9};
        //找最大值以及第一个最大值下标
        int max = arr[0];
        int index = 0;
        for(int i=1; i<arr.length; i++){
            if(arr[i] > max){
                max = arr[i];
                index = i;
            }
        }
        System.out.println("max = " + max);
        System.out.println("index = " + index);
    }
}

再来个难点的例子看下:输入一个整形数组,数组里有正数也有负数,数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如:输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。

public class Test {
	public static void main(String[] args) {
		int[] arr = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
		int i = getGreatestSum(arr);
		System.out.println(i);
	}
	public static int getGreatestSum(int[] arr){
		int greatestSum = 0;
		if(arr == null || arr.length == 0){
			return 0;
		}
		int temp = greatestSum;
		for(int i = 0;i < arr.length;i++){
			temp += arr[i];
			if(temp < 0){
				temp = 0;
			}
			if(temp > greatestSum){
				greatestSum = temp;
			}
		}
		if(greatestSum == 0){
			greatestSum = arr[0];
			for(int i = 1;i < arr.length;i++){
				if(greatestSum < arr[i]){
					greatestSum = arr[i];
				}
			}
		}
		return greatestSum;
	}
}

数组赋值与数组复制

这里看个经典的例子:回形数。 从键盘输入一个整数(1-20) ,则以该数字为矩阵的大小,把1,2,3…n*n 的数字按照顺时针螺旋的形式填入其中。

例如:

输入数字2,则程序输出:

1 2

4 3

输入数字3,则程序输出:

1 2 3

8 9 4

7 6 5

输入数字4, 则程序输出:

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

/**例如1-49的回形数:
	01 02 03 04 05 06 07 
	24 25 26 27 28 29 08 
	23 40 41 42 43 30 09 
	22 39 48 49 44 31 10 
	21 38 47 46 45 32 11 
	20 37 36 35 34 33 12 
	19 18 17 16 15 14 13 
 */
public class RectangleTest {
	public static void main(String[] args) {
		int n = 7;
		int[][] arr = new int[n][n];
		int count = 0; //要显示的数据
		int maxX = n-1; //x轴的最大下标
		int maxY = n-1; //Y轴的最大下标
		int minX = 0; //x轴的最小下标
		int minY = 0; //Y轴的最小下标
		while(minX<=maxX) {
			for(int x=minX;x<=maxX;x++) {
				arr[minY][x] = ++count;
			}
			minY++;
			for(int y=minY;y<=maxY;y++) {
				arr[y][maxX] = ++count;
			}
			maxX--;
			for(int x=maxX;x>=minX;x--) {
				arr[maxY][x] = ++count;
			}
			maxY--;
			for(int y=maxY;y>=minY;y--) {
				arr[y][minX] = ++count;
			}
			minX++;
		}
		for(int i=0;i<arr.length;i++) {
			for(int j=0;j<arr.length;j++) {
				String space = (arr[i][j]+"").length()==1 ? "0":"";
				System.out.print(space+arr[i][j]+" ");
			}
			System.out.println();
		}
	}
}

数组元素的反转

实现思想:数组对称位置元素互换。

方式1图解:

数组中这些常用算法你掌握了吗?

方式1代码实现:

public class TestArrayReverse1 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println("反转之前:");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        //反转
        /**思路:首尾对应位置的元素交换
        确定交换几次:次数 = 数组.length / 2
        确定交换对象:
        for(int i=0; i<次数; i++){
             int temp = arr[i];
             arr[i] = arr[arr.length-1-i];
             arr[arr.length-1-i] = temp;
        }
         */
        for(int i=0; i<arr.length/2; i++){
            int temp = arr[i];
            arr[i] = arr[arr.length-1-i];
            arr[arr.length-1-i] = temp;
        }
        System.out.println("反转之后:");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

方式2图解:

数组中这些常用算法你掌握了吗?

方式2代码实现:

public class TestArrayReverse2 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println("反转之前:");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        //反转
        //左右对称位置交换
        for(int left=0,right=arr.length-1; left<right; left++,right--){
            //首尾交换
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        System.out.println("反转之后:");
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

数组扩容与缩容

数组的扩容:现有数组int[] arr = new int[]{1,2,3,4,5};,现将数组长度扩容1倍,并将10,20,30三个数据添加到arr数组中。

public class ArrTest1 {
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5};
        int[] newArr = new int[arr.length << 1];
        for(int i = 0;i < arr.length;i++){
            newArr[i] = arr[i];
        }
        newArr[arr.length] = 10;
        newArr[arr.length + 1] = 20;
        newArr[arr.length + 2] = 30;
        arr = newArr;
        //遍历arr
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

数组的缩容:现有数组int[] arr={1,2,3,4,5,6,7},现需删除数组中索引为4的元素。

public class ArrTest2 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        //删除数组中索引为4的元素
        int delIndex = 4;
        /**方式1:
        int[] newArr = new int[arr.length - 1];
        for (int i = 0; i < delIndex; i++) {
            newArr[i] = arr[i];
        }
        for (int i = delIndex + 1; i < arr.length; i++) {
            newArr[i - 1] = arr[i];
        }
        arr = newArr;
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
         */
        //方式2:
        for (int i = delIndex; i < arr.length - 1; i++) {
            arr[i] = arr[i + 1];
        }
        arr[arr.length - 1] = 0;
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

数组元素的查找

这里看下经典的二分法查找,程序流程图如下:

数组中这些常用算法你掌握了吗?

代码实现:

//二分法查找要求此数组必须是有序的
int[] arr3 = new int[]{-99,-54,-2,0,2,33,43,256,999};
boolean isFlag = true;
int value = 256;
//int value = 25;
int head = 0; //首索引位置
int end = arr3.length - 1; //尾索引位置
while(head <= end){
    int middle = (head + end) / 2;
    if(arr3[middle] == value){
        System.out.println("找到指定的元素,索引为:" + middle);
        isFlag = false;
        break;
    }else if(arr3[middle] > value){
        end = middle - 1;
    }else{ //arr3[middle] < value
        head = middle + 1;
    }
}
if(isFlag){
    System.out.println("未找到指定的元素");
}

数组元素的排序

排序算法概述

内部排序:整个排序过程不需要借助于外部存储器(如磁盘等),所有排序操作都在内存中完成。

外部排序:参与排序的数据非常多,数据量非常大,计算机无法把整个排序过程放在内存中完成,必须借助于外部存储器(如磁盘)。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

十大内部排序算法对比:

数组中这些常用算法你掌握了吗?

冒泡排序

排序思想:

  1. 比较相邻的元素,如果第一个比第二个大(升序),就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较为止。

冒泡排序图解:

数组中这些常用算法你掌握了吗?

冒泡排序代码实现:

/**
思想:每一次比较“相邻(位置相邻)”元素,如果它们不符合目标顺序(例如:从小到大),
     就交换它们,经过多轮比较,最终实现排序。
    (例如:从小到大)每一轮可以把最大的沉底,或最小的冒顶。
过程:arr{6,9,2,9,1}  目标:从小到大
第一轮:
	第1次,arr[0]与arr[1],6>9不成立,满足目标要求,不交换
	第2次,arr[1]与arr[2],9>2成立,不满足目标要求,交换arr[1]与arr[2] {6,2,9,9,1}
	第3次,arr[2]与arr[3],9>9不成立,满足目标要求,不交换
	第4次,arr[3]与arr[4],9>1成立,不满足目标要求,交换arr[3]与arr[4] {6,2,9,1,9}
	第一轮所有元素{6,9,2,9,1}已经都参与了比较,结束。
	第一轮的结果:第“一”最大值9沉底(本次是后面的9沉底),即到{6,2,9,1,9}元素的最右边
第二轮:
	第1次,arr[0]与arr[1],6>2成立,不满足目标要求,交换arr[0]与arr[1] {2,6,9,1,9}
	第2次,arr[1]与arr[2],6>9不成立,满足目标要求,不交换
	第3次:arr[2]与arr[3],9>1成立,不满足目标要求,交换arr[2]与arr[3] {2,6,1,9,9}
	第二轮未排序的所有元素 {6,2,9,1}已经都参与了比较,结束。
	第二轮的结果:第“二”最大值9沉底(本次是前面的9沉底),即到{2,6,1,9}元素的最右边
第三轮:
	第1次,arr[0]与arr[1],2>6不成立,满足目标要求,不交换
	第2次,arr[1]与arr[2],6>1成立,不满足目标要求,交换arr[1]与arr[2] {2,1,6,9,9}
	第三轮未排序的所有元素{2,6,1}已经都参与了比较,结束。
	第三轮的结果:第三最大值6沉底,即到 {2,1,6}元素的最右边
第四轮:
	第1次,arr[0]与arr[1],2>1成立,不满足目标要求,交换arr[0]与arr[1] {1,2,6,9,9}
	第四轮未排序的所有元素{2,1}已经都参与了比较,结束。
	第四轮的结果:第四最大值2沉底,即到{1,2}元素的最右边
*/
public class TestBubbleSort{
    public static void main(String[] args){
        int[] arr = {6,9,2,9,1};
        //目标:从小到大
        //冒泡排序的轮数 = 元素的总个数 - 1
        //轮数是多轮,每一轮比较的次数是多次,需要用到双重循环,即循环嵌套
        //外循环控制 轮数,内循环控制每一轮的比较次数和过程
        for(int i=1; i<arr.length; i++){ //循环次数是arr.length-1次/轮
			/**
			假设arr.length=5
			i=1,第1轮,比较4次
				arr[0]与arr[1]
				arr[1]与arr[2]
				arr[2]与arr[3]
				arr[3]与arr[4]
				arr[j]与arr[j+1],int j=0;j<4; j++
			i=2,第2轮,比较3次
				arr[0]与arr[1]
				arr[1]与arr[2]
				arr[2]与arr[3]
				arr[j]与arr[j+1],int j=0;j<3; j++
			i=3,第3轮,比较2次
				arr[0]与arr[1]
				arr[1]与arr[2]
				arr[j]与arr[j+1],int j=0;j<2; j++
			i=4,第4轮,比较1次
				arr[0]与arr[1]
				arr[j]与arr[j+1],int j=0;j<1; j++
				int j=0; j<arr.length-i; j++
			*/
            for(int j=0; j<arr.length-i; j++){
                //希望的是arr[j] < arr[j+1]
                if(arr[j] > arr[j+1]){
                    //交换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]+"  ");
        }
    }
}

冒泡排序的优化:

class TestBubbleSort2{
	public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        //从小到大排序
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true; //假设数组已经是有序的
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //希望的是arr[j] < arr[j+1]
                if (arr[j] > arr[j + 1]) {
                    //交换arr[j]与arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false; //如果元素发生了交换,那么说明数组还没有排好序
                }
            }
            if (flag) {
                break;
            }
        }
        //完成排序,遍历
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }
}

快速排序

快速排序(Quick Sort)由图灵奖获得者Tony Hoare发明,被列为20世纪十大算法之一,是迄今为止所有内排序算法中速度最快的一种,快速排序的时间复杂度为O(nlog(n))。

快速排序通常明显比同为O(nlogn)的其他算法更快,因此常被采用,而且快排采用了分治法的思想,所以在很多笔试面试中能经常看到快排的影子。

排序思想:

  1. 从数列中挑出一个元素,称为"基准"(pivot)。
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归的(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
  4. 递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

快速排序图解: 第一轮操作:

数组中这些常用算法你掌握了吗?

第二轮操作:

数组中这些常用算法你掌握了吗?

内部排序性能比较与选择

性能比较:

  • 从平均时间而言,快速排序最佳,但在最坏情况下时间性能不如堆排序和归并排序
  • 从算法简单性看,由于直接选择排序、直接插入排序和冒泡排序的算法比较简单,将其认为是简单算法。对于Shell排序、堆排序、快速排序和归并排序算法,其算法比较复杂,认为是复杂排序
  • 从稳定性看,直接插入排序、冒泡排序和归并排序时稳定的,而直接选择排序、快速排序、 Shell排序和堆排序是不稳定排序
  • 从待排序的记录数n的大小看,n较小时宜采用简单排序,而n较大时宜采用改进排序

选择:

  • 若n较小(如n≤50),可采用直接插入或直接选择排序。 当记录规模较小时,直接插入排序较好,否则因为直接选择移动的记录数少于直接插入,应选直接选择排序为宜
  • 若文件初始状态基本有序(指正序),则应选用直接插入、冒泡或随机的快速排序为宜
  • 若n较大则应采用时间复杂度为O(nlgn)的排序方法,比如快速排序、堆排序或归并排序

工具类Arrays

上面介绍的算法要掌握,但是开发中一般不会自己实现,开发中一般直接调用现有的工具类Arrays。java.util.Arrays类即为操作数组的工具类,包含了用来操作数组(比如排序和搜索)的各种方法。

比如:

  1. 数组元素拼接。
    • static String toString(int[] a):字符串表示形式由数组的元素列表组成,括在方括号中。相邻元素用字符 ", "(逗号加空格)分隔。形式为[元素1,元素2,元素3。。。]
    • static String toString(Object[] a):字符串表示形式由数组的元素列表组成,括在方括号中。相邻元素用字符 ", "(逗号加空格)分隔。元素将自动调用自己从Object继承的toString方法将对象转为字符串进行拼接,如果没有重写,则返回类型@hash值,如果重写则按重写返回的字符串进行拼接
  2. 数组排序。
    • static void sort(int[] a):将a数组按照从小到大进行排序
    • static void sort(int[] a, int fromIndex, int toIndex):将a数组的[fromIndex, toIndex)部分按照升序排列
    • static void sort(Object[] a):根据元素的自然顺序对指定对象数组按升序进行排序
    • static <T> void sort(T[] a, Comparator<? super T> c):根据指定比较器产生的顺序对指定对象数组进行排序
  3. 数组元素的二分查找。
    • static int binarySearch(int[] a, int key)static int binarySearch(Object[] a, Object key):要求数组有序,在数组中查找key是否存在,如果存在返回第一次找到的下标,不存在返回负数
  4. 数组的复制。
    • static int[] copyOf(int[] original, int newLength):根据original原数组复制一个长度为newLength的新数组,并返回新数组
    • static <T> T[] copyOf(T[] original,int newLength):根据original原数组复制一个长度为newLength的新数组,并返回新数组
    • static int[] copyOfRange(int[] original, int from, int to):复制original原数组的[from,to)构成新数组,并返回新数组
    • static <T> T[] copyOfRange(T[] original,int from,int to):复制original原数组的[from,to)构成新数组,并返回新数组
  5. 比较两个数组是否相等。
    • static boolean equals(int[] a, int[] a2):比较两个数组的长度、元素是否完全相同
    • static boolean equals(Object[] a,Object[] a2):比较两个数组的长度、元素是否完全相同
  6. 填充数组。
    • static void fill(int[] a, int val):用val值填充整个a数组
    • static void fill(Object[] a,Object val):用val对象填充整个a数组
    • static void fill(int[] a, int fromIndex, int toIndex, int val):将a数组[fromIndex,toIndex)部分填充为val值
    • static void fill(Object[] a, int fromIndex, int toIndex, Object val):将a数组[fromIndex,toIndex)部分填充为val对象

举例:

import java.util.Arrays;
public class SortTest {
	public static void main(String[] args) {
		int[] arr = {3, 2, 5, 1, 6};
        System.out.println("排序前" + Arrays.toString(arr));
        Arrays.sort(arr);
        System.out.println("排序后" + Arrays.toString(arr));
	}
}

数组常见异常

数组角标越界

当访问数组元素时,下标指定超出[0, 数组名.length-1]的范围时,就会报数组下标越界异常:ArrayIndexOutOfBoundsException

public class TestArrayIndexOutOfBoundsException {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        //System.out.println("最后一个元素:" + arr[3]); //错误,下标越界
        //System.out.println("最后一个元素:" + arr[arr.length]); //错误,下标越界
        System.out.println("最后一个元素:" + arr[arr.length-1]); //对
    }
}

空指针异常

当访问数组中还未分配具体存储元素的空间时,会抛出NullPointerException空指针异常。

public class TestNullPointerException {
    public static void main(String[] args) {
        //定义数组
        int[][] arr = new int[3][];
        System.out.println(arr[0][0]); //NullPointerException
    }
}

最后,今天的内容就到这里,Java教程持续更新中,喜欢的话点个关注吧,下篇见!

转载自:https://juejin.cn/post/7216705712684007481
评论
请登录