八大排序

八大排序

import java.util.ArrayList;
import java.util.Arrays;

/**
 * author: wang
 * date: 2018/4/10
 * time: 20:21
 */
public class Sort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 7, 2, 4, 9, 6, 10, 8};
        //int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; //给优化的选择排序和优化的冒泡排序做测试
        //int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; //给堆排序做测试
        System.out.println("排序前: " + Arrays.toString(arr));
        //insertSort(arr);
        //shellSort(arr);
        //selectSort(arr);
        //selectSortOpti(arr);
        //heapSort(arr);
        //bubbleSort(arr);
        //quickSort(arr, 0, 9);
        //mergeSort(arr, 0, 9);
        radixSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    /**
     * 插入排序
     * 时间复杂度：平均O(n^2),最好O(n),最坏O(n^2)
     * 辅助存储：O(1)
     * 稳定性：稳定
     */
    private static void insertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            for(int j = i; j > 0; j--){
                if(arr[j] < arr[j-1]){
                    swap(arr, j, j-1);
                }else{
                    break;
                }
            }
        }
    }
    /**
     * 希尔排序
     * 时间复杂度：平均O(n^1.3),最好O(n),最坏O(n^2)
     * 辅助存储：O(1)
     * 稳定性：不稳定
     */
    private static void shellSort(int[] arr){
        int interval = arr.length/2;
        while(interval >= 1){
            for(int i = interval; i < arr.length; i++){
                for(int j = i; j > interval-1; j = j-interval){
                    if(arr[j] < arr[j-interval]){
                        swap(arr, j, j-interval);
                    }else{
                        break;
                    }
                }
            }
            interval /= 2;
        }
    }
    /**
     * 未优化的选择排序
     * 时间复杂度：平均O(n^2),最好O(n^2),最坏O(n^2)
     * 辅助存储：O(1)
     * 稳定性：不稳定
     */
    private static void selectSort(int[] arr) {
        for(int i = 0; i < arr.length-1; i++){
            int min = i;
            for(int j = i+1; j < arr.length; j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            swap(arr, i, min);
        }
    }
    /**
     * 优化的选择排序
     * 时间复杂度：平均O(n^2),最好O(n),最坏O(n^2)
     * 辅助存储：O(1)
     * 稳定性：不稳定
     */
    private static void selectSortOpti(int[] arr){
        boolean sorted = false;
        for(int i = 0; (!sorted)&&i<arr.length-1; i++){
            sorted = true;
            int max = 0;
            for(int j = 1; j < arr.length-i; j++){
                if(arr[j] > arr[max]){
                    max = j;
                }else{
                    sorted = false;
                }
            }
            if(!sorted){
                swap(arr, max, arr.length-1-i);
            }
        }
    }
    /**
     * 堆排序
     * 时间复杂度：平均O(nlogn),最好O(nlogn),最坏O(nlogn)
     * 辅助存储：O(1)
     * 稳定性：不稳定
     */
    private static void heapSort(int[] arr){
        int N = arr.length-1;
        for(int i = N/2; i > 0; i--){
            sink(arr, i, N);//构造出最大堆
        }
        while(N > 1){
            swap(arr, 1, N);
            N--;
            sink(arr, 1, N);
        }
    }
    private static void sink(int[] arr, int i, int N) {
        while(2*i <= N){
            int j = 2*i;
            if(j < N && arr[j] < arr[j+1]){
                j++;
            }
            if(arr[i] < arr[j]){
                swap(arr, i, j);
                i = j;
            }else{
                break;
            }
        }
    }
    /**
     * 优化的冒泡排序
     * 时间复杂度：平均O(n^2),最好O(n),最坏O(n^2)
     * 辅助存储：O(1)
     * 稳定性：稳定
     */
    private static void bubbleSort(int[] arr){
        boolean sorted = false;
        for(int i = 0; (!sorted)&&i<arr.length-1; i++){
            sorted = true;
            for(int j = arr.length-1; j > i; j--){
                if(arr[j] < arr[j-1]){
                    swap(arr, j, j-1);
                    sorted = false;
                }
            }
        }
    }
    /**
     * 快速排序
     * 时间复杂度：平均O(nlogn),最好O(nlogn),最坏O(n^2)
     * 辅助存储：O(1)
     * 稳定性：不稳定
     */
    private static void quickSort(int[] arr, int low, int high) {
        if(low < high){
            int middle = partition(arr, low, high);
            quickSort(arr, low, middle-1);
            quickSort(arr, middle+1, high);
        }
    }
    private static int partition(int[] arr, int low, int high) {
        int sorted = arr[low];
        int i = low+1;
        int j = high;
        while(true){
            while(i <=high && arr[i] <= sorted){
                i++;
            }
            while(j >=low+1 && arr[j] >= sorted){
                j--;
            }
            if(j <= i){
                break;
            }
            swap(arr, i, j);
        }
        swap(arr, low, j);
        return j;
    }
    /**
     * 归并排序
     * 时间复杂度：平均O(nlogn),最好O(nlogn),最坏O(nlogn)
     * 辅助存储：O(1)
     * 稳定性：稳定
     */
    public static void mergeSort(int[] arr, int low, int high){
        if(low >= high){
            return;
        }
        int middle = (low+high)/2;
        mergeSort(arr, low, middle);
        mergeSort(arr, middle+1, high);
        merge(arr, low, middle, high);
    }

    private static void merge(int[] arr, int low, int middle, int high) {
        int[] tmp = new int[high-low+1];
        int i = low;
        int j = middle+1;
        int k = 0;
        while(i <= middle && j <= high){
            if(arr[i] < arr[j]){
                tmp[k++]=arr[i++];
            }else{
                tmp[k++]=arr[j++];
            }
        }
        while(i <= middle){
            tmp[k++]=arr[i++];
        }
        while(j <= high){
            tmp[k++]=arr[j++];
        }
        for(int k2=0; k2 < tmp.length; k2++){
            arr[low+k2]=tmp[k2];
        }
    }
    /**
     * 基数排序
     * 时间复杂度：平均O(d(r+n)),最好O(d(n+rd)),最坏O(d(r+n))
     * 辅助存储：O(rd+n)
     * 稳定性：稳定
     */
    private static void radixSort(int[] arr) {
        int max = arr[0];
        for(int i = 1; i < arr.length; i++){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int times = 0;
        while(max > 0){
            max /= 10;
            times++;
        }
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        for(int i = 0; i < 10; i++){
            ArrayList<Integer> que = new ArrayList<>();
            queue.add(que);
        }
        for(int i = 0; i < times; i++){
            for(int a : arr){
                int x = a%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                queue.get(x).add(a);
            }
            int count = 0;
            for(int j = 0; j < 10; j++){
                while(queue.get(j).size() > 0){
                    arr[count++] = queue.get(j).get(0);
                    queue.get(j).remove(0);
                }
            }
        }
    }
}