数组、三种排序

数组是一组数据的集合,数组中的每个数据被称为元素。

在java中,数组也是对象,数组中的元素可以是任意类型(基本数据类型或引用类型),但同一个数组里只能存放类型相同的元素。相同的数据类型是指类型相同或兼容的数据,兼容就是允许自动类型转换。

args.length用于获取这个数组对象中的元素个数,length是数组的属性;
args[0] 是获取这个数组中,第一个元素的值,获取下标为0的元素;
Integer.parseInt()方法是将一个字符串转换为int数字。

任意类型+[]=相应的数组类型,任意类型可以是八大基本数据类型、引用类型String、接口类型。

数组变量:先使用一个已有的类型,然后加上中括号,组合成一个数组类型,然后再声明这个数组类型的变量。
1)数组类型的变量,也是引用类型变量,简称引用,它是可以指向对象的(数组对象)。
2)数组对象保存在内存的堆区中,是一块连续的内存空间,在这个连续的空间中,可以存放多个类型相同的数据。
3)数组对象中只有一个属性(length),表示数组的长度。方法只有从父类型Object中继承过来的方法。

数组长度,是指必须在一个数组对象中,最多可以存放多个同一类型的数据;必须创建数据对象的时候就明确指定;一旦确定之后,就无法再改变;可以为0,但不能为负数。

创建int类型数组对象:

int[] arr = new int[5];  //1)创建数组对象,没有还没有给其赋值。
int[] arr = new int[]{1,3,5,7,9};  //2)创建数组对象的同时,并赋值。
int[] arr = {1,3,5,7,9};  //3)java提供的创建数组对象的简便形式。
int[] arr; arr = new int[]{1,3,5,7,9};  //4)显示声明数组类型变量,然后创建对象,并赋值。

注意:指定长度和赋值不能同时进行。

数组拷贝:数组对象的长度确定后不能修改,但可以通过复制数组的内容,再创建不同长度的新数组实现。
java.lang.System类中提供了一个名为arraycopy的方法可以实现复制数组中元素的功能:
public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)
//src是需要被复制的目标数组,srcPos是目标数组中开始被复制的位置,dest是需要把数据复制到新的数组时,从新数组的什么位置开始复制进去,length是要复制目标数组里面多长的一组数据。

数组对象本身没有什么可以调用的方法,但API中有一个工具类Arrays,可以对数组对象进行一些基本操作。
java.util.Arrays中的常用类:
toString:把数组变成对应的String形式;
copyOf:底层通过arrayCopy方法实现;
copyOfRange:指定从哪一个下标位置开始复制;
sort:对数组进行排序;
binarySearch:返回这个指定的值在数组中的下标,但要先排序;
fill:把数组中的元素都赋成指定的特定值;
asList:把数据封装到List集合中并返回List集合对象。

冒泡排序,比较排序,插入排序
冒泡排序:在一组数据中,从左到右,俩俩比较,然后把较大的数据往前推,一轮下来之后,最大的一个数据就被推到了最右边。

package com.briup.day02;
import java.util.Arrays;
/**
 * 1.冒泡排序
 * (1)实现原理:
1.比较相邻的元素,如果第一个比第二个大,就交换他们两个。
2.对每一对相邻元素重复上述工作,从第一对到最后一对。完成后,最大的数会放到最后位置。
3.针对所有的元素重复以上的步骤,除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
 * (2)冒泡排序的优化:
如果排序进行了几次循环后,排序已经完成,就提前结束循环,不再进行遍历。
 */
public class BubbleSort {
	public static void main(String[] args) {
		BubbleSort sort = new BubbleSort();
		sort.testBubbleSort();
		System.out.println("冒泡排序的优化:");
		sort.testBubbleSort2();
	}
	// 基础冒泡排序
	public void bubbleSort(int[] array) {
		// 待排序元素的个数
		int length = array.length;
		// 如果数组的长度只有一个元素或者没有元素,不需要排序
		if (length <= 1) {
			return;
		}
		/**
		 *  外层循环控制整体排序的次数:
		 * i!=0,不然就多进行一次循环,会导致数组下标越界异常
		 */
		for (int i = 1; i < length; i++) {
			// 相邻比较
			for (int j = 0; j < length - i; j++) {
				//判断前后数据是否需要进行交换,如果前面的数据大于后面的数据,就进行交换,否则不交换
				if (array[j] > array[j + 1]) {
					int temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
				}
			}
			// 观察每次排序的结果:
			System.out.println("第" + i + "次排序后:" + Arrays.toString(array));
		}
	}
	public void testBubbleSort() {
		int[] array = new int[] { 7, 2, 1, 9, 0, 3 };
		System.out.println("排序前 : " + Arrays.toString(array));
		// 进行排序
		bubbleSort(array);
		// 输出排序结果
		System.out.println("排序后 : " + Arrays.toString(array));
	}
	public void bubbleSort2(int[] array) {
		int len = array.length;
		if (len <= 1) {
			return;
		}
		for (int i = 1; i < len; i++) {
			// 是否需要提前结束冒泡排序的标识
			boolean flag = true;
			for (int j = 0; j < len - i; j++) {
				if (array[j] > array[j + 1]) {
					int temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;
					flag = false;
				}
				// 如果排序已经完成,后面就不需要进行遍历
			}
			if (flag) {
				break;
			}
			System.out.println("第" + i + "次排序后:" + Arrays.toString(array));
		}
	}
	public void testBubbleSort2() {
		int[] array = new int[] { 7, 2, 1, 9, 0, 3 };
		System.out.println("排序前 : " + Arrays.toString(array));
		bubbleSort2(array);
		System.out.println("排序后 : " + Arrays.toString(array));
	}
}

选择排序:每一轮在待排序的区域中比较找到一个最小值后,把这个最小值放到已经排好顺序的区域的末尾,剩下的部分,组成一个新的待排序部分,重复上面的步骤直到排序结束。

package com.briup.day02;
import java.util.Arrays;
/**
 * 3.选择排序
 * (1)实现原理:
1.把数组分成俩部分,将后面部分的数据一个一个的和前面部分数据的元素进行比较,
2.如果我们指定的元素比前面部分的元素小,那么就将前面的元素往前移动一步,
3.直到没有比我们这个指定元素还小的元素了,那么这个位置就是需要插入的地方。
 */
public class SelectionSort {
	public static void main(String[] args) {
		SelectionSort sort = new SelectionSort();
		sort.testSelectionSort();
	}
	public void selectionSort(int[] arr) {
		int len = arr.length;
		if (len <= 1) {
			return;
		}
		for (int i = 0; i < len - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < len; j++) {
				if (arr[minIndex] > arr[j]) {
					minIndex = j;
				}
			}
			if (minIndex != i) {
				arr[minIndex] = arr[minIndex] ^ arr[i];
				arr[i] = arr[minIndex] ^ arr[i];
				arr[minIndex] = arr[minIndex] ^ arr[i];
			}
			System.out.println("第"+(i+1)+"次排序"+Arrays.toString(arr));
		}
	}
	public void testSelectionSort() {
		int[] array = {7, 2, 5, 1, 9, 0, 3};
		System.out.println("排序前: " + Arrays.toString(array));
		selectionSort(array);
		System.out.println("排序后: " + Arrays.toString(array));
	}
}

插入排序:把数组分成俩部分,将后面部分的数据一个一个的和前面部分数据的元素进行比较,如果我们指定的元素比前面部分的元素小,那么就将前面的元素往前移动一步,直到没有比我们这个指定元素还小的元素了,那么这个位置就是需要插入的地方。

package com.briup.day02;
import java.util.Arrays;
/**
 * 2.插入排序
 * (1)实现原理:
1.每一轮在待排序的区域中比较找到一个最小值后,把这个最小值放到已经排好顺序的区域的末尾,
2.剩下的部分组成一个新的待排序部分,重复上面的步骤直到排序结束。
 */
public class InsertionSort {
	public static void main(String[] args) {
		InsertionSort sort = new InsertionSort();
		sort.testInsertionSort();
	}
	public void insertionSort(int[] arr) {
		int len = arr.length;
		if (len <= 1) {
			return;
		}
		for (int i = 1; i < len; i++) {
			int value = arr[i];
			int j = i - 1;
			for (; j >= 0; j--) {
				if (value < arr[j]) {
					arr[j + 1] = arr[j];
				} else {
					break;
				}
			}
			arr[j + 1] = value;
			System.out.println("第" + i + "次排序后:" + Arrays.toString(arr));
		}
	}
	public void testInsertionSort() {
		int[] array = { 7, 2, 6, 1, 9, 0, 3 };
		System.out.println("排序前: " + Arrays.toString(array));
		insertionSort(array);
		System.out.println("排序后: " + Arrays.toString(array));
	}
}
上一篇:ecshop foreach控制文章显示条数


下一篇:PyTorch初步学习day4