要成功就做一百题-94

题目名称

今天来几个排序，都是经典题目，包括带拆分的快速排序，堆排序，归并排序。

描述

1. 快速排序
   快速排序核心就是分治法，取一个基准位置，然后从两边比较，符合条件替换。最终递归实现。
2. 堆排序
   堆排序核心就是调整堆的方法adjustHeap([], parent, len)，先按照大小构建堆，主要是移动数组的索引位，其中堆对应树的结构,升序情况下，构建大顶堆，性质是父节点不小于左右孩子arr[parent]>=arr[left] && arr[parent] >= arr[right], left = 2*parent+1, right=left+1，都是数组索引值，从找第一个非叶子节点开始。堆构建完成后，再将堆顶与最后一个调整，最终得到有序数组。
3. 归并排序
   归并也是分治法的思路，如果要让数据变有序，首先拆分小问题，然后可以理解成多个有序数组合并，有n个元素，相当于从n个元素个数为1的有序数组合并。

代码

如下是代码和注释

//堆排序
    private void heapSort(int[] arr){
        //build max , 从第一个非叶子节点开始
        for (int i = arr.length/2 -1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        System.out.println(Arrays.toString(arr));
        //调整堆
        int len = arr.length;
        for (int i = len-1; i > 0; i--) {
            int t = arr[0];
            arr[0] = arr[i];
            arr[i] = t;
            adjustHeap(arr, 0, --len);
        }
    }

    private void adjustHeap(int[] arr, int parent, int len){
        int temp = arr[parent];
        int left = 2* parent+1;
        int right = left+1;
        while (left< len){
            if(left+1 < len && arr[left] < arr[right]){
                left++;
            }
            if(arr[left]> temp){
                arr[parent] = arr[left];
                parent = left;
                left = 2*parent+1;
            }else {
                break;
            }
        }
        arr[parent] = temp;

    }

//快速排序

    private int partition(int[] arr, int left, int right){
        int temp = arr[left];
        while (left < right){
            while (arr[right] >= temp && left < right){
                --right;
            }
            arr[left] = arr[right];
            while (arr[left] <= temp && left < right){
                ++left;
            }
            arr[right] = arr[left];
        }
        arr[right] = temp;
        return left;
    }

    private void qsort1(int[] arr, int left, int right){
        if(left < right){
            int pivot = partition(arr, left, right);
            qsort1(arr, left, pivot - 1);
            qsort1(arr, pivot+1, right);
        }
    }

//归并排序

    private void msort(int[] arr, int left, int right, int[] temp){
        if(left < right){
            int mid = (left + right)/2;
            msort(arr,left, mid, temp);
            msort(arr,mid+1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private void merge(int[] arr , int left, int mid, int right, int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= right){
            if (arr[i] < arr[j]){
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid){
            temp[t++] = arr[i++];
        }
        while (j <= right){
            temp[t++] = arr[j++];
        }
        t = 0;
        while (left <= right){
            arr[left++] = temp[t++];
        }
    }

//单测例子
    @Test
    public void runTest(){
        int[] arr = new int[]{1,3,4,87,2,83,Integer.MAX_VALUE,Integer.MIN_VALUE};
        qsort1(arr,0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        int[] arr2 = new int[]{33,23,5,5,6,23,5,6,7,7};
        qsort2(arr2,0, arr2.length - 1);
        System.out.println(Arrays.toString(arr2));
    }