0-0、基本排序算法总结

class Solution {
    //选择排序
    public int[] sortArray(int[] nums) {
        //[] [1,5,7,4,8] [3,1,0,0][6,7,11,11,13,15] 
        for (int i = 0; i < nums.length;i++){
            int min = i;
            for (int j = i + 1; j < nums.length;j++){
                if (nums[j] < nums[min]){
                    min = j;
                }
            }
            exchange(i, min, nums);
        }
        return nums;
    }

    public void exchange(int i , int j , int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    //插入排序
    public int[] sortArray(int[] nums) {
        //[] [1,5,7,4,8] [3,1,0,0][6,7,11,11,13,15] 
        for (int i = 1; i < nums.length;i++){
            for (int j = i; j >= 1 && nums[j - 1] > nums[j];j--){
             exchange(j, j - 1, nums);
            }
        }
        return nums;
    }

    public void exchange(int i , int j , int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    //希尔排序
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        int h = 1;
        while (3 * h + 1 < n){
            h = h * 3 + 1;
        }
        //[] [1,5,7,4,8] [3,1,0,0][6,7,11,11,13,15] 
        while (h > 0){
            for (int i = h; i < nums.length;i++){
                for (int j = i; j - h >= 0 && nums[j - h] > nums[j];j-=h){
                exchange(j, j - h, nums);
                }
            }
            h = h/3;
        }
        return nums;
    }

    public void exchange(int i , int j , int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    //归并排序
    int[] helper = null;
    public int[] sortArray(int[] nums) {
        //[] [1,5,7,4,8] [3,1,0,0][6,7,11,11,13,15] 
        int n = nums.length;
        helper = new int[n];
        sort(nums, 0, n - 1);
        return nums;
    }
    public void sort(int[] nums, int low, int hi){
        if (low == hi) {
            return;
        }
        int mid = (low + hi) / 2;
        sort (nums, low, mid);
        sort(nums, mid + 1, hi);
        merge(nums, low, mid, hi);
    }
    public void merge(int[] nums, int low, int mid,int hi){
        for(int k = 0; k <= hi;k++){
            helper[k] = nums[k];
        }
        int i = low;
        int j = mid + 1;
        for (int k = low;k <= hi;k++){
            if (i > mid){
                nums[k] = helper[j++]; 
            }else if (j > hi){
                nums[k] = helper[i++];
            }else if (helper[i] > helper[j]){
                  nums[k] = helper[j++];//小的在前
            }else{
                 nums[k] = helper[i++];
            }
        }

    }
}

class Solution {
    //堆排序
    public int[] sortArray(int[] nums) {
        PQSort pq = new PQSort(nums.length);
        for (int i = 0; i < nums.length; i++) {
            pq.insert(nums[i]);
        }
        for (int i = 0; i < nums.length;i++){
            nums[i] = pq.deleteMin();
        }
        return nums;

    }


    private static class  PQSort{
        int N = 0;
        int[] arr;
        public boolean isEmpty(){
            return N == 0;
        };
        public int size(){
            return N;
        };
        public void insert(int var){
            arr[++N] = var;
            swim();
        }
        public int deleteMin(){
            if (!isEmpty()){
                int temp = arr[1];
                exchange(1, N--);
                sink();
                return temp;
            }
            return - 1;
        }

        public PQSort(int size){
            arr = new int[size + 1];
        }

        public PQSort(int[] nums){

        }


        private void exchange(int i , int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //[ [] 5 4 8 7 2 9 1]
        private void swim(){
            int k = N;
            while (k > 1){
                if (arr[k] < arr[k / 2]){
                    exchange(k , k / 2);
                }
                k = k / 2;
            }
        }

        private void sink(){
            int k = 1;
            while (k <= N / 2){
                int j = k * 2;
                if (j + 1 <= N && arr[j] > arr[j + 1]){
                    j++;
                }
                if (arr[k] < arr[j]){
                    break;
                }
                exchange(k , j);
                k = j;
            }
        }
    }

}

//快速排序 待上传

class Solution {
    //冒泡排序
    public int[] sortArray(int[] nums) {
        //[ 7  5 8 2 1]
        for (int i = nums.length - 1 ; i > 0;i--){
            for (int j = 0; j < i; j++){
                if (nums[j] > nums[j + 1]){
                    exchange(nums,j, j + 1);
                }
            }
        }
        return nums;
    }


    private void exchange(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}

0-0、基本排序算法总结

原文：https://www.cnblogs.com/linyxBlog/p/14688902.html