排序算法

import java.util.Arrays;

/**

• @Author: Xia

• @Date: 2021/2/22 8:48

• @Email：x2358114512@163.com

• /
  public class SortEight{
  public static void main(String[] Args){

    int[] nums = new int[]{1,2,2,2,12,2,14,5,6,7,8,190};
    bubbleSort(nums);
    quickSort(0, nums.length-1, nums);
    insertSort(nums);
    shellSort(nums);
    selectSort(nums);
    heapSort(nums);
    megerSort(0, nums.length-1, nums);
    radixSort(nums);
    System.out.println(Arrays.toString(nums));

  }

  private static void radixSort(int[] nums) {

    int[][] bucket = new int[10][nums.length];  //10个桶，每个桶长度为nums.length
    int[] tem = new  int[10];    //下标对应的桶，元素对应哪个桶装的个数
    int maxNum = max(nums);
    int len = (maxNum+"").length();
    for(int i=0, d=1; i<len; i++,d*=10){
        for(int j=0; j<nums.length; j++){
            int yushu = nums[j]/d%10;
            bucket[yushu][tem[yushu]] = nums[j]; //nums[j]放到桶中【拿一个桶，该桶里有几个元素】
            tem[yushu]++;    //
        }
        int idx = 0;
        for(int k=0; k<tem.length; k++){
            if(tem[k]!=0){
                for(int m = 0; m<tem[k]; m++){
                    nums[idx] = bucket[k][m];
                    idx++;
                }
            }
            tem[k] = 0;  //清空，下次存放到桶中数据
        }
    }

  }

  private static int max(int[] nums) {

    int maxNum = Integer.MIN_VALUE;
    for(int i=0; i<nums.length; i++){
        if(nums[i]>maxNum){
            maxNum = nums[i];
        }
    }
    return maxNum;

  }

  private static void heapSort(int[] nums) {

    int start = (nums.length-1)/2;  //从第一个非叶子结点从下至上调整为大顶堆
    for(int i=start; i>=0; i--){
        toHeap(i, nums.length, nums);
    }
    for(int i=nums.length-1; i>0; i--){
        swap(0, i, nums);
        toHeap(0, i, nums);
    }

  }

  private static void toHeap(int idx, int length, int[] nums) {

    int leftIdx = 2*idx+1; int rightIdx = 2*idx+2;
    int maxIdx = idx;
    if(leftIdx<length && nums[maxIdx]<nums[leftIdx]){
        maxIdx = leftIdx;
    }
    if(rightIdx<length && nums[maxIdx]<nums[rightIdx]){
        maxIdx = rightIdx;
    }
    if(idx!=maxIdx){
        swap(idx, maxIdx, nums);
        toHeap(maxIdx, length, nums);
    }

  }

  private static void megerSort(int start, int end, int[] nums) {

    if(start<end){
        int middle = start+(end-start)/2;
        megerSort(start,middle, nums);
        megerSort(middle+1,end, nums);
        meger(start,middle,end,nums);
    }

  }

  private static void meger(int start, int middle, int end, int[] nums) {

    int[] tem = new int[end-start+1];  int idx = 0;
    int left = start; int right = middle+1;
    while(left<=middle && right<=end){
        if(nums[left]>nums[right]){
            tem[idx] = nums[right];
            right++;
        }else{
            tem[idx] = nums[left];
            left++;
        }
        idx++;
    }
    while(left<=middle){
        tem[idx] = nums[left];
        left++;idx++;
    }
    while(right<=end){
        tem[idx] = nums[right];
        right++;idx++;
    }
    for(int i=0; i<tem.length; i++){
        nums[i+start] = tem[i];
    }

  }

public static void bubbleSort(int[] nums){
    int len = nums.length;
    for(int i=0; i<len-1; i++){
        for(int j=0; j<len-1-i; j++){
            if(nums[j]>nums[j+1]){
                swap(j, j+1, nums);
            }
        }
    }
}

public static void swap(int i, int j, int[] nums){
    int tem = nums[i];
    nums[i] = nums[j];
    nums[j] = tem;
}

public static void quickSort(int start, int end, int[]nums){
    if(start<end){
        int tem = nums[start];
        int l = start; int r = end;
        while(l<r){
            while(l<r && tem<=nums[r]){
                r--;
            }nums[l] = nums[r];
            while(l<r && tem>=nums[l]){
                l++;
            }nums[r] = nums[l];
        }
        nums[l] = tem;
        quickSort(start, l-1, nums);
        quickSort(l+1, end, nums);
    }
}

public static void insertSort(int[] nums){
    int len = nums.length;
    for(int i=1; i<len; i++){
        if(nums[i-1]>nums[i]) {
            int tem = nums[i];
            int j;
            for (j = i - 1; j >= 0 && nums[j] >  tem; j--) {
                nums[j + 1] = nums[j];
            }
            nums[j+1] =  tem;
        }
    }
}

public static void shellSort(int[] nums){
    int len = nums.length;
    for(int d=len/2; d>0; d/=2){
        for(int i=d; i<len; i++){
            for(int j=0; j<len-d; j+=d){
                if(nums[j]>nums[j+d]){
                    swap(j, j+d, nums);
                }
            }
        }
    }
}

public static void selectSort(int[] nums){
    int len = nums.length;
    for(int i=0; i<len; i++){
        int minIdx = i;
        for(int j=i; j<len; j++){
            if(nums[j]<nums[minIdx]){
                minIdx = j;
            }
        }
        if(minIdx!=i){
            swap(i, minIdx, nums);
        }
    }

}

}