1.快速排序

基本思想：

  • 先从数列中取出一个数作为基准数
  • 分区过程中，将这个数交换到数组的左端，左右两个指针分别从两端开始，先从右端判断，大于基数，则左移右指针，小于基数，则交换，同时右移右指针。然后再从右指针开始，直到左右张指针相同，此时，将基数存放进去，这样，基数左边的数就全部小于基数，基数右边的数就全部大于基数

  • 再对左右区间重乎第二步，直到最小区间只有一个数。

    1. class Solution {
    2.   public int[] sortArray(int[] nums) {
    3.       if(nums == null || nums.length == 0){
    4.           return nums;
    5.       }
    6.       quickSort(nums, 0 , nums.length - 1);
    7.       return nums;
    8.   }
    9.   //对nums数据中索引为x到y的位置快速排序
    10.   public void quickSort(int[] nums, int x, int y){
    11.       if(x < y){
    12.           //取出基数
    13.           int pos = getPosValue(nums, x,y);
    14.           //左右区间递归排序
    15.           quickSort(nums,x,pos-1);
    16.           quickSort(nums,pos+1,y);
    17.       }
    18.   }
    20.   //x为左指针，y为右指针
    21.   public int getPosValue(int[] nums, int x, int y){
    22.       //取中间的数字，同时交换到最左端
    23.       int pos =  x + ((y -x) /2);
    24.       swap(nums,x,pos);
    25.       pos = x;
    26.       //基数为posVal
    27.       int posVal = nums[pos]; 
    28.       //当x == y，跳出循环，将基数放入该位置
    29.       while(x < y){
    30.           //从右指针开始，当右指针的数大于基数时，位置不变，右指针左移
    31.           while(x < y && nums[y] >= posVal){
    32.               y--;
    33.           }
    34.           //此时左移到右指针的数大于基数，做左指针当前位置是基数，可视为空，将右指针数值赋值给左指针，同时左指针右移
    35.           if(nums[y] < posVal){
    36.               nums[x] = nums[y];
    37.               x++;
    38.           }
    39.           //理由如上，次数右指针的位置可视为空，需要挑选比基数大的值赋值进去
    40.           while(x<y && nums[x] <= posVal){
    41.               x++;
    42.           }
    43.           if(nums[x] > posVal){
    44.               nums[y] = nums[x];
    45.               y--;
    46.           }
    47.           //两次赋值后，当前左指针的位置再次为空，再次循环
    48.       }
    49.       nums[x] = posVal;
    50.       return x;
    51.   }
    53.   private void swap(int[] nums, int i, int j) {
    54.       int temp = nums[i];
    55.       nums[i] = nums[j];
    56.       nums[j] = temp;
    57.   }
    58. }

    2.堆排序

    堆排序分为大根堆和小根堆

  • 必须是完全二叉树

  • 二叉堆中的每一个节点，都必须大于等于（或小于等于）其子树中每个节点的值

image.png
根据父节点索引（index）来定位子节点

  • 左子节点 index*2 + 1
  • 右子节点 index*2 + 2

根据子节点索引来定位父节点

  • (index -1)/2

堆排序有两步

  • 建堆
  • 排序

建堆

利用上浮操作建堆
image.png**
假设让我们插入新的元素 1 （绿色节点），我们发现此时 1 小于其父节点 的值 7 ，并不遵守小顶堆的规则，那我们则需要移动元素 1 。让 1 与 7 交换，（如果新插入元素大于父节点的值，则说明插入新节点后仍满足小顶堆规则，无需交换）。
之前我们说过，我们可以用数组保存堆，并且可以通过 （i-1）/2得到其父节点的值，那么此时我们就明白怎么做啦。
image.png
image.png
交换之后，我们继续将新插入元素，也就是 1 与其父节点比较，如果大于其父节点，则无需交换，循环结束。若小于则需要继续交换，直到 1 到达适合他的地方。大家是不是已经直到该怎么做啦！

  1. public void swim (int index) {
  2.     while (index > 1 && nums[index/2] > nums[index]) {
  3.         swap(index/2,index);//交换
  4.         index = index/2;
  5.     }
  6. }
  8. 作者：chefyuan
  9. 链接：https://leetcode-cn.com/problems/sort-an-array/solution/dong-hua-mo-ni-yi-ge-po-dui-pai-wo-gao-l-i6mt/
  10. 来源：力扣（LeetCode）
  11. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

利用下沉操作建堆

image.png**
我们发现，7 位于堆顶，但是此时并不满足小顶堆的要求，我们需要把 7 放到属于它的位置，我们应该怎么做呢？
看完视频是不是懂个大概了，但是不知道大家有没有注意到这个地方。为什么 7 第一次与其左孩子节点 2 交换，第二次与右孩子节点 3 交换。见下图
image.png
其实很容易理解，我们需要与孩子节点中最小的那个交换，因为我们需要交换后，父节点小于两个孩子节点，如果我们第一步，7 与 5 进行交换的话，则同样不能满足小顶堆。

那我们怎么判断节点找到属于它的位置了呢？主要有两个情况

待下沉元素小于（大于）两个子节点，此时符合堆的规则，无序下沉，例如上图中的 6
下沉为叶子节点，此时没有子节点，例如 7 下沉到最后变成了叶子节点。
我们将上面的操作称之为下沉操作。

  1. public void sink (int[] nums, int index,int len) {
  2.         while (true) {
  3.             //获取子节点
  4.             int j = 2 * index;
  5.             if (j < len-1 && nums[j] < nums[j+1]) {
  6.                 j++;
  7.             }
  8.             //交换操作，父节点下沉，与最大的孩子节点交换
  9.             if (j < len && nums[index] < nums[j]) {
  10.                 swap(nums,index,j);
  11.             } else {
  12.                 break;
  13.             } 
  14.             //继续下沉
  15.             index = j;
  16.         }
  17.     }
  19. 作者：chefyuan
  20. 链接：https://leetcode-cn.com/problems/sort-an-array/solution/dong-hua-mo-ni-yi-ge-po-dui-pai-wo-gao-l-i6mt/
  21. 来源：力扣（LeetCode）
  22. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

排序
image.png
假设我们想要去除堆顶的 11 ，那我们则需要将其与堆的最后一个节点交换也就是 2 ，2然后再执行下沉操作，执行完毕后仍能满足堆的要求，见下图
image.png
相当于我们再数组中将第一位最大的与最后一位交换，这样最大的数值就放在了最后面，然后再对前面的数组做调整，这样前面数组的最大值也会调整到首位，再次交换，重复操作。
好啦，大家是不是已经搞懂啦，下面我们总结一下堆排序的具体执行过程
1.建堆，通过下沉操作建堆效率更高，具体过程是，找到最后一个非叶子节点，然后从后往前遍历执行下沉操作。
2.排序，将堆顶元素（代表最大元素）与最后一个元素交换，然后新的堆顶元素进行下沉操作，遍历执行上诉操作，则可以完成排序。

  1. public class Solution {
  3.     public int[] sortArray(int[] nums) {
  4.         int len = nums.length;
  5.         // 将数组整理成堆
  6.         heapify(nums);
  8.         // 循环不变量：区间 [0, i] 堆有序
  9.         for (int i = len - 1; i >= 1; ) {
  10.             // 把堆顶元素（当前最大）交换到数组末尾
  11.             swap(nums, 0, i);
  12.             // 逐步减少堆有序的部分
  13.             i--;
  14.             // 下标 0 位置下沉操作，使得区间 [0, i] 堆有序
  15.             siftDown(nums, 0, i);
  16.         }
  17.         return nums;
  18.     }
  20.     /**
  21.      * 将数组整理成堆（堆有序）
  22.      *
  23.      * @param nums
  24.      */
  25.     private void heapify(int[] nums) {
  26.         int len = nums.length;
  27.         //i = (len - 1) / 2最后一个元素的父节点，依次遍历下沉
  28.         for (int i = (len - 1) / 2; i >= 0; i--) {
  29.             siftDown(nums, i, len - 1);
  30.         }
  31.     }
  33.     /**
  34.      * @param nums
  35.      * @param k    当前下沉元素的下标
  36.      * @param end  [0, end] 是 nums 的有效部分
  37.      */
  38.     private void siftDown(int[] nums, int k, int end) {
  39.         //当前节点存在子节点的时候，循环
  40.         while (2 * k + 1 <= end) {
  41.             //左子节点
  42.             int j = 2 * k + 1;
  43.             //如果存在右子节点，并且右子节点的值大于左子节点，此时最大的就是右子节点，需要交换的也是右子节点
  44.             if (j + 1 <= end && nums[j + 1] > nums[j]) {
  45.                 j++;
  46.             }
  47.             //交换的子节点大于父节点，交换，否则，跳出循环
  48.             if (nums[j] > nums[k]) {
  49.                 swap(nums, j, k);
  50.             } else {
  51.                 break;
  52.             }
  53.             //从交换后的节点再次开始下沉操作
  54.             k = j;
  55.         }
  56.     }
  58.     private void swap(int[] nums, int index1, int index2) {
  59.         int temp = nums[index1];
  60.         nums[index1] = nums[index2];
  61.         nums[index2] = temp;
  62.     }
  63. }

3.归并排序

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
排序 - 图9

排序 - 图10

  1. package sortdemo;
  3. import java.util.Arrays;
  5. /**
  6.  * Created by chengxiao on 2016/12/8.
  7.  */
  8. public class MergeSort {
  9.     public static void main(String []args){
  10.         int []arr = {9,8,7,6,5,4,3,2,1};
  11.         sort(arr);
  12.         System.out.println(Arrays.toString(arr));
  13.     }
  14.     public static void sort(int []arr){
  15.         int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
  16.         sort(arr,0,arr.length-1,temp);
  17.     }
  18.     private static void sort(int[] arr,int left,int right,int []temp){
  19.         if(left<right){
  20.             int mid = (left+right)/2;
  21.             sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
  22.             sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
  23.             merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
  24.         }
  25.     }
  26.     private static void merge(int[] arr,int left,int mid,int right,int[] temp){
  27.         int i = left;//左序列指针
  28.         int j = mid+1;//右序列指针
  29.         int t = 0;//临时数组指针
  30.         while (i<=mid && j<=right){
  31.             if(arr[i]<=arr[j]){
  32.                 temp[t++] = arr[i++];
  33.             }else {
  34.                 temp[t++] = arr[j++];
  35.             }
  36.         }
  37.         while(i<=mid){//将左边剩余元素填充进temp中
  38.             temp[t++] = arr[i++];
  39.         }
  40.         while(j<=right){//将右序列剩余元素填充进temp中
  41.             temp[t++] = arr[j++];
  42.         }
  43.         t = 0;
  44.         //将temp中的元素全部拷贝到原数组中
  45.         while(left <= right){
  46.             arr[left++] = temp[t++];
  47.         }
  48.     }
  49. }