题解 | #排序#冒泡、快速、选择、堆排序、插入排序详细思路解释

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr == null || arr.length <= 1){
            return arr;
        }
        //思路一 利用系统函数排序
//         Arrays.sort(arr);
        
        //思路二 冒泡排序
//        bubbleOrder(arr);
        
        //思路三 快速排序（递归）对冒泡排序的优化 打破只能相邻两个元素进行交换的限制
//         quickOrder(arr,0,arr.length - 1);
        
        //思路四 选择排序 （循环选择最大的值往右侧放）
//         selectSort(arr);
        
        //思路五 堆排序 可以看成是对选择排序的优化，选择最大值的过程利用大顶堆实现 利用二叉树的结构 实现二叉堆（大顶堆）然后依次把顶部的数据做交换到尾部和下沉的处理
        heapSort(arr);
        
        //思路六 插入排序（将数组利用下标一分为2 左边是排好序的 右边是待排序的，不断从右边取元素插入到左边合适的位置，当然下标是不断往尾部移动的，移动完毕就OK了
//         insertSort(arr);
        return arr;
    }
    
    //冒泡排序
    private void bubbleOrder(int[] arr){
         for(int i = arr.length - 1;i>=0;i--){
            for(int j = 0;j<i;j++){
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    //快速排序 对冒泡排序的优化 打破只能相邻两个数交换的限制 支持指定元素范围的排序
    private void quickOrder(int[] arr,int begin,int end){
        if(begin >= end){
            return;
        }
        int left = begin;
        int right = end;
        int cur = arr[left];
        while(left < right){
            //第一步 从右侧找一个比cur小的 放到左侧的位置
            while(left < right && arr[right] >= cur){
                right --;
            }
            if(left < right){
                swap(arr,left,right);
            }
            //第二步 从左侧找一个比cur大的 放到右侧位置
            while(left < right && arr[left] <= cur){
                left ++;
            }
            if(left < right){
                swap(arr,left,right);
            }
        }
        quickOrder(arr,begin,left - 1);
        quickOrder(arr,left + 1,end);
    }
 
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    private void selectSort(int[] arr){
        //每次找一个最大的和最右侧还未排序的进行交换，arr size是多少就循环多少次
        for(int end = arr.length - 1;end >= 0;end--){
            //找到最大值 并交换位置
            int maxIndex = 0;
            for(int begin = 0;begin <= end;begin ++){
                maxIndex = arr[begin] > arr[maxIndex] ? begin : maxIndex;
            }
            //交换
            swap(arr,maxIndex,end);
        }
    }
    
    private void insertSort(int[] arr){
        //把数组分为两部分 用下标做分割 左边部分是排好序的 右边是未排序的
        //不断把右侧的插入到左侧 一开始可以认为左边就是第一个数 剩下的是右边
        for(int i = 1;i< arr.length;i++){
            //每次都从右边取出第一个数
            int firstOfRight = arr[i];
            //从左边的第一个位置开始 找出应该插入的位置
            int insertIndex = i;
            //i 就是左右两边的分割位置
            for(int j = 0;j<i;j++){
                if(arr[i] >= arr[j]){
                    continue;
                } else {
                    insertIndex = j;
                    break;
                }
            }   
            //进行插入操作 如果刚好等于 i 就不用挪屁股了 刚刚好
            if(insertIndex != i){
                  //0 - insertIndex - 1 不用动
                //insertIndex - i - 1 依次往后挪一个位置
                int targetValue = arr[i];
                for(int begin = i - 1;begin >= insertIndex;begin--){
                    arr[begin + 1] = arr[begin];
                }
                arr[insertIndex] = targetValue;
            }
        }
        
    }
    
    //堆排序
    private void heapSort(int[] arr){
        //第一步 原地建立大顶堆 自下而上的下滤方式（效率高）
        int len = arr.length;
        //从第一个非叶子节点（最大的下标，超过这个就不用做下沉操作了）开始循环 len / 2 - 1 位运算效率更高
        int maxIndex = (len >> 1) - 1;
        for(int i = maxIndex;i >= 0;i--){
            //下滤 或者叫下沉操作（父节点小于左右节点就把左右节点中较大的和父节点进行交换操作） 一直下沉到叶子节点为止
            siftDown(arr,i,len);
        }
        //第二步 依次把顶部的数据做交换到尾部和下沉的处理 这里跟选择排序思路就一直 选大的往后放就完了
        //大顶堆第一个位置当然是最大的了
        for(int i = 0;i<len;i++){
            swap(arr,0,len - 1 - i);
            //交换完了 要下沉 要不然就破坏大顶堆了
            siftDown(arr,0,len - i - 1);
        }
    }
    private void siftDown(int[] arr,int index,int len){
        int limitIndex = (len >> 1) - 1;
        //要小于等于第一个非叶子节点的位置才有可能继续下沉
        if(index > limitIndex){
            return;
        }
        //左节点下标 一定是存在的
        int left = index * 2 + 1;
        //右节点下标 可能不存在
        int right = left + 1;
        int max = left;
        if(right < len){
            max = arr[left] > arr[right] ? left : right;
        }
        if(arr[index] < arr[max]){
            //交换
            swap(arr,index,max);
            //交换完毕后 可能还要继续下沉 注意交换完毕后当前值的index就是maxIndex了
            siftDown(arr,max,len);
        }
    }
}