数组与排序

数组与排序

数组

一,数组的概念

数组是一个可以存储多个相同数据类型的容器。可以让我们更方便的操作多个数据

二,数组的初始化

(1)什么是数组的初始化

java中的数组必须先初始化，然后才能使用

初始化：就是给数组中的数组元素分配内存空间，并未每个数组元素赋值。

(2)数组初始化的分类

1. 动态初始化： 只指定长度，有系统给出初始化值

2. 静态初始化： 给出初始化值，由系统决定长度

注意事项：这两种初始化方式只能使用一种，不能动静结合

(3)动态初始化的格式：

数据类型[] 数组名 = new 数据类型[数组长度]；

int[] arr = new int[5];

ps：数组长度其实就是数组中元素的个数。

(4)静态初始化的格式：

数据类型[] 数组名 = new 数据类型[] {数组元素,数组元素};

int[] arr = new int[]{1,2,3,4,5}；

静态数组的简写

int[] arr = {1,2,3,4,5}；

三,数组的使用

1. 动态初始化的数组，在定义的同事已经被赋值 例如：int数组默认值位“0”

2. 数组通过下标取得数组元素；

   int num = arr[1];

3. 数组通过下标修改数组元素：

   arr[1] = 20;

四,数组的常见操作

通过[数组.length]可以获取数组中数组元素的个数

int length = arr.length;

(1)数组的元素遍历

• 通过for循环来遍历数组

  for(int i = 0; i < arr.length; i++){System.out.println(arr[i]);
  }

• 通过增强for循环遍历数组

  for(int i : arr){System.out.println(i);
  }

(2)数组常见的下标越界异常

ArrayIndexOutOfBoundsException

(3)数组的反向遍历

通过for循环来反向遍历数组

for(int i = arr.length - 1; i > 0; i--){System.out.println(arr[i]);
}

(4)获取数组元素的最大值或最小值

获取数组元素的最大值

int max = arr[0];
for(int i = 1; i < arr.length; i++){if(arr[i] > max){max = arr[i];}
}
​
System.out.pringln("数组中的最大值:" + max)

获取数组元素的最小值

int min = arr[0];
for(int i = 1; i < arr.length; i++){if(arr[i] < min){max = arr[i];}
}System.out.pringln("数组中的最小值:" + min)

(5)数组元素的反转

思路:首尾元素互换

for(int i = 0; i < arr.length / 2; i++){int temp = arr[i];arr[i] = arr[length - i - 1];arr[length - i - 1] = temp;
}

五,二维数组

(1)二维数组概述

二维数组:其实就是一维数组的数组

(2)二维数组定义格式

• 动态初始化(我们指定数组的长度,由系统为数组元素赋默认值)二维数组

  // 我们定义的一个二维素组,这个二维数组里面有三个一维数组,每个一维数组中有两个数组元素
  int[][] arr = new int[3][2];
  // 取得二维数组中的一维数组
  int[] arr1 = arr[0];
  // 取得二维数组中的值
  int value = arr[0][0];

• 静态初始化(我们给数组赋值,由系统为数组分配空间)二维数组

  // 我们定义的一个二维素组
  int[][] arr = new int[][]{{1,2},{3,4},{4,5}};
  // 取得二维数组中的3
  int int_3 = arr[1][0];
  // 取得二维数组中的5
  int int_5 = arr[2][1];
  // 取得数组元素中最后一个数组元素
  int int_last = arr[arr.lengthh - 1][arr[arr.lengthh - 1].length - 1]

• 二维数组的使用和一位数组相同,都是通过下标对数组元素进行操作

• 二维数组的其他定义方式

  // 二维数组的简化方式
  int[][] arr = {{1,2},{3,4},{4,5}};
  ​
  // 二维数组的其他定义方式(不建议使用)
  int arr[][] = {{1,2},{3,4},{4,5}};
  int[] arr[] = {{1,2},{3,4},{4,5}};
  ​
  // 定义了一个一维数组g,和一个二维素组j
  int[] g,j[];

(3)二维数组的遍历

• 通过for循环来遍历数组

  for(int i = 0; i < arr.length; i++){// System.out.println(arr[i]);for(int j = 0; j < arr[i].length; j++){System.out.println(arr[i][j]);}
  }

(4)二维数组的练习

案例演示1:

​

/*需求:公司销售额求和:
某公司按照季度和月份统计的数据如下:单位(万元 )
第一季度:22,66,44
第二季度:77,33,88
第三季度:25,45,65
第四季度:11,66,99*/
int[][] arr = {{22, 66, 44}, {77, 33, 88}, {25, 45, 65}, {11, 66, 99}};
int sum = 0;
for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[i].length; j++) {sum += arr[i][j];}
}
​
System.out.println("总销售额为:" + sum);

案例演示2:

        /** 需求: 打印杨辉三角形(行数可以键盘录入)* 1* 1 1* 1 2 1* 1 3 3 1* 1 4 6 4 1* 1 5 10 10 5 1** 观察发现:* 1.每一行的第一列和最后一列都是1* 2.从第三行开始,从第二列开始,每个数字等于她上一行的前一列,和上一行本列之和* 3.行数和列数相同**/Scanner sc = new Scanner(System.in);System.out.println("请输入行数:");int n = sc.nextInt();// 定义二维数组,存储数据int arr[][] = new int[n][n];// 每一行的第一列和最后一列都是1for (int i = 0; i < arr.length; i++) {arr[i][0] = 1;arr[i][i] = 1;}
​// 设置中间元素// 2.从第三行开始,从第二列开始,每个数字等于她上一行的前一列,和上一行本列之和for (int i = 2; i < arr.length; i++) {for (int j = 1; j < arr[i].length; j++) {arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];}}
​// 遍历数组for (int i = 0; i < arr.length; i++) {for (int j = 0; j <= i; j++) {System.out.print(arr[i][j] + "t");}System.out.println("");}

(5)查找

根据元素查找出该元素,在数组中第一次出现的索引

1. 基本查找

public int getIndexByElement(int ele, int[] arr){// 目标索引int index = -1;// 遍历数组for (int i = 0; i < arr.length; i++) {if(ele == arr[i]){index = i;}}return index;
}

1. 二分查找

   前提:该数组元素必须有序

   思想:每次都查找中间的元素,比较大小,就能减少一半的元素

   步骤:

   1).设置最大索引=arr.length-1,最小索引=0和中间索引=(最大索引+最小索引)/2

   2).取中间索引所对应的元素与目标元素比较

   3).比较之后有三种

   ①.目标元素等于中间索引所对应的元素,返回中间索引,结束方法

   ②.目标元素小于中间索引所对应的元素,改变最大索引=中间索引-1,中间索引再次取(最大索引+最小索引)/2,执行2)

   ③.目标元素大于中间索引所对应的元素,改变最小索引=中间索引+1,中间索引再次取(最大索引+最小索引)/2,执行2)

   4).当最小索引大于最大索引,返回-1,方法结束

   public static int getIndexByEle(int[] arr, int ele) {// 定义最小索引,最大索引,中间索引int minIndex = 0;int maxIndex = arr.length - 1;int midIndex = (maxIndex + minIndex) / 2;while (minIndex <= maxIndex) {// ①.目标元素等于中间索引所对应的元素,返回中间索引,结束方法if (ele == arr[midIndex])return midIndex;// ②.目标元素小于中间索引所对应的元素,改变最大索引=中间索引-1else if (ele < arr[midIndex])maxIndex = midIndex - 1;// ③.目标元素大于中间索引所对应的元素,改变最小索引=中间索引+1else if (ele > arr[midIndex])minIndex = midIndex + 1;// 重新计算midIndexmidIndex = (maxIndex + minIndex) / 2;}// 当最小索引大于等于最大索引,目标元素不存在这个数组中,返回-1,方法结束return -1;
   }

数组常见的排序算法

一,冒泡排序

排序原理:数组元素两两比较,交换位置,大元素往后放,最大的元素就会出现在最大的索引处

总结规律:

假设数组有5个元素;

第一轮需要比较4次(第一个元素和其他元素比较)

第二轮需要比较3次(第一轮确定了一个最大值,排除在比较范围之外)

第三轮需要比较2次

第四轮需要比较1次

假设数组有n个元素;

第一轮需要比较n-1次(第一个元素和其他元素比较)

第二轮需要比较n-2次(第一轮确定了一个最大值,排除在比较范围之外)

......

第n-2轮需要比较2次

第n-1轮需要比较1次

public static void bubbleSort(int[] arr) {// 外循环为排序轮数，len个数进行len-1轮for (int i = 0; i < arr.length - 1; i++) {// 内循环为每轮比较的次数，第i趟比较len-i次for (int j = 0; j < arr.length - 1 - i; j++) {// 相邻元素比较，若逆序则交换（升序为左大于右，降序反之）if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

二,选择排序

原理:从0索引处开始,一次和后面的元素进行比较,小的元素往前放,经过一轮比较后,最小的元素就出现在了最小索引处

总结规律:

假设数组有5个元素;

第一轮需要比较4次(第一个元素和其他元素比较)

第二轮需要比较3次(第一轮确定了一个最小值,排除在比较范围之外)

第三轮需要比较2次

第四轮需要比较1次

假设数组有n个元素;

第一轮需要比较n-1次(第一个元素和其他元素比较)

第二轮需要比较n-2次(第一轮确定了一个最小值,排除在比较范围之外)

......

第n-2轮需要比较2次

第n-1轮需要比较1次

public static void selectionSort(int[] arr) {// 外循环为排序轮数，len个数进行len-1轮for (int i = 0; i < arr.length - 1; i++) {// 内循环为每轮比较的次数，第i趟比较len-i次for (int j = i + 1; j < arr.length; j++) {// 元素比较，若逆序则交换（升序为左大于右，降序反之）if (arr[i] > arr[j]) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}}
}

三,插入排序

原理:直接插入排序,是一种最简单排序方法,她的基本操作是讲一个记录插入到一个长度为m的有序序列总,是指仍保持有序

public static void insertionSort(int[] arr) {// 外循环为排序轮数，从一个元素的有序列表开始for (int i = 1; i < arr.length; i++) {
​int j = i;// 内循环进行比较交换while (j > 0 && arr[j] < arr[j - 1]) {int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;j--;}}
}
​
public static void insertionSort2(int[] arr) {// 外循环为排序轮数，从一个元素的有序列表开始for (int i = 1; i < arr.length; i++) {// 内循环进行比较交换for (int j = i; j > 0; j--) {if (arr[j] < arr[j - 1]) {int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}}
}

四,希尔排序

希尔排序又称缩小增量排序.是对插入排序的优化

• 基本思想:先将原来的数组按照增量ht分组,每个子序列按照直接插入法排序.同样,用下一个增量ht/2将序列再分为子序列,再按照直接插入法排序.直到增量ht=1时整个文件排好序了.

• 关键:选择合适的增量.

  • 第一次的增量可以选择数组的一半,然后不断减半

  public static void shellSort1(int[] arr) {// 第一次的增量可以选择数组的一半,然后不断减半for (int h = arr.length / 2; h > 0; h /= 2) {for (int i = h; i < arr.length; i++) {for (int j = i; j > h - 1; j -= h) {if (arr[j] < arr[j - h]) {int temp = arr[j];arr[j] = arr[j - h];arr[j - h] = temp;}}}}
  }
  通过克努特(Knuth)序列选择增量h=1h=h*3-1public static void shellSort2(int[] arr) {// 根据克努特序列取得第一个增量int ht = 1;while (ht <= arr.length / 3) {ht = ht * 3 + 1;}//外层增量根据克努特序列递减,直到增量=1for (int h = ht; h > 0; h = (h - 1) / 3) {//中间层控制循环次数for (int i = h; i < arr.length; i++) {//里层比较元素大小,进行排序for (int j = i; j > h - 1; j -= h) {if (arr[j] < arr[j - h]) {int temp = arr[j];arr[j] = arr[j - h];arr[j - h] = temp;}}}}
  }

• 希尔排序算法9-3:可以通过三重循环来实现.

五,快速排序

原理:

分治法:比大小,再分区

1.从数组中去一个数,作为基准数

2.分区:将等于等于基准数的元素,全部放到他的右边,小于他的 数全部放到他的左边.

3.再对左右区分重复第二部,直到各个区间自由一个数.

步骤:

挖坑填数:

1.将基准数挖出,形成第一个坑;

2.由后向前找比他小的数,找到后挖出此数,填到前一个坑中;

3.由前向后找大于等于他的数,找到后挖出此数,填到前一个坑中;

4.重复2,3步骤

public static void quickSort(int[] arr, int start, int end) {// 找出区分左右两区的 索引位置,然后对左右两区进行递归调用if (start < end) {int index = getIndex(arr, start, end);quickSort(arr, start, index - 1);quickSort(arr, index + 1, end);}
}/** 1.将基准数挖出,形成第一个坑;* 2.由后向前找比他小的数,找到后挖出此数,填到前一个坑中;* 3.由前向后找大于等于他的数,找到后挖出此数,填到前一个坑中;* 4.重复2,3步骤*/
private static int getIndex(int[] arr, int start, int end) {int i = start;int j = end;int x = arr[i];while (i < j) {// 由后向前找比他小的数,找到后挖出此数,填到前一个坑中;while (i < j && arr[j] >= x) {j--;}if (i < j) {arr[i] = arr[j];i++;}// 由前向后找大于等于他的数,找到后挖出此数,填到前一个坑中;while (i < j && arr[i] < x) {i++;}if (i < j) {arr[j] = arr[i];j--;}//把基准数填到最后一个坑中arr[i] = x;}return i;
}

六,归并排序

归并排序(Merge sort)就是利用归并思想实现排序的方法.

原理:假设初始序列有N个记录,责可以看成N个有序的子序列,每个子序列的长度为1,然后两两归并,得到N/2个长度为2或1的有序子序列,再两两归并...

如此重复,直到得到一个长度为N的有序序列为止,这种排序方法被称为二路归并排序.

// 拆分
private static void chaiFen(int[] arr, int startIndex, int endIndex) {// 计算中间索引int centerIndex = (startIndex + endIndex) / 2;// 递归调用if (startIndex < endIndex) {chaiFen(arr, startIndex, centerIndex);chaiFen(arr, centerIndex + 1, endIndex);guiBing(arr, startIndex, centerIndex, endIndex);}
}
​
// 归并
public static void guiBing(int[] arr, int startIndex, int centerIndex, int endIndex) {// 定义一个临时数组int[] temp = new int[endIndex - startIndex + 1];// 定义左边数组的起始索引int i = startIndex;// 定义右边数组的起始索引int j = centerIndex + 1;// 定义临时数组的起始索引int index = 0;// 比较左右两个数组的元素大小,往临时数组中放while (i <= centerIndex & j <= endIndex) {if (arr[i] <= arr[j]) {temp[index] = arr[i];i++;} else {temp[index] = arr[j];j++;}index++;}
​// 处理剩余元素while (i <= centerIndex) {temp[index] = arr[i];i++;index++;}
​while (j <= endIndex) {temp[index] = arr[j];j++;index++;}
​// 将临时数组中的元素取到原数组中for (int k = 0; k < temp.length; k++) {arr[k + startIndex] = temp[k];}
}

七,基数排序

基数排序不同于上述各类排序,上述排序都是通过比较和移动记录来实现排序.而基数排序只需要对关键字进行分配与收集这两种操作就可以完成排序

private static void sortArray(int[] arr) {// 定义二维数组,放10个桶int[][] tempArr = new int[10][arr.length];// 定义统计数组int[] counts = new int[10];// 首先的确定轮次,获取数组中的最大值int max = geMax(arr);// 循环轮次int len = String.valueOf(max).length();for (int i = 0, n = 1; i < len; i++, n *= 10) {// 获取每个数组元素每位上的数for (int j = 0; j < arr.length; j++) {int ys = arr[j] / n % 10;tempArr[ys][counts[ys]++] = arr[j];}
​// 原数组的下标int index = 0;// 取出桶中的元素for (int k = 0; k < counts.length; k++) {if (counts[k] != 0) {for (int h = 0; h < counts[k]; h++) {// 从桶里取出元素放回原数组arr[index] = tempArr[k][h];index++;}// 清除上一次统计counts[k] = 0;}}}
}
// 获取数组中的最大值
private static int geMax(int[] arr) {int max = arr[0];for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}return max;
}

八,堆排序

堆排序是利用堆这种数据结构,而设计的一种排序算法,堆排序是一种选择排序.

堆排序的基本思想:

1.将待排序序列构造成一个大的顶堆,此时整个序列的最大值就是堆顶的根节点;

2.将其与末尾元素进行交换,那么末尾元素就是最大值;

3.然后将剩余n个元素重新构造成一个堆,这样会得到n个元素的次小值;

堆的定义：

大顶堆：arr[i]>=arr[2i+1] && arr[i]>=arr[2i+2]

小顶堆：arr[i]>=arr[2i+1] && arr[i]>=arr[2i+2]

import java.util.Arrays;
​
/*** @PackageName:PACKAGE_NAME* @ClassName: ArrayDemo* @Description:* @Author:lfq* @Date:2021/8/2118:54*/
public class ArrayDemo11 {public static void main(String[] args) {// 定义一个数组int[] arr = {1, 0, 6, 7, 2, 3, 4};
​// 调整成大顶堆的方法// 定义开始调整的位置int startIndex = (arr.length - 1) / 2;for (int i = startIndex; i >= 0; i--) {toMaxHeap(arr, arr.length, i);}
​// 经过上面的操作之后,已经将数组变成了一个大顶堆,吧根元素和最后一个元素进行调换for (int i = arr.length - 1; i > 0 ; i--) {// 进行调换int t = arr[0];arr[0] = arr[i];arr[i] = t;
​// 还完之后,在吧剩余元素调成大顶堆toMaxHeap(arr, i, 0);}
​
​System.out.String(arr));}
​/*** 将数组调整成大顶堆** @param arr   要排序的数组* @param size  调整的元素个数* @param index 从哪里开始调整*/private static void toMaxHeap(int[] arr, int size, int index) {// 获取左右子节点的索引int leftNodeIndex = index * 2 + 1;int rightNodeIndex = index * 2 + 2;
​// 查找最大节点所对应的索引int maxIndex = index;if (leftNodeIndex < size && arr[leftNodeIndex] > arr[maxIndex]) {maxIndex = leftNodeIndex;}if (rightNodeIndex < size && arr[rightNodeIndex] > arr[maxIndex]) {maxIndex = rightNodeIndex;}
​// 调换位置if (maxIndex != index) {int t = arr[maxIndex];arr[maxIndex] = arr[index];arr[index] = t;
​// 调整过后.可能影响到下面的子树,不是大顶堆,还需要再次调换toMaxHeap(arr, size, maxIndex);}}
}

​