数组
数组的使用：数组名[下标] -> 数组元素
四要素：数组名 下标 类型 数组元素
数组的类型 和 数组元素的类型一致
当多个元素类型相同步时，考虑用数组
数组的定义：三种类型
int [] student = new int[3]
int [] student = new int[]{97,98,99}
int [] student = {97,98,99}
数组的长度
数组名.length
数组下标从0开始 到length-1
数组最后一个是数组[length-1]
多维数组
二维数组
二维数组就是数组的数组。定义一个二维数组如下：
// 二维数组
public class Main {
public static void main(String[] args) {
int[][] ns = {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 }
};
System.out.println(ns.length); // 3
}
}访问二维数组的某个元素需要使用array[row][col]，例如：
System.out.println(ns[1][2]);
二维数组的每个数组元素的长度并不要求相同，例如，可以这么定义ns数组：
int[][] ns = {
{ 1, 2, 3, 4 },
{ 5, 6 },
{ 7, 8, 9 }
};要打印一个二维数组，可以使用两层嵌套的for循环：
for (int[] arr : ns) {
for (int n : arr) {
System.out.print(n);
System.out.print(', ');
}
System.out.println();
}
或者使用Java标准库的Arrays.deepToString()：
// 二维数组
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[][] ns = {
{ 1, 2, 3, 4 },
{ 5, 6 },
{ 7, 8, 9 }
};
System.out.println(Arrays.deepToString(ns));
}
}三维数组
三维数组就是二维数组的数组。可以这么定义一个三维数组：
int[][][] ns = {
{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
},
{
{10, 11},
{12, 13}
},
{
{14, 15, 16},
{17, 18}
}
};理论上，我们可以定义任意的N维数组。但在实际应用中，除了二维数组在某些时候还能用得上，更高维度的数组很少使用。
排序算法
冒泡排序
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("排序后的数组：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
二分排序
public class BinarySort {
public static void binarySort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
for (int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = key;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
binarySort(arr);
System.out.println("二分排序后的数组：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
## 插入排序
```java
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
insertionSort(arr);
System.out.println("插入排序后的数组：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
选择排序
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
selectionSort(arr);
System.out.println("选择排序后的数组：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
归并排序：
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
mergeSort(arr, 0, arr.length - 1);
System.out.println("归并排序后的数组：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}快速排序：
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr, 0, arr.length - 1);
System.out.println("快速排序后的数组：");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
冒泡排序：适用于小型数据集，实现简单，但效率较低，不适合大规模数据排序。
二分排序：适用于大型数据集，效率较高，但需要数据是有序的。
插入排序：适用于小型数据集或基本有序的数据集，实现简单，但对于大规模数据排序效率较低。
选择排序：适用于小型数据集，实现简单，但效率较低，不适合大规模数据排序。
Comments