有各种排序的方法

插入排序 折半插入 冒泡 快速 堆 基数 希尔排序 归并 选择

package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Sort {
    // 插入排序
    void insert(int[] nums){
        for(int i=1;i<nums.length;i++){
            int value = nums[i];
            for(int j=0;j<i;j++){
                if(value<nums[j]){
                    for(int k=i;k>j;k--){
                        nums[k] = nums[k-1];
                    }
                    nums[j] = value;
                    break;
                }
            }
        }
    }
    // 折半查找排序
    void binSearch(int[] nums){
        for(int i=1;i<nums.length;i++){
            int value = nums[i];
            int start = 0,end = i-1;
            while (start<=end){
                int mid = (start+end)/2;
                if(nums[mid]>value){
                    end = mid -1;
                }else {
                    start = mid + 1;
                }
            }
            for(int k=i-1;k>end;k--){
                nums[k+1] = nums[k];
            }
            nums[end+1] = value;
        }
    }
    // 希尔选择排序
    void shellSelectSort(int[] nums){
        for(int skip=nums.length/2;skip>0;skip = skip/2){
            for (int i = 0;i<nums.length;i++){
                int minI = 0;
                int minValue = Integer.MAX_VALUE;
                for(int j = i;j<nums.length;j+=skip){
                    if(minValue>nums[j]){
                        minValue = nums[j];
                        minI = j;
                    }
                }
                nums[minI] = nums[i];
                nums[i] = minValue;
            }
        }
    }
    // 希尔冒泡排序
    void shellSort(int[] nums){
        for(int skip=nums.length/2;skip>0;skip/=2){
            for(int i=skip;i<nums.length;i++){
                for(int j=i;j>=skip;j-=skip){
                    if(nums[j]<nums[j-skip]){
                        int temp = nums[j];
                        nums[j] = nums[j-skip];
                        nums[j-skip]=temp;
                    }
                }
            }
        }
    }
    // 选择排序
    void selectSort(int[] nums){
        for(int i=0;i<nums.length;i++){
            int min = 0;
            int minValue = Integer.MAX_VALUE;
            for(int j=i;j<nums.length;j++){
                if(minValue>nums[j]){
                    minValue = nums[j];
                    min = j;
                }
            }
            nums[min] = nums[i];
            nums[i] = minValue;
        }
    }
    // 冒泡排序
    void bubbleSort(int[] nums){
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<nums.length-i-1;j++){
                if(nums[j+1]<nums[j]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }
    // QuickSort
    void quickSort(int[] nums,int start,int end){
        if(start>=end){
            return;
        }
        int flagValue=nums[start];
        int flagIndex = start;
        for(int i=start+1;i<end;i++){
            if(nums[i]<flagValue){
                nums[flagIndex] = nums[i];
                flagIndex++;
                nums[i] = nums[flagIndex];
            }
        }
        nums[flagIndex] = flagValue;
        quickSort(nums,start,flagIndex);
        quickSort(nums,flagIndex+1,end);
    }
    public void swap(int[] nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    public void adjustBiggerHeap(int[] nums,int i,int size){
        int left = 2*i+1;
        int right = 2*i+2;
        if(left>=size){
            return;
        }
        if(nums[left]>nums[i]){ // 顶堆调整 那么他之后的顶堆也需要调整
            swap(nums,i,left);
            adjustBiggerHeap(nums,left,size);
        }
        if(right<size){
            if(nums[right]>nums[i]){
                swap(nums,i,right);
                adjustBiggerHeap(nums,right,size);
            }
        }
    }
    // heapSort 堆排序
    public void heapSort(int[] nums){
        // 把数组看成二叉树
       for (int i = nums.length/2;i>=0;i--){
           adjustBiggerHeap(nums,i,nums.length);
       }
       // 排序
        for(int i=nums.length-1;i>0;i--){
            swap(nums,i,0);
            adjustBiggerHeap(nums,0,i);
        }
    }
    public void  merge(int[] nums,int j,int leftStart,int leftEnd,int rightStart,int rightEnd){
        int[] book = new int[nums.length];
        int k = 0;
        while (leftStart<leftEnd&&rightStart<rightEnd){
            if(nums[leftStart]<nums[rightStart]){
                book[k] = nums[leftStart];
                leftStart++;
            }else {
                book[k] = nums[rightStart];
                rightStart++;
            }
            k++;
        }
        while (leftStart<leftEnd){
            book[k] = nums[leftStart];
            leftStart++;
            k++;
        }
        while (rightStart<rightEnd){
            book[k] = nums[rightStart];
            rightStart++;
            k++;
        }
        for(int n = 0;n<k;n++){
            nums[j+n] = book[n];
        }
    }
    public void mergeSort(int[] nums){
        int leftStart,leftEnd,rightEnd,rightStart;
        for(int i=1;i<nums.length;i*=2){
            for(int j=0;j<nums.length;j+=2*i){
                leftStart = j;
                leftEnd = rightStart = Math.min(nums.length,j+i);
                rightEnd = Math.min(nums.length,j+i+i);
                merge(nums,j,leftStart,leftEnd,rightStart,rightEnd);
            }
        }
    }

    // 基数排序
    public void baseSort(int[] nums){
        List<List<Integer>> bucket = new ArrayList<>();
        for(int i=0;i<10;i++){
            bucket.add(new LinkedList<>());
        }
        int countNum = 1;
        boolean flag = true;
        while (flag){
            int count = 1;
            for(int i=0;i<countNum;i++){
                count *= 10;
            }
            countNum++;
            for (int num : nums) {
                bucket.get(num % count / (count/10)).add(num);
            }
            int index = 0;
            for(List<Integer> list:bucket){
                for(int temp:list){
                    nums[index] = temp;
                    index++;
                }
                if(list.size()==nums.length){
                    return;
                }
                list.clear();
            }
        }
    }

}
class TestSort{
    public static void main(String[] args) {
        int[] nums = {8,12,4,54,9,4,3,6,1,2,1};
        System.out.println(Arrays.toString(nums));

        Sort sort = new Sort();
        sort.baseSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}