2024秋招备战java 复习资料-1

一、数据结构与算法是基础

1.1 数据结构部分

推荐阅读：数据结构最全讲解

数据结构概念：数据结构分类细讲

数据结构java源码：经典数据结构及算法-Java实现-附源代码（可下载）

1.2 经典算法部分

推荐：

十大经典算法：https://www.cnblogs.com/ice-line/p/11753852.html

二、手写代码是能力

2.1.排序算法手写

选择排序（Selection Sort）

代码实现：

import java.util.Arrays;

public class Demo {

//选择排序

/**

*1.从待排序序列中，找到关键字最小的元素；

* 2.如果最小元素不是待排序序列的第一个元素，将其和第二个元素交换；

* 3.从余下的N-1个元素中，找出关建字最小的元素，重复1.2步骤，直到排序排序结束

* 当增量因子微一时，整个序列长度为原来序列的长度；

*/

public static void main(String[] args) {

int[] arr = {25,89,56,88,21,3,56,66,8,663,55};

Selectionchose(arr);

System.out.println("========================");

int[] res = Selectchose1(arr);

System.out.println(Arrays.toString(res));

}

//展示选择的过程

public static void Selectionchose(int[] arr){

if(arr==null||arr.length==0) return;

//开始遍历，寻找最小的元素，打印出来

for(int i=0;i<arr.length-1;i++){

int min = i;

for(int j=i+1;j<arr.length;j++){

if(arr[j]<arr[min]){

min =j;

}

}

if(min!=i){

int temp = arr[min];

arr[min] = arr[i];

arr[i] = temp;

System.out.println(Arrays.toString(arr));

}

}

}

//直接返回最终结果

public static int[] Selectchose1(int[] arr){

if(arr==null||arr.length==0){

System.out.println("序列不合法！");

return null;

}

for(int i =0;i<arr.length-1;i++){

int min = i;

for(int j =i+1;j<arr.length;j++){

if(arr[min]>arr[j]){

min =j;

}

}

if(min!=i){

int res = arr[i];

arr[i] = arr[min];

arr[min] = res;

}

}

return arr;

}

}

2、插入排序（Insertion Sort）

代码实现：

import java.util.Arrays;

public class Deom {

/**

* 插入排序

*/

public static void main(String[] args) {

int[] arr = {25,89,56,88,21,3,56,66,8,663,55};

//insertionSort(arr);

insertionSort1(arr);

}

//序列较少的情况下：

public static void insertionSort(int[] arr){

if(arr==null||arr.length==0) return;

for(int i =1;i<arr.length;i++){

int temp = arr[i]; //取出第二个元素；

for(int j =i;j>=0;j--){

if(j>0&&arr[j-1]>temp){//j-1为当前元素的前一个元素的下标，如果前一个数大于当前的元素，那么两个数据进行交换

arr[j] = arr[j-1];

System.out.println("inserting"+Arrays.toString(arr));

}else{

arr[j]=temp;//如果大于或等于，那么保存当前数，并且进入下一次插入；

System.out.println("Sorting"+Arrays.toString(arr));

break;

}

}

}

}

//数据量比较多的时候

public static void insertionSort1(int[] arr){

if(arr.length==0||arr==null) return;

for(int i =0;i<arr.length-1;i++){

for(int j = i+1;j>0;j--){

if(arr[j-1]<arr[j]){

break; //如果前一个元素小于当前元素，不做处理

}

int temp = arr[j]; //如果前一个元素大于或等于当前元素时，交换数值，然后进入循环。

arr[j] = arr[j-1];

arr[j-1] = temp;

}

}

System.out.println(Arrays.toString(arr));

}

}

3、冒泡排序（Bubble Sort）

代码实现：

import java.util.Arrays;

public class Deom {

public static void main(String[] args) {

int[] arr = {25,89,56,88,21,3,56,66,8,663,55};

BubbleSort(arr);

}

public static void BubbleSort(int[] arr){

if(arr.length==0||arr==null) return;

for(int i =0;i<arr.length;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;

}

}

}

System.out.println(Arrays.toString(arr));

}

}

4、快速排序（Quick Sort）

代码实现：（递归方法）

import java.util.Arrays;

/**

* 用伪代码描述如下：

*

* ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。

* ②．j--，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

* ③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

* ④．再重复执行②，③二步，直到i==j，将基准数填入a[i]中

* ————————————————

*

*/

public class Deom {

public static void main(String[] args) {

int[] arr = {25,89,56,88,21,3,56,66,8,663,55};

QuickSort(arr,0,arr.length-1);//以第一个数为基准

}

public static void QuickSort(int[] arr ,int low,int high){

if(arr==null||arr.length==0) return;

if(low>=high) return;

int left = low;

int right = high;

int temp = arr[left]; //确定基准值；

while (left<right){

while (left<right&&arr[right]>=temp){ //从后往前，找到小于或等于基准的数进行交换

right--;

}

arr[left] = arr[right];

while (left<right&&arr[left]<=temp){ //从前往后走，找到大于或等于基准的数进行交换

left++;

}

arr[right] = arr[left];

}

arr[left]=temp; //将基准值填到坑3中

//开始递归；

QuickSort(arr,low,left-1);

QuickSort(arr,left+1,high);

System.out.println(Arrays.toString(arr));

}

}

上面是递归版的快速排序：通过把基准temp插入到合适的位置来实现分治，并递归地对分治后的两个划分继续快排。那么非递归版的快排如何实现呢？

因为递归的本质是栈，所以我们非递归实现的过程中，可以借助栈来保存中间变量就可以实现非递归了。在这里中间变量也就是通过QuickSort1函数划分

区间之后分成左右两部分的首尾指针， 只需要保存这两部分的首尾指针即可。

import java.util.Arrays;

import java.util.Stack;

/**

* 用伪代码描述如下：

*

* ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。

* ②．j--，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

* ③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

* ④．再重复执行②，③二步，直到i==j，将基准数填入a[i]中

* ————————————————

*

*/

public class Deom {

public static void main(String[] args) {

int[] arr = {25,89,56,88,21,3,56,66,8,663,55};

// QuickSort(arr,0,arr.length-1);//以第一个数为基准、

quickSortByStack(arr);

}

public static void QuickSort(int[] arr ,int low,int high){

if(arr==null||arr.length==0) return;

if(low>=high) return;

int left = low;

int right = high;

int temp = arr[left]; //确定基准值；

while (left<right){

while (left<right&&arr[right]>=temp){ //从后往前，找到小于或等于基准的数进行交换

right--;

}

arr[left] = arr[right];

while (left<right&&arr[left]<=temp){ //从前往后走，找到大于或等于基准的数进行交换

left++;

}

arr[right] = arr[left];

}

arr[left]=temp; //将基准值填到坑3中

//开始递归；

QuickSort(arr,low,left-1);

QuickSort(arr,left+1,high);

System.out.println(Arrays.toString(arr));

}

/**

* 快速排序（非递归）

*

* ①. 从数列中挑出一个元素，称为"基准"（pivot）。

* ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

* ③. 把分区之后两个区间的边界（low和high）压入栈保存，并循环①、②步骤

* @param arr 待排序数组

*/

public static void quickSortByStack(int[] arr){

if(arr.length <= 0) return;

Stack<Integer> stack = new Stack<Integer>();

//初始状态的左右指针入栈

stack.push(0);

stack.push(arr.length - 1);

while(!stack.isEmpty()){

int high = stack.pop(); //出栈进行划分

int low = stack.pop();

int pivotIdx = QuickSort1(arr, low, high);

//保存中间变量

if(pivotIdx > low) {

stack.push(low);

stack.push(pivotIdx - 1);

}

if(pivotIdx < high && pivotIdx >= 0){

stack.push(pivotIdx + 1);

stack.push(high);

}

}

}

private static int QuickSort1(int[] arr, int low, int high){

if(arr.length <= 0) return -1;

if(low >= high) return -1;

int l = low;

int r = high;

int pivot = arr[l]; //挖坑1：保存基准的值

while(l < r){

while(l < r && arr[r] >= pivot){ //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中

r--;

}

arr[l] = arr[r];

while(l < r && arr[l] <= pivot){ //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中

l++;

}

arr[r] = arr[l];

}

arr[l] = pivot; //基准值填补到坑3中，准备分治递归快排

System.out.println(Arrays.toString(arr));

return l;

}

}

5.希尔排序（Shell Sort）

import java.util.Arrays;

/**

* 希尔排序

*

* 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）

* 2. 按增量序列个数k，对序列进行k 趟排序；

* 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。

* 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

* @param arr 待排序数组

*/

public class Deom {

public static void main(String[] args) {

int[] arr = {2,1,6,9,5,4,20,19,11};

shellSort(arr);

}

public static void shellSort(int[] arr){

if(arr==null||arr.length==0){

return;

}

int groud = arr.length/2;

for(;groud>0;groud/=2){

for(int i = 0;i+groud<arr.length;i++){

for(int j = 0;j+groud<arr.length;j+=groud){

if(arr[j]>=arr[j+groud]){

int temp = arr[j];

arr[j] = arr[j+groud];

arr[j+groud] = temp;

}

}

}

}

System.out.println(Arrays.toString(arr));

}

}

6、堆排序（Heap Sort）

代码实现：

import java.util.Arrays;

/**

* 堆排序

*

* 1. 先将初始序列K[1..n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.

* 2. 再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1..n−1]和有序区K[n], 且满足K[1..n−1].keys⩽K[n].key

* 3. 交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1..n−1]调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止.

* @param arr 待排序数组

*/

public class Demo {

public static void main(String[] args) {

int[] arr = {1,5,4,8,20,15,23,65,45};

heapSort(arr);

}

public static void heapSort(int[] arr){

for(int i = arr.length; i > 0; i--){

max_heapify(arr, i);

int temp = arr[0]; //堆顶元素(第一个元素)与Kn交换

arr[0] = arr[i-1];

arr[i-1] = temp;

}

System.out.println(Arrays.toString(arr));

}

private static void max_heapify(int[] arr, int limit){

if(arr.length <= 0 || arr.length < limit) return;

int parentIdx = limit / 2;

for(; parentIdx >= 0; parentIdx--){

if(parentIdx * 2 >= limit){

continue;

}

int left = parentIdx * 2; //左子节点位置

int right = (left + 1) >= limit ? left : (left + 1); //右子节点位置，如果没有右节点，默认为左节点位置

int maxChildId = arr[left] >= arr[right] ? left : right;

if(arr[maxChildId] > arr[parentIdx]){ //交换父节点与左右子节点中的最大值

int temp = arr[parentIdx];

arr[parentIdx] = arr[maxChildId];

arr[maxChildId] = temp;

}

}

//System.out.println("Max_Heapify: " + Arrays.toString(arr));

}

}

以上,

①. 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);

②. 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);

③. 堆排序的过程由n次第②步完成, 时间复杂度为O(nlgn).

7、归并排序（Merging Sort）

代码实现：

归并排序其实要做两件事：

分解：将序列每次折半拆分

合并：将划分后的序列段两两排序合并

因此，归并排序实际上就是两个操作，拆分+合并

如何合并？

L[first…mid]为第一段，L[mid+1…last]为第二段，并且两端已经有序，现在我们要将两端合成达到L[first…last]并且也有序。

首先依次从第一段与第二段中取出元素比较，将较小的元素赋值给temp[]

重复执行上一步，当某一段赋值结束，则将另一段剩下的元素赋值给temp[]

此时将temp[]中的元素复制给L[]，则得到的L[first…last]有序

如何分解？

在这里，我们采用递归的方法，首先将待排序列分成A,B两组；然后重复对A、B序列

分组；直到分组后组内只有一个元素，此时我们认为组内所有元素有序，则分组结束。

import java.util.Arrays;

public class Demo {

public static void main(String[] args) {

int[] arr = {1,5,3,8,4,6,15,3,24};

System.out.println("归并排序前"+Arrays.toString(arr));

System.out.println("归并排序后"+Arrays.toString(mergeSort(arr)));

}

//将一个序列，拆分成两个序列

public static int[] mergeSort(int[] arr){

if(arr.length<=1) return arr;

int num = arr.length>>1;

int[] leftarr = Arrays.copyOfRange(arr,0,num);

int[] rightarr= Arrays.copyOfRange(arr,num,arr.length);

return mergeTwoArray(mergeSort(leftarr),mergeSort(rightarr));

}

//将两个排好序列的短序列合并为一个序列

public static int[] mergeTwoArray(int[] arr1,int[] arr2){

int i =0;int j =0;int k=0;

int[] result = new int[arr1.length+arr2.length];

while (i< arr1.length&&j<arr2.length){

if(arr1[i]<=arr2[j]){

result[k++]= arr1[i++];

}else {

result[k++]=arr2[j++];

}

}

while (i<arr1.length){

result[k++] = arr1[i++];

}

while (j<arr2.length){

result[k++] = arr2[j++];

}

return result;

}

}

由上, 长度为n的数组, 最终会调用mergeSort函数2n-1次。通过自上而下的递归实现的归并排序, 将存在堆栈溢出的风险。

原文链接：https://blog.csdn.net/ILOVEMYDEAR/article/details/117399152