1：冒泡排序BubbleSort
我觉得这个没啥好说的，代码如下
package algorithm;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {5,3,8,6,4};
BubbleSort.sort(arr);
for(int a:arr) {
System.out.print(a+" ");
}
}
public static void sort(int[] arr) {
for (int i =0;i<arr.length;i++) {
for (int j = arr.length-1;j>i;j--) {
if (arr[j]<arr[j-1]) {
swap(arr,j,j-1);
}
}
}
}
public static void swap(int[] arr,int i ,int j) {
int temp = arr[i];
arr[i]= arr[j];
arr[j] = temp;
}
}
2:插入排序
这个有一点点说的，之前写python插入排序的时候可能没注意到这个地方；第二个循环在循环的时候：如果前面的数比这个数大，就把它往后放，直到找到第一个比他小的数（这时候也就找到了这个位置）代码是while(j>0&&target<arr(j-1))
剩下的附上代码
public class InsertSort {
public static void main(String[]args) {
int[] arr= {5,3,9,6,4,0};
InsertSort.sort(arr);
for(int a:arr) {
System.out.println(a+" ");
}
}
public static void sort(int[] arr) {
for (int i =1;i<arr.length;i++) {
int j =i;
int target = arr[i];
while(j>0&&target<arr[j-1]) {
arr[j] = arr[j-1];
j--;
}
arr[j] = target;
}
}
public static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
3:选择排序，我觉得还是没啥好说的
package algorithm;
//插入排序的思想就是找到最小或者最大的值，依次从前往后放在该在的位置上；要注意的地方是，找最小（大）值时，要比较的是arr[target]而不是arr[i]
public class SelectSort {
public static void main(String[] args) {
int[] arr = {5,3,8,6,4};
SelectSort.sort(arr);
for(int a:arr) {
System.out.println(a);
}
}
public static void sort(int[] arr) {
for (int i = 0;i<arr.length;i++) {
int target = i;
for (int j=i;j<arr.length;j++) {
if (arr[j] <arr[target]) {
target = j;
}
}
swap(arr,i,target);
}
}
public static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
4:快速排序，大概要注意的点在python实现的时候我都写过了，代码如下
package algorithm;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5,3,8,6,4,7};
QuickSort.sort(arr, 0, 5);
for(int a:arr) {
System.out.println(a+" ");
}
}
public static int partition(int[] arr,int i,int j) {
int TargetIndex = i;
int TargetNum = arr[i];
while(i<j) {
while(i<j && arr[j] >= TargetNum) {
j--;
}
while(i<j && arr[i] <= TargetNum) {
i++;
}
swap(arr,i,j);
}
swap(arr,i,TargetIndex);
return i;
}
public static void sort(int[] arr,int i,int j) {
if (i >=j) {
return ;
}
int target = partition(arr,i,j);
sort(arr, i, target-1);
sort(arr,target+1,j);
}
public static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
5:归并排序
这个大概是我今天遇见最大的坑
之前使用python的切片，直接返回了两个子数组，所以打算java也这么做
然后查了arrays的api发现有个方法是 从copyOfRange（int[] arr,int start,int end）
但是要获取到每次传入这个数组的第一个位置，（也就是传入数组在原数组的位置）可能有机会实现，但是我感觉太复杂了，而且不允许空开这个参数，所以换了用下标的这个做法
然后第二个坑就是，merge并不返回一个新数组，而是把原来的数组排序，也就是说两个方法的返回值都是void，通过改变引用类型参数来达到数组排序的目的
第三个坑：这个很智障的问题，出现在原地归并的实现中
归并是通过两两有序的方式来实现的，所以最后合并的两个数组是分别有序的。
剩下的要注意的点就是看代码拉
package algorithm;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {5,3,8,6,4};
MergeSort.sort(arr, 0, 4);
for(int a:arr) {
System.out.println(a);
}
}
public static void sort(int[] arr,int i,int j) {
if (i >=j) {
return;
}
int mid = (i + j)/2;
sort(arr,i,mid);
sort(arr,mid+1,j);
merge(arr,i,mid,j);
}
public static void merge(int[] arr ,int i ,int mid,int j) {
int [] temp = new int[j-i+1];
int left = i;
int right = mid+1;
int k = 0;
while(left <mid+1 && right <=j) {
if(arr[left]<arr[right]) {
temp[k++] = arr[left++];
}else {
temp[k++] = arr[right++];
}
}
while(left<mid+1) {
temp[k++] = arr[left++];
}
while (right<=j) {
temp[k++] = arr[right++];
}
for(int p = 0;p<temp.length;p++) {
arr[i+p] = temp[p];
}
}
}
原地归并还没实现，先把对原地归并的再次理解放上来（给你活动下颈椎，不用谢我）
7d13f93f5fa8177d8e303a6a80c96102.JPEG
大致今天的上班摸鱼就摸了这些，最近发现自己效率好低，写了五个算法，写了一天，还是建立在就把python改一下java的前提下，看东西也效率比较低。努力改正。
image.png
