[数据结构与算法]java实现十大排序算法---优化版

十大排序算法优化后-java实现=—带注释

package com.test.autimatic;

import java.util.Arrays;

/**
 * @author 25338
 * @version 1.0
 * @date 2021/11/22 19:09
 * @description
 */
public class Sort {
    public static void main(String[] args) {
        int[] arr = {21,3,4,2,1,22,21,26,7,8,6,7,51,5,23,33,35,36,87,88,0,4,5,6,6,5,5,7,7,7,980,1,9,19,0,88,66};
        System.out.println(Arrays.toString(arr));
        choiceSort(arr);
        System.out.println(Arrays.toString(arr));
        //插入
        int[] arr1 = {21,3,4,2,1,22,21,26,7,8,6,7,51,5,23,33,35,36,87,88,0,4,5,6,6,5,5,7,7,7,980,1,9,19,0,88,66};
        System.out.println(Arrays.toString(arr1));
        insertSort(arr1);
        System.out.println(Arrays.toString(arr1));
        //希尔
        int[] arr2 = {21,3,4,2,1,22,21,26,7,8,6,7,51,5,23,33,35,36,87,88,0,4,5,6,6,5,5,7,7,7,980,1,9,19,0,88,66};
        System.out.println(Arrays.toString(arr2));
        xiErSort(arr2);
        System.out.println(Arrays.toString(arr2));
        //快速
        int[] arr3 = {21,3,4,2,1,22,21,26,7,8,6,7,51,5,23,33,35,36,87,88,0,4,5,6,6,5,5,7,7,7,980,1,9,19,0,88,66};
        System.out.println(Arrays.toString(arr3));
        quickSort(arr3,0,arr3.length-1);
        System.out.println(Arrays.toString(arr3));
        //归并
        int[] arr4 = {21,3,4,2,1,22,21,26,7,8,6,7,51,5,23,33,35,36,87,88,0,4,5,6,6,5,5,7,7,7,980,1,9,19,0,88,66};
        System.out.println(Arrays.toString(arr4));
        mergeSort(arr4,0,arr4.length-1,new int[arr4.length]);
        System.out.println(Arrays.toString(arr4));
        //堆排序
        int[] arr5 = {21,3,4,2,1,22,21,26,7,8,6,7,51,5,23,33,35,36,87,88,0,4,5,6,6,5,5,7,7,7,980,1,9,19,0,88,66};
        System.out.println(Arrays.toString(arr5));
        heapSort(arr5);
        System.out.println(Arrays.toString(arr5));

    }

    /**
     * 選擇排序-找到数组中最小的数字
     * @param arr
     */
    public static void choiceSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int t = i;
            //从签到后找到最小的数
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j]<arr[t]){
                    t = j;
                }
            }
            if(i != t){swap(arr,i,t);}//如果不想等则交换
        }
    }

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //当不比前一个数小的时候停止
            for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
                swap(arr,j,j-1);//否则交换两个数
            }
        }
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void xiErSort(int[] arr){
        //外层遍历负责分组排序
        for (int i = arr.length/2; i > 0 ; i/=2) {
            //第二层循环将数据按层排好序
            for (int j = i; j < arr.length; j++) {
                //第三层将数据比较按照i进行阶层排序
                for (int k = j; k >= i && arr[k] < arr[k-i]; k-=i) {
                    swap(arr,k,k-i);
                }
            }
        }
    }

    /**
     * 三指针快速排序
     * @param arr
     * @param i
     * @param j
     */
    public static void quickSort(int[] arr,int i,int j){
        //如果开始大于等于结束则停止
        if(i >= j){return;}
        //定义一个比较的目标值--i为标准值，start为左侧开始节点，end为右侧开始节点,mid为标准值
        int t = arr[i];int start = i + 1;int mid = i;int end = j;
        while (start<=end){//如果左侧值小于右侧继续
            if(arr[start] < t){//如果左侧值小于标准值，则交换，并且移动两个指针，标准值和左侧值指针
                swap(arr,start++,mid++);
            }else if(arr[start] > t){//大于，则将此值交给右侧，并且移动右侧指针
                swap(arr, start, end--);
            }else{//如果等于则移动左侧值
                start++;
            }
        }
        quickSort(arr, i, mid-1);//递归左侧部分
        quickSort(arr, end+1, j);//递归右侧部分
    }

    /**
     * 归并排序
     * @param arr
     * @param start
     * @param end
     * @param temp
     */
    public static void mergeSort(int[] arr,int start,int end,int[] temp){
        if(start >= end){ return; }//结束状态--开始值大于等于结束值
        //归并排序--定义起始终止值
        int mid = start + (end - start)/2;
        //递归到最小值不能再分
        mergeSort(arr,start,mid,temp);
        mergeSort(arr,mid+1,end,temp);
        //拷贝start - end段数组数据
        int k = start;int i = start;int j = mid+1;
        System.arraycopy(arr,i,temp,i,end-start+1);
        while (k <= end){
            if(i > mid){//如果左侧数组达到最大值，则将右侧值不断赋值给arr
                arr[k++] = temp[j++];
            }else if(j > end){//如果右侧数组达到最小值，则将左侧值不断赋值给arr
                arr[k++] = temp[i++];
            }else if(temp[i] > temp[j]){//如果左侧数据比右测数据大则将有测数据赋值
                arr[k++] = temp[j++];
            }else{//如果右侧数据比左测数据大则将有测数据赋值
                arr[k++] = temp[i++];
            }
        }
    }

    /**
     * 堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        //构建最大堆
        for (int i = (arr.length/2)-1; i >= 0; i--) {
            sink(arr,i,arr.length);
        }
        //交换并不断下沉
        int n = arr.length - 1;
        while (n >= 0){
            //交换最大值
            swap(arr,0,n--);
            //下沉
            sink(arr,0,n+1);
        }
    }

    /**
     * 下沉操作
     * @param arr
     * @param n
     */
    private static void sink(int[] arr,int n,int len){
        while ((n*2+1)<len){
            int t = n * 2 + 1;//赋值子节点
            if(t+1 < len && arr[t+1] > arr[t]){t++;}//如果有右节点并且右侧节点比左侧节点大则将t赋值右节点下标
            if(arr[n] >= arr[t]){break;}//如果父节点比子节点大直接停止
            swap(arr,n,t);//交换
            n = t;//将子节点赋值为下一次下沉的指针
        }
    }


    /**
     * 数据交换
     * @param arr
     * @param a
     * @param b
     */
    private static void swap(int[] arr,int a,int b){
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}