java实现五大排序算法

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