1 堆排序

步骤（以升序排列为例，排序完结后数组开端为最大值）：

• 从最初一个非叶子结点开始（叶结点天然不必调整，第一个非叶子结点 arr.length/2-1），从左至右，从下至上进行调整，最终将一个无序序列结构成一个大根堆，此时序列头就是最大值。
• 将堆顶元素与开端元素进行替换，使开端元素最大,即将最大元素”沉”到数组末端。而后持续调整堆；再将堆顶元素与次开端元素替换，失去第二大元素;如此重复进行替换、重建、替换。

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

public class HeapSort {
    public static void main(String[] args){
        int []arr = {7,6,7,11,5,12,3,0,1};
        System.out.println("排序前："+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后："+Arrays.toString(arr));
    }

    public static void sort(int[] array){
        //1.构建大顶堆
        //从第一个非叶子节点开始，从左至右，从下到上调整
        for(int i=array.length/2-1;i>=0;i--){
            adjustHeap(array,i,array.length);
        }
        //2.重复替换堆顶和开端元素，最终实现排序
        for(int i=array.length-1;i>0;i--){
            swap(array,0,i);
            adjustHeap(array,0,i);
        }
    }

    //调整大顶堆
    //len示意调整到数组的第几个元素，比方第n轮替换，阐明是倒数第n个元素与顶部替换，那么len=array.length-n
    public static void adjustHeap(int[] array,int index,int len){
        int temp=array[index];
        for(int i=index*2+1;i<len;i++){ //从左子节点开始调整
            //如果存在左右子节点，抉择左右子节点中值较大的点
            if(i+1<len && array[i]<array[i+1])
                i++;
            if(array[i]>temp){
                array[index]=array[i];//此处只将子节点的值赋值给父节点，并不是替换
                index=i; ////index调整到换下来的子节点的地位，持续看子结构有没有呈现凌乱
            }else
                break;
        }
        array[index]=temp; //将temp值放到最终的地位
    }

    public static void swap(int []array,int a ,int b){
        int temp=array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

2 疾速排序

重点：

• public static void quickSort(int[] array,int left,int right){}办法
• 每次先右指针左移，保障了最初l,r相遇当前所对应的值，肯定是小于参照点的值的，因而间接替换参照点与该点即可。

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(int[] array){
        quickSort(array,0,array.length-1);
    }

    public static void quickSort(int[] array,int left,int right){
        if(left>right)
            return;
        int temp=array[left];
        int l=left,r=right;
        while(l<r){
            //每次先右指针左移，保障了最初l,r相遇时肯定指向<temp的值，这样最初与array[left]替换当前肯定是右边小左边大。
            while(array[r]>=temp && l<r)
                r--;
            while(array[l]<=temp && l<r) {
                l++;
            }
            if(l<r){//做一次判断
                swap(array,l,r);
            }
        }
        array[left]=array[l];
        array[l]=temp;

        //递归调用
        quickSort(array,left,l-1);
        quickSort(array,l+1,right);
    }

    public static void swap(int[] array,int a,int b){
        int temp=array[b];
        array[b]=array[a];
        array[a]=temp;
    }
}