排序算法：快速排序、堆排序

1、快速排序

? 1.1左右指针法

1. 创建两个游标，分别指向数组两侧
2. 右游标先向右走，找到小于第一个元素的元素停止。（第一个元素为拆分后数组的第一个元素，而不是下标为0的数组元素）
3. 左游标向右走，找到大于第一个元素的元素停止。
4. 左右游标所指值交换（如果右找到小于第一个元素的元素后，左游标还没找到比第一个元素大的碰到右游标，则将此时这个元素与第一个元素交换）。
5. 此时交换到中间的元素前面都是比它小或等于它的元素，后面都是比它大或等于的元素。（此时这个元素在整个数组的位置已经拍好）。
6. 将此元素的左右两边元素拆分为两个数组（此元素不参与后面的排序了），继续以上操作，直至被拆分的数组全为一个元素。

为什么要j（右）游标必需先动？

因为j停下来后i（左）可能会直接碰到j，此时j可直接与left交换, 因为j所指的一定比left小。

如果i先动，j还没找到比base小的值， 就因碰到i停下，此时如果j所指比base大交换后就出错了。? ?我选取的是第一个元素作为base，如果是最后一个则反过来。

public static void quickSort(int []arr,int left,int right){
        //当分组后的数组只剩下一个元素，则直接返回
        if (left >= right){
            return;
        }
        //以数组的第一个元素作为基准元素
        int base = arr[left];
        int l = left;
        int r = right;
        //这个循环是待l与r相遇的元素，左边小于基准元素，右边大于基准元素
        while (l<r){
            //右指针左移直到遇到小于base的元素
            while(r>l&&arr[r]>=base){
                r--;
            }
            //左指针右移，直到遇到大于base的元素
            while (l<r&&arr[l]<=base){
                l++;
            }
            //此时右指针指向的值小于base，左指针指向的值大于base
            //交换两个所指元素
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //相遇后将这个元素与基准元素交换。
        //则基准元素左边下于它，右边大于它。则这个元素排序完成
        arr[left] = arr[l];
        arr[l] = base;
        //递归实现其他元素的排序
        quickSort(arr,left,r-1);
        quickSort(arr,r+1,right);
    }

? 1.2双指针法

1、选出一个key，一般是最左边或是最右边的。
2、起始时，left指针指向序列开头，cur指针指向left+1。
3、若cur指向的内容小于key，则left先向后移动一位，然后交换left和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达right位置，交换left和key（i）的值。

再这个排序过程中left指向的元素及其左边的所有元素都是小于等于key的，它右边的与cur之间的则是大于key的元素。

经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
?

public static void quickSort2(int []arr, int left, int right){
        if (left>=right){
            return;
        }
        int base = arr[left];
        int i = left;
        int curv = left+1;
        while (curv<=right){
            if (arr[curv]<base){
                int temp = arr[++left];
                arr[left] = arr[curv];
                arr[curv] = temp;
            }
            curv++;
        }
        int temp = arr[left];
        arr[left] = base;
        arr[i] = temp;
        quickSort2(arr, i, left-1);
        quickSort2(arr,left+1,right);
    }

2、堆排序?

利用完全二叉树构建 大顶堆（父节点的值大于或等于其左右孩子的值）。

1. 先将数组变为完全二叉树。
2. 定义parent游标，让parent游标从后往前移动（从下到上，从右到左），直到有节点有孩子节点，parent指向它。
3. 定义一个child游标，指向parent指向节点的左孩子，判断右孩子是否为空（如果完全二叉树的一个节点存在孩子，那么左孩子一定存在（完全二叉树的定义决定））
4. 判断parent所指节点的右孩子是否存在，如果存在，就比较左右孩子的大小，将child指向大的那个孩子。
5. 比较父子节点大小（比较parent所指节点和child所指节点大小），如果子节点大于父节点，则交换两节点数值（如果父节点大于子节点（此次循环结束，则parent游标一开始此次循环的前一位，child按照c规律来移动继续执行（c-f）））。
6. 如果child所指节点有孩子（如果child没有孩子，则结束此次循环，则parent游标一开始此次循环的前一位），praent游标指向child所指节点。child游标指向parent节点的左孩子（继续d-f）。
7. 重复执行（）

堆顶元素与堆底元素进行互换，互换完成后，堆底元素（最底层的最右边的元素）不再参与构建（这个元素已经排好序了）。

   public static void main(String[] args) {
        int [] arr = new int[]{1,3,2,4,8,3};
        //先构建大顶堆
        for (int p = arr.length-1; p >=0 ; p--) {
            abjust(arr,p,arr.length);
        }
        //此时大顶堆的堆顶是第一大的
        for (int i = arr.length-1; i >=0; i--) {
            //将堆顶和为排序区域第一个交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //此时大顶堆的堆顶不符合大顶堆性质，则需要一次修改变为大顶堆
            abjust(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }

  public static void abjust(int []arr, int parent, int length){
        int child = parent*2+1;
        while (child<length){
            int rChild = child+1;
            if (rChild<length&&arr[rChild]>arr[child]){
                child++;
            }
            if (arr[child]>arr[parent]){
                int temp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = temp;
                parent = child;
                child = child*2+1;
            }else {
                break;
            }
        }
  }

?

????????????????