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;
    }
}