冒泡排序、插入排序、归并排序、快速排序代码实现

import java.util.Arrays;

/*
自己整理的几种常见排序算法
1.冒泡排序
2.插入排序
3.归并排序
4.快速排序
 */
public class Main {
    public static void main(String[] args) {
        long[] nums={5,4,8,9,3,2,1,15,31,7,33,56}; //无序的数组
        System.out.println("原数组："+Arrays.toString(nums));
        //冒泡排序并打印
        bubbleSort(nums);

        //插入排序并打印
        insertSort(nums);

        //归并排序并打印
        mergeSort(nums);
        System.out.println("归并排序后的数组："+Arrays.toString(nums));

        //快速排序并打印
        quickSort(nums,0,nums.length-1);
        System.out.println("快速排序后的数组："+Arrays.toString(nums));

    }

    /*
    1.冒泡排序(从小到大):
    原理：n个元素数组，外循环遍历n-1次，每次外循环都把一个最大的数排到后面。
         内循环遍历n-1-i次，当第j个元素比第j + 1大时，交换元素。
         保证第i次外循环遍历后，第 n - i的元素是 0 ~ n - i中最大的。
    上限：O（n ^ 2） 交换次数：O(n ^ 2)
     */
    public static  void bubbleSort(long[] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
        System.out.println("冒泡排序后的数组："+Arrays.toString(arr));
    }

    /*
    2.插入排序(从小到大):
    原理：把第i个元素与前i - 1（有序）个元素进行比较，把i插到正确位置，保证每次外循环遍历后，前i个元素是有序的。
    上限：O(n ^ 2) ,交换次数： O(n ^ 2)
     */
    public static void insertSort(long[] arr){
        for(int i =1;i<arr.length;i++){
            long temp = arr[i];
            int j;
            for(j=i-1;j>=0&&arr[j]>temp;j--){
                arr[j+1]=arr[j];
            }
            arr[j+1]=temp;
        }
        System.out.println("插入排序后的数组："+Arrays.toString(arr));
    }

    /*

    3.归并排序（从小到大）
    原理：先使用2分法把数组分为一个个数字，然后每两个进行比较。排序结构二叉树类似。从下往上进行排序
            分解：二分法
            递归：使用递归一层层分解数组
            合并：从下往上合并数组。左右两个数组排序。可参考两个栈内存，比较栈顶元素，取出小的那个进行排序。
    上限：O(n log n)
     */
    public static void mergeSort(long[] arr){

        //分解
        int length = arr.length;
        if(length ==1)
            return;
        int middle = length/2;
        long[] left = new long[middle];
        long[] right = new long[length-middle];
        for(int i =0,leftIndex=0,rightIndex=0;i<length;i++){
            if(i<middle){
                left[leftIndex++]=arr[i];
            }else {
                right[rightIndex++]=arr[i];
            }
        }
        //递归
        mergeSort(left);
        mergeSort(right);
        //合并
        for(int i = 0,j=0,k=0;i<left.length ||j<right.length;){
            if(i==left.length){
                arr[k++]=right[j++];
                continue;
            }
            if(j==right.length){
                arr[k++]=left[i++];
                continue;
            }
            if(left[i]<=right[j]){
                arr[k++]=left[i++];
                continue;
            }
            if(left[i]>right[j]){
                arr[k++]=right[j++];
            }
        }

    }

    /*
    4.快速排序（从小到大）
    原理：对于一个数组，取出一个数（这里默认是low）作为基准数,然后将后面的数与之对比，比基准数小的放左边，比基准数
         大的放右边，然后当i=j时，第i个与第low个数据对换，最终实现，第i个元素的左边都比它小，右边都比它大；
         然后将左边和右边当成一个数组，再次进行递归；
     */
    public static void quickSort(long[] arr,int low,int high){
        if(low>high){
            return;
        }
        int i,j;
        long base = arr[low];//基准位
        i = low;
        j = high;
        while(i<j){
            while(arr[j]>=base&&i<j){
                j--;
            }
            while(arr[i]<=base&&i<j){
                i++;
            }
            if(i<j){
                swap(arr,i,j);
            }
        }

        arr[low]=arr[i];
        arr[i]=base;

        quickSort(arr,low,j-1);
        quickSort(arr,j+1,high);

    }

    //交换位置swap
    public static void swap(long[] arr,int p,int q){
        long temp = arr[p];
        arr[p]=arr[q];
        arr[q]=temp;
    }
}