文档章节

Java基础系列——数组相关算法(11)

卢佳鹏
 卢佳鹏
发布于 07/10 19:32
字数 4046
阅读 380
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

这里介绍一下数组中的常用算法

杨辉三角形

杨辉三角:它的两个边都是1,内部其它都是肩上两个数的和。

public class YangHui {
    public static void main(String[] args) {
        /**
         * 6行6列的杨辉三角
         */
        int row = 6;//行数
        int[][] yanghui = new int[row][row];//6行6列数组
        for (int i = 0; i < row; i++){//行
            for(int j = 0;j<= i;j++){//列
                if (j==0 || j==i){
                    yanghui[i][j]=1;
                }else{
                    yanghui[i][j]=yanghui[i-1][j-1]+yanghui[i-1][j];
                }
                System.out.print(yanghui[i][j]+" ");
            }
            System.out.println();
        }
    }
}





求数组中的最大、最小、平均数、总和等

这里要求数组的元素是数值类型,但是一般来说,这种都比较简单。示例如下:

public class TestArray04 {
    public static void main(String[] args) {
        // 最大值
        int max = 0 ;
        // 最小值
        int min = 0 ;
        // 总和
        int sum = 0 ;
        // 平均值
        int avg = 0 ;
        int[] arrays = {1,2,3,4,66,8,9,10};
        // 计算最大值
        for (int i = 0 ; i < arrays.length ; i++ ){
            if( max < arrays[i]){
                max = arrays[i] ;
            }
        }
        System.out.println( max );
        // 计算最小值
        for (int i = 0 ; i < arrays.length ; i++ ){
            // 因为在上边进行min的初始化,所以这里应该将min设置为数组中的元素,可以是任意元素
            min = arrays[0] ;
            if( min > arrays[i]){
                min = arrays[i] ;
            }
        }
        System.out.println( min );

        // 计算总和
        for (int i = 0 ; i < arrays.length ; i++ ){
            sum += arrays[i] ;
        }
        System.out.println( sum );

        // 计算平均数
        System.out.println( sum / arrays.length );
    }
}





数组的复制

其实就是将一个数组复制到另一个数组中。分别采用了自己手写的方法以及JDK内部提供的API。


/**
 * @ClassName TestArray05
 * @Description 复制数组
 * @Author lujiapeng
 **/
public class TestArray05 {
    public static void main(String[] args) {
        int[] source = {1,2,3,4,5,6,7,8} ;
        // 明确数组长度
        int[] dest = new int[ source.length ] ;
        for (int i = 0 ; i < source.length ; i ++ ){
            dest[i] = source[i] ;
        }
        // 循环输出 dest数组,查看是否一致
        for (int j : dest) {
            System.out.println( j );
        }
        // 使用 System 中的方法,进行复制
        /**
         * 方法描述 :
         *  arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);
         *   src : 表示原数组
         *   srcPos : 表示 原数组 要复制的位置
         *   dest : 目标数组
         *   destPos : 目标数组 开始的下标
         *   length : 复制元素的个数(也就是要复制几个)
         *  那么这个方法就可以随心的复制,同时可以明确是任意类型的数组。
         *  注意:目标数组和原数组的类型要匹配
         */
        System.arraycopy( source , 0 , dest , 0 , source.length );
        // 循环输出 dest数组,查看是否一致
        for (int j : dest) {
            System.out.println( j );
        }

        /**
         * 使用Arrays中的API,可以查看源码,底层依旧用的是 System.arraycopy
         *  Arrays.copyOf 与 Arrays.copyOfRange 两种方法
         */
        // 复制了 10 个元素 
        dest = Arrays.copyOf( source ,10  ) ;
        // 循环输出 dest数组,查看是否一致
        for (int j : dest) {
            System.out.println( j );
        }
    }
}






数组的查找

线性查找

从n个数字中查找指定的数字。

/**
 * @ClassName TestArray06
 * @Description 线性查找
 * @Author lujiapeng
 **/
public class TestArray06 {
    public static void main(String[] args) {
        int[] source = {1,2,3,4,5,6,7,8} ;
        int key= 8;
        for(int i = 0 ; i < source.length ; i++ ){
            if( source[i] == key ){
                System.out.println( "下标为:"+i );
                break ;
            }else if( (i+1) == source.length ){
                System.out.println("没有找到");
            }
        }
    }
}





二分查找

二分查找,又称折半查找。二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空,则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半,其时间复杂度是O(logN)。

这里分别用基础程序和Java提供的API进行实现

/**
 * @ClassName TestArray07
 * @Description 二分查找
 * @Author lujiapeng
 **/
public class TestArray07 {
    public static void main(String[] args) {
        int[] source = {1,2,3,4,5,6,7,8} ;
        int key= 18;
        boolean isFlag = true ;
        // 首索引位置
        int head = 0 ;
        // 尾索引位置
        int end = source.length - 1;
        while( head <= end ){
            int middle = ( head + end ) / 2 ;
            if( source[middle] == key ){
                System.out.println("找到指定元素,索引为:" + middle );
                isFlag = false ;
                break ;
            }else if( source[middle] > key ){
                end = middle -1 ;
            }else{
                // 此时表示的状态就是 source[middle] < key
                head = middle + 1 ;
            }
        }
        if( isFlag ){
            System.out.println("未找到指定元素");
        }
    }
}





API实现:

/**
 * @ClassName TestArray08
 * @Description 二分查找之使用JavaAPI
 * @Author lujiapeng
 **/
public class TestArray08 {
    public static void main(String[] args) {
        int[] source = {1,2,3,4,5,6,7,8} ;
        int key= 1;
        /**
         * 如果找到了对应的元素,则返回下标,如果没有找到,则返回一个负数。
         * 如果在一个数组中有多个相同元素,则不保证返回是具体的某一个(也就是在这些元素中随机返回一个)
         */
        int j = Arrays.binarySearch( source , key );
        System.out.println( j );
    }
}





排序算法

排序的基本概念

  • 排序:是计算机程序设计中的一项重要操作,其功能是指一个数据元素集合或序列重新排列成一个按数据元素某个数据项值有序的序列。
  • 排序码(关键码):排序依据的数据项
  • 稳定排序:排序前与排序后相同关键码元素间的位置关系,保持一致的排序方法。
  • 不稳定排序:排序前与排序后相同关键码元素间的相同位置发生改变的排序方法。

排序分为两类:

  • 内排序:指待排序列完全存放在内存中所进行的排序。内排序大致可分为五类:插入排序、交换排序、选择排序、归并排序和分配排序。
  • 外排序:指排序过程中还需外存储器的排序。

衡量排序算法的优劣

  • 时间复杂度:分析比较的次数和记录的移动次数
  • 空间复杂度:分析排序算法中许哟啊多少辅助内存
  • 稳定性:若两个记录A和B的关键字值相等,但排序后A、B的先后次序保 持不变,则称这种排序算法是稳定的

插入排序

基本思想:每次将一个待排序的元素,按其关键字的大小插入到前面已经排好序的子文件的适当位置,直到全部记录插入完成为止。

直接插入排序

直接插入排序的基本思想:把N个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有N-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

算法图示

示例如下:

/**
 * @ClassName InsertSort
 * @Description 直接插入算法
 * @Author lujiapeng
 **/
public class InsertSort {
    public static void main(String[] args) {
        int[] ints = {101, 92, 3, 34, 24, 234};
        //直接插入排序
        //把第一个数看成是有序的 ,所以从第二个数开始循环。
        for (int i = 1; i < ints.length; i++) {
            //内层循环 是从外层 循序的 前一个数开始 比
            for (int j = i - 1; j >= 0; j--) {
                // 如果前一个 比后一个大
                if (ints[j] > ints[j + 1]) {
                    int temp = ints[j] ;
                    ints[j] = ints[j+1] ;
                    ints[j+1] = temp ;
                }
            }
        }
        System.out.println(Arrays.toString(ints));
    }
}

直接插入排序的效率分析:首先从空间来看,它只需要一个元素的辅助空间,用于元素的位置交换。从时间分析,首先外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动0次;最多比较i次,移动i+1次(逆序)。因此,直接插入排序的时间复杂度为O(n2)。之际插入算法的元素移动时顺序的,该方法是稳定的。

希尔排序

希尔排序的基本思想:先将整个待排元素序列分割成若干个子序列(由像个某个“增量”的元素组成的)分别进行直接插入排序,待整个序列中的元素基本有序(增量足够下)时,再堆全体元素进行一次直接插入排序。因为直接插入排序再元素基本有序的情况下(接近最好情况),效率是很高的,因此写入排序在时间效率上有较大提高。

算法图示

代码实现:

/**
 * @ClassName XierSort
 * @Description TODO
 * @Author lujiapeng
 **/
public class XierSort {
    public static void main(String[] args) {
        int[] ints = {101, 92, 3, 34, 24, 234};
        // 步长
        for (int tap = ints.length / 2; tap > 0; tap /= 2) {
            for (int i = tap; i < ints.length; i++) {
                for (int j = i - tap; j >= 0; j -= tap) { // 控制每组的元素
                    if (ints[j] > ints[j + tap]) { // 如果逆序
                        int temp = ints[j]; // 则交换位置
                        ints[j] = ints[j + tap];
                        ints[j + tap] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(ints));
    }
}

虽然写出的算法是三层循环,最外层循环为log2n数量级,中间的for循环时n数量级,内层循环远远低于n数量级,因为当分组较少时,组内元素较少,次循环次数少;当分组较少时,组内元素增多,但是已经接近有序,循环次数并不增加。因此,希尔排序的时间复杂性在O(nlog2n) 和 O( n2 )之间。

由于 希尔排序对每个子序列单独比较,在比较时进行元素移动,有可能改变相同排序码元素的原始顺序,因此希尔排序时不稳定的。

交换排序

主要时通过排序表中两个记录关键码的比较,若与排序要求相逆(不符合升序或降序),则将两者交换。

冒泡排序

冒泡排序的基本思想:通过对待排序序列从前向后,一次比较相邻元素的排序码,若发信啊逆序则交换,使排序码较大的元素逐渐从前向后移动。

算法图示

代码示例如下:

/**
 * @ClassName EffervesceSort
 * @Description TODO
 * @Author lujiapeng
 **/
public class EffervesceSort {
    public static void main(String[] args) {
        //冒泡排序算法
        int[] numbers = new int[]{1, 5, 8, 2, 3, 9, 4};
        for ( int i = 0; i < numbers.length - 1; i++) {
            for (int j = 0; j < numbers.length - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }

            }
        }
        System.out.println(Arrays.toString( numbers ));
    }
}

从冒泡排序的算法可以看出,若待排序的元素为正序,则只需要进行一趟排序,比较次数为(n-1)次,移动元素次数为0;若待排序的元素为逆序,则需要进行n-1趟排序,比较次数为(n2-n)/2,移动次数为3(n2-n)/2,因此冒泡排序算法的时间复杂度为O(n2)。由于其中的元素移动较多,所以属于内排序中速度较慢的一种。因为冒泡排序算法只进行元素间的顺序移动,所以是一个稳定的算法。

快速排序( 分区交换排序 )

快速排序是迄今位置所有内排序算法中速度最快的一种。它的基本思想是:任取待排序序列中的某个元素作为基准(也称支点、界点,一般取第一个元素),通过一次划分,将待排元素分为左右两个子序列,左子序列元素的排序码均小于基准元素的排序码,右子序列的排序码则大于或等于基准元素的排序码,然后分别对两个子序列继续进行划分,直至每一个序列只有一个元素为止。最后得到的就是有序序列。

算法图示:

代码示例如下:

/**
 * @ClassName QuickSort
 * @Description TODO
 * @Author lujiapeng
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString( arr ));
    }
    /**
     * @param arr        待排序列
     * @param leftIndex  待排序列起始位置
     * @param rightIndex 待排序列结束位置
     */
    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = arr[left];
        //从左右两边交替扫描,直到left = right
        while (left < right) {
            while (right > left && arr[right] >= key) {
                //从右往左扫描,找到第一个比基准值小的元素
                right--;
            }
            //找到这种元素将arr[right]放入arr[left]中
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) {
                //从左往右扫描,找到第一个比基准值大的元素
                left++;
            }
            //找到这种元素将arr[left]放入arr[right]中
            arr[right] = arr[left];
        }
        //基准值归位
        arr[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, right + 1, rightIndex);
    }
}

如果每次划分对一个对象定位后,该对象的左子序列与右子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况。快速排序最好的时间复杂度位O(nlog2n)。最坏的时间复杂度是O(n2)

快速排序是递归的,需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致,理想情况位log2(n+1);最坏情况即待排序对象序列已经按其序码从小到大排好序的情况下,其递归树成为单支树,深度位n。因此,快速排序最好的空间复杂度位O(log2n),最坏的空间复杂度为O(n)(即快速排序所需要用的辅助空间)。

快速排序是一种不稳定的排序方法。

选择排序

基本原理:将待排序的元素分为已排序(初始为空)和未排序两组,一次将未排序的元素中值最小的元素放入已排序的组中。

简单选择排序

简单选择排序的基本过程为:

  1. 在以组元素R[i]到R[n] 中选择具有最小关键码的元素
  2. 若它不是这组元素中的第一个元素,则将它与这组元素中的第一个元素对调。
  3. 除去具有最小关键字的元素,在剩下的元素中重复1、2不,直到剩余元素只有一个为止。

算法图示:

代码示例:

/**
 * 直接选择排序
 * @author shkstart
 */
public class SelectSort {
	public static void selectSort(int[] data) {
		System.out.println("开始排序");
		int arrayLength = data.length;
		for (int i = 0; i < arrayLength - 1; i++) {
			for (int j = i + 1; j < arrayLength; j++) {
				if (data[i] - data[j] > 0) {
					int temp = data[i];
					data[i] = data[j];
					data[j] = temp;
				}
			}
			System.out.println(java.util.Arrays.toString(data));
		}
	}

	public static void main(String[] args) {
		int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
		System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
		selectSort(data);
		System.out.println("排序之后:\n" + java.util.Arrays.toString(data));
	}
}

归并排序

归并排序是一种概念上最简单的排序算法,与快速排序一样,归并排序也是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列,为每一个子序列排序,然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。

归并排序是一种稳定的排序算法,归并排序的主要问题在于它需要一个与待排序数组一样大的辅助数组空间。由于归并排序每次划分时两个子序列的长度基本一样,所以归并排序最好、最差和平均时间复杂度都是nlog2n。

算法图示:

代码示例:

/**
 * 归并排序
 * 
 * @author lujiapeng 
 */
public class MergeSort {
	public static void mergeSort(int[] data) {
		// 归并排序
		sort(data, 0, data.length - 1);
	}

	// 将索引从left到right范围的数组元素进行归并排序
	private static void sort(int[] data, int left, int right) {
		if(left < right){
			//找出中间索引
			int center = (left + right)/2;
			sort(data,left,center);
			sort(data,center+1,right);
			//合并
			merge(data,left,center,right);
		}
	}

	// 将两个数组进行归并,归并前两个数组已经有序,归并后依然有序
	private static void merge(int[] data, int left, int center, int right) {
		int[] tempArr = new int[data.length];
		int mid = center + 1;
		int third = left;
		int temp = left;
		while (left <= center && mid <= right) {
			if (data[left] - data[mid] <= 0) {
				tempArr[third++] = data[left++];
			} else {
				tempArr[third++] = data[mid++];
			}
		}
		while (mid <= right) {
			tempArr[third++] = data[mid++];
		}
		while (left <= center) {
			tempArr[third++] = data[left++];
		}
		while (temp <= right) {
			data[temp] = tempArr[temp++];
		}
	}

	public static void main(String[] args) {
		int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
		System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
		mergeSort(data);
		System.out.println("排序之后:\n" + java.util.Arrays.toString(data));
	}
}
卢佳鹏
粉丝 7
博文 18
码字总数 33439
作品 0
西安
程序员
私信 提问
加载中
请先登录后再评论。
访问安全控制解决方案

本文是《轻量级 Java Web 框架架构设计》的系列博文。 今天想和大家简单的分享一下,在 Smart 中是如何做到访问安全控制的。也就是说,当没有登录或 Session 过期时所做的操作,会自动退回到...

黄勇
2013/11/03
3.5K
6
浅入浅出Android(003):使用TextView类构造文本控件

基础: TextView是无法供编辑的。 当我们新建一个项目MyTextView时候,默认的布局(/res/layout/activity_main.xml)中已经有了一个TextView: <TextView 运行效果如下: 修改其文本内容...

樂天
2014/03/22
662
1
【opencv】图形的绘制

1.矩形图像的绘制: 原函数:void cvRectangle(CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8,int shift=0) img就是需要绘制的图像 pt1 and pt......

其实我是兔子
2014/10/08
1.2K
1
树莓派(Raspberry Pi):完美的家用服务器

自从树莓派发布后,所有在互联网上的网站为此激动人心的设备提供了很多有趣和具有挑战性的使用方法。虽然这些想法都很棒,但树莓派( RPi )最明显却又是最不吸引人的用处是:创建你的完美家用...

异次元
2013/11/09
6.6K
8
程序猿媛一:Android滑动翻页+区域点击事件

滑动翻页+区域点击事件 ViewPager+GrideView 声明:博文为原创,文章内容为,效果展示,思路阐述,及代码片段。文尾附注源码获取途径。 转载请保留原文出处“http://my.oschina.net/gluoyer...

花佟林雨月
2013/11/09
4.2K
1

没有更多内容

加载失败,请刷新页面

加载更多

matplotlib基础绘图命令之imshow

欢迎关注”生信修炼手册”! 在matplotlib中,imshow方法用于绘制热图,基本用法如下 import matplotlib.pyplot as plt import numpy as np np.random.seed(123456789) data = np.random...

庐州月光
昨天
0
0
[Bazel]自定义工具链

1 前言 2 Non-Platform 方式 3 Platform 方式 3.1 平台 3.2 工具链 3.3 Platform + Toolchain 实现平台方式构建 4 小结 1 前言 本文会讲述 Bazel 自定义工具链的两种方式,Platform 和 Non-...

别打名名
前天
0
0
浏览器在输入URL后,到底发生了什么?

这是一道面试会经常问的问题,平时虽然很常见的操作,但是探究其底层原理,可能并不是一件简单的事情,于是我从各处搜罗整理下全过程,在这里做分享。 第一步:浏览器输入域名 例如输入:www...

lintao111
前天
0
0
通过注解的方式整合 MyBatis + Spring Boot

目录 目录 1. 前言 2. 整合过程 2.1 新建 Spring Boot 项目 2.2 添加 pom 依赖 2.3 准备数据库 2.4 pojo 层 2.5 dao 层 2.7 controller 层 2.8 入口程序配置 2.9 网页测试 1. 前言 本篇博客主...

村雨遥
前天
0
0
字节跳动AI Lab 秋季正式批招聘

0 1 公司简介 字节跳动AI Lab,成立于2016年,致力于开发为字节跳动内容平台服务的创新技术,不仅仅是进行理论研究,我们的想法还可以通过实验证明和快速跟踪用于产品部署。 人工智能涉及的研...

我爱计算机视觉
前天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部