前言

最近一直比较忙，马上就要考试了，所以LeetCode稍微暂时放了放，集中精力回顾了下内部排序算法，本篇文章会对常见的十大内部排序算法进行系统的回顾。

概述

算法分类

常见排序算法可以分为两大类：

比较排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法复杂度

在这里要说明的是，这个图里的快排空间复杂度错了，快排的平均空间复杂度应该是 O(logn)，就是栈的深度，但是最差的情况下，比如全是倒序，则空间复杂度为栈深度 O(n)。归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是 O(n)。

部分补充

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
不稳定排序算法：谐音记忆法：快（快排）些（希尔）选（选择）对（堆）。
总共4个不稳定，6个稳定。

冒泡排序

基本思想

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

一次比较两个数字，两两比较，如果前者比后者大，则交换，以此类推，一轮下来，就会产生一个最大的数；
当某一轮没有产生任何一次交换，则说明冒泡完成。

动图演示

代码实现

package 排序;

import JAVA_I_O.Buffer.BufferedInputStream;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
//测试类
public class SortTest {
    public static void main(String[] args) throws Exception {
        System.out.println("请输入一个数组，用逗号分隔：");
        Scanner sc = new Scanner(System.in);
        String next = sc.nextLine();
        String[] net = next.split(",");
//        String[] arr = Arrays.copyOf(net,net.length);
//        int[] arr = new int[0];
        ArrayList<Integer> arrayList = new ArrayList<Integer>();

        for (int i = 0 ; i < net.length ; i++) {
            arrayList.add(Integer.parseInt(net[i]));
//            System.out.println(arr[i]);
        }
        int size = arrayList.size();
        Integer[] arrInt = arrayList.toArray(new Integer[size]);
        int[] arr = new int[size];
        for(int i = 0 ; i < arrInt.length;i++){
            arr[i] = arrInt[i];
        }
//        System.out.println(arr[i]);
//        int[] InsertSortArray = Sort.InsertSort(arr);
//        int[] SelectSortArray = Sort.SelectSort(arr);
        Sort.BubbleSort(arr);
//        int[] ShellSortArray = Sort.ShellSort2(arr);
//        Sort.quickSort(arr,0,arr.length-1);
//        Sort.heapSort(arr,arr.length-1);
//        Sort.courtSort(arr);
//        Sort.BucketSort(arr);
//        Sort.radixSort(arr);
//        for (int i = 0 ; i < ShellSortArray.length ; i++) {
//            System.out.print(ShellSortArray[i] + " ");
//        }

    }
}

 /**
 * 冒泡
 *
 * @param sortArray 原始数组
 * @return 排序数组
 */
public static void BubbleSort(int[] sortArray) {
    //复制一份原始数组，用于排序操作
    int[] arr = Arrays.copyOf(sortArray, sortArray.length);
    //循环n-1轮，剩最后一个就不需要交换了
    for (int i = 1; i < arr.length; i++) {
        //标志位，当一轮下来没有任何变化时，说明冒泡结束，需要结束循环
        boolean flag = true;
        //每一轮都要两两比较，注意每一轮结束都会确认一个值在正确的位置上，所以j的遍历次数得稍加注意
        for (int j = 0; j < arr.length - i; j++) {
            //位置变化的同时说明冒泡没有结束
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    System.out.println(Arrays.toString(arr));
}

算法效率

时间复杂度：很明显，看代码就知道，冒泡有两个for循环，所以一般情况下和最坏情况下的复杂度都为O(n²)，最好的时间复杂度就是一次冒泡就完成了，即为O(n);
空间复杂度：在冒泡中，只用了temp来存储中间变量交换，没有用到其他空间(我的代码中的复制初始数组的容量其实可以省去)，所以空间复杂度是O(1);
稳定性：交换过程中，如果相邻两者的值一样，则不会交换，所以明显冒泡排序是稳定的。

tips

外循环 n-1次；
注意添加标志位，判断冒泡是否结束；
注意内部循环的次数，每外部循环结束一次，就确定一个数的最终位置。

快速排序

基本思想

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法描述

首先选定一个基准值（pivot），我一般的做法是选定最左边的作为基准；
定义两个指针，一个指向最右边，一个指向最左边，然后注意让右边的先动，等右边指针所指的数值小于pivot时，右边指针不再往左走，不准动了，然后移动左边指针，等左边指针所指向的数值大于pivot时，左边指针停下，不再向右移动，然后二者交换；
交换完毕后，重复第二步，右边指针继续向左，重复；
直到左右两个指针相遇，两个都停下，将指向的数值和pivot交换，至此数组就分成了两个子数组，pivot左侧比其小，右边比其大；
然后递归子数组，直到子数组为0（low > high）。

动图演示

代码实现

/**
 * 快速排序
 * 后续所有测试都跟冒泡那章写的一样
 * @param sortArray 原始数组
 * @param low 最左侧
 * @param high 最右侧
 */
public static void quickSort(int[] sortArray, int low, int high) {
    //当low = high 时，说明子数组只剩一个数了，还排个锤子啊
    if (low < high) {
        //拿到基准值，这样就可以愉快的递归了
        int pivot = partition(sortArray, low, high);
        //注意哦，递归时可没有把pivot放入其中
        quickSort(sortArray, low, pivot - 1);
        quickSort(sortArray, pivot + 1, high);
        System.out.println(Arrays.toString(sortArray));
    }
}

/**
 * 快排主思路
 * @param sortArray
 * @param low
 * @param high
 * @return
 */
private static int partition(int[] sortArray, int low, int high) {
    //我个人习惯是把最左边定为基准值，具体方法有很多啦，随便你，爱咋咋的
    int pivot = low;
    //定义左右两指针
    int p = low;
    int q = high;
    //相遇就结束了哈，然后直接交换基准和指向的数值就行咯
    while (p < q) {
        //没相遇并且右指针指向的值比基准值大，就向左移动，若比基准值小，那就得停下
        while (p < q && sortArray[pivot] <= sortArray[q])
            q--;
        while (p < q && sortArray[pivot] >= sortArray[p])
            p++;
        //都停下了就交换叭！
        swap(sortArray, p, q);
    }
    swap(sortArray, pivot, p);
    //不要忘记最后要返回这个基准值
    return p;
}


public static void swap(int[] sum, int i, int j) {
    int temp = sum[i];
    sum[i] = sum[j];
    sum[j] = temp;
}

算法效率

快排嘛，用了分治的思想咯，所以复杂度肯定是比冒泡低的，至于是多少，我们稍加分析一下：

时间复杂度：分治思想，但是绝壁不是线性的，因为它一轮下来搞来搞去，交换这交换那的，所以一轮是O(n),综合前面的分治就是nlogN了。我说的是最好情况和平均情况哈，最坏那肯定还是O(n²)，因为可能你很不幸，基准值就是最大的，然后就得疯狂交换。
空间复杂度：不瞎的都看得出来，就用了一个temp中间变量用来存值，所以是O(1) 。
稳定性：哎呀肯定是不稳定的啊，两个指针在那换来换去，能稳定嘛…

tips

注意递归时的子串是不包括pivot的，一个是(low,pivot-1)，一个是(pivot+1,high)；
两个指针相遇，不用判断和pivot值的大小，直接交换即可，因为两个指针只会有一个在移动，那么此时此刻另一个指针一定是静止的，假如此时是右边的指针移动，那么相遇的位置即左指针停下的位置，而左指针停下说明之前右边指针也停下来过并且和左边指针指向的数进行了交换(因为只有右边停下，左边才能移动)，那么此时左边指向的数是一定比pivot小的，所以必然可以直接交换，换个角度考虑也是一样的。
还有，我一直强调必须右指针先动(其实只要是和基准相反方向的指针先动就行)，为什么捏，因为嘛，给你举个例子吧，假如有这样一个数组 9,3,4,5,6,7,10 ,左边的先动那就凉了啊，因为最后你都定在10，一叫换就变成了10,3,4,5,6,7,9，这还玩个锤子啊———–> 快排从右边开始的原因

至于快排的优化

采用三数取中法

package 排序.二刷排序;

import java.util.Arrays;
import java.util.Scanner;

public class quickSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入数组的大小： ");
        int len = scanner.nextInt();
        int[] nums = new int[len];
        for (int i = 0;i < len;i++){
            nums[i] = scanner.nextInt();
        }
        quick(nums,0,len-1);
        System.out.println(Arrays.toString(nums));

    }
    public static void quick(int[] nums,int left,int right){
        if(left < right){
            int partition = partition(nums,left,right);
            quick(nums,left,partition-1);
            quick(nums,partition+1,right);
        }

    }

    private static int partition(int[] nums, int left, int right) {
        // 基准值
        // 优化，就是尽量能做到分治，也就是选取的基准值尽量在中间是性能最好的
        int mid = (left + right)/2;
        dealPivot(nums,left,mid,right);
        int pivot = left;
        // 定义两个指针
        int p = left;
        int q = right;
        while(p < q){
            while(p < q && nums[q] >= nums[pivot]){
                q--;
            }
            while(p < q && nums[p] <= nums[pivot]){
                p++;
            }
            swap(nums,p,q);
        }
        swap(nums,p,pivot);
        return p;
    }

    private static void dealPivot(int[] nums, int left, int mid, int right) {
        if((left - mid) * (mid - right) > 0){  // left < mid < right
            swap(nums,left,mid);
            return;
        }
        else if((mid - left) * (left - right) > 0){ // left 是中间值
            return;
        }
        swap(nums,left,right);
        return;
    }


    private static void swap(int[] nums, int p, int q) {
        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
    }
}

三路快排，这个适用于有大量相同数字的数组「LeetCode 第 75 题」

https://www.bilibili.com/video/BV1Kr4y187VP/?spm_id_from=333.337.search-card.all.click&vd_source=f0b1231ec6fe669e8d0d175afde5696d

https://www.bilibili.com/video/av73100790?from=search&seid=4070762078682607758

class quickSortByThree{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入要输入的排序数组的长度：" );
        int len = scanner.nextInt();
        int[] nums = new int[len];
        for(int i = 0; i < len;i++){
            nums[i] = scanner.nextInt();
        }
        quickSortByThreeWays(nums,0,len-1);
        System.out.println(Arrays.toString(nums));
    }

    private static void quickSortByThreeWays(int[] nums, int left, int right) {
        if(left < right){
            // 此时需要返回的值是两个，一个是基准值的最终位置，还有一个是与基准值相同的最后一个数的位置
            // 适用于很多相同数字的数组排序，官方的 Arrays.sort() 也是采用的三路快排
            int[] par = quickThreePartition(nums,left,right);
            int lt = par[0];
            int gt = par[1];
            quickSortByThreeWays(nums,left,lt-1);
            quickSortByThreeWays(nums,gt+1,right);
        }

    }

    private static int[] quickThreePartition(int[] nums, int left, int right) {
        int pivot = left;
        // 定义三个指针
        int cur = left + 1;
        int lt = left + 1;  // nums[left...lt-1] 都是 小于 pivot 的
        int gt = right; // nums(gt...right] 都是 大于 pivot 的
        while(cur <= gt){
            if(nums[cur] < nums[pivot]){
                swap(nums,cur,lt); 
                cur++;
                lt++;
            }
            else if(nums[cur] > nums[pivot]){
                swap(nums,gt,cur);
                gt--;
            }
            else cur++;
        }
        swap(nums,lt-1,pivot);
        return new int[]{lt-1,gt};
    }
    private static void swap(int[] nums, int p, int q) {
        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
    }
}

简单插入排序

基本思想

看名字叭，插入，还尼玛简单插入，顾名思义，就是把这个待排序数组看成是一步步插好的数组，用的是最简单的方法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

注：啥是in-place知道不：原地算法)

动图演示

代码实现

/**
 * 直接插入排序
 * 我没有in-place哈，但是是可以的
 * @param SortArray 原始数组
 * @return 排序数组
    */

  public static void InsertSort(int[] SortArray) {
    int[] arr = Arrays.copyOf(SortArray, SortArray.length);
    //从1开始哦，因为第一个数默认是排好序的啦
    for (int i = 1; i < arr.length; i++) {
        int temp = arr[i];
        int j = i;
        for (; (j > 0 && arr[j - 1] > temp); j--) {
            //这一步最关键，因为要注意每当插入一个数字，其后面都要往后顺移一位，不然的话就空不出要插入的位置！！！
            arr[j] = arr[j - 1];
        }
        //如果没有变化，则temp依然等于arr[i],如果变化，则将arr[i]移动过来就行
        //注意不能直接arr[j] = arr[i]哦，因为此时的i索引值已经可能变化啦！！！！temp非常的关键！！
        arr[j] = temp;
    }
    System.out.println(Arrays.toString(arr));
  }

算法效率

时间复杂度：这种直接插入麻烦的一笔，如果是原数组是倒序，那每一轮都得疯狂插，毫无疑问最坏情况下的时间复杂度是O(n²)，最好的时间复杂度就是一次都不用给后来者让位，那么就是线性复杂度了O(n)，平均下来依旧是O(²)。
空间复杂度：in-place,O(1) 。
稳定性：当然是稳定的啦！

tips

注意插入的时候是将比插入的数大的已经排序好的数全部后移一位哦！！！给朕让位的赶脚…
用temp来保存当前需要插入的数据是非常重要的，这也是插入排序唯二需要注意的地方，还要一个需要注意的地方就是全部后移一位。

希尔排序

基本思想

希尔排序又叫缩小增量排序，1959年Shell发明。是插入排序的一种高速而稳定的改进版本。

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法描述

希尔排序有n种步长方式，这里介绍两种，一种是循环折半，另一种是 gap = gap * 3 + 1。

具体：希尔排序增量序列介绍。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

代码实现

/**
* 其实就是将直接插入排序的间隔1变为更大，也就是其实就多了一个循环，就是多次缩小间隔的循环，其他跟直接插入是一样的
*
* @param sortArray
* @return
*/
  public static int[] ShellSort2(int[] sortArray) {
  int[] arr = Arrays.copyOf(sortArray, sortArray.length);
  int size = sortArray.length;
  for (int increment = size / 2; increment > 0; increment /= 2) {
      for (int i = increment; i < size; i++) {
          int temp = arr[i];
          int j = i;
          for (; (j >= increment && arr[j - increment] > temp); j -= increment) {
              //这一步最关键，因为要注意每当插入一个数字，其后面都要往后顺移increment位，不然的话就空不出要插入的位置！！！
              arr[j] = arr[j - increment];
          }
          //如果没有变化，则temp依然等于arr[i],如果变化，则将arr[i]移动过来就行
          arr[j] = temp;
      }
  }
  return arr;
  }


 /**
 * 不是我写的
 *
 * @param sourceArray
 * @return
 * @throws Exception
 */
public static int[] ShellSort1(int[] sourceArray) throws Exception 			 {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    int gap = 1;
    while (gap < arr.length) {
        gap = gap * 3 + 1;
    }

    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i;
            for (; j >= 0 && arr[j - gap] > tmp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = tmp;
        }
        gap = (int) Math.floor(gap / 3);
    }

    return arr;
}

算法效率

时间复杂度：最坏和最好我们都知道，这个就跟直接插入没区别，最好最坏都是取决于原数组序列，所以最好的时间复杂度依旧是O(n)，最坏的时间复杂度依旧是O(n²)，平均复杂度？我tm也不知道为啥，记住就是啦，O(n^1.3)。
空间复杂度：这个简单的一批，还不就是O(1)。
稳定性：这种跳跃性的当然是不稳定了。例如arr = {3,2,2}。

tips

简单的一批…不就是把直接插入的1变成 increment 嘛 …… 没啥需要注意的！

啊！！！不对，其实还是有一个需要注意的！！！

这里是三重循环，因为那个步长要变化，然后不同步长都要进行排序，一次排序是两重循环 over

简单选择排序

基本思想

选择排序，意在突出选择 二字，所以我们要做的就是有一个选择的过程，至于简单选择，简而言之就是非常非常简单的选择排序，那不就是每次都找个最小值往前扔嘛…

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述

n个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：(这么官方肯定是复制的啦哈哈哈哈哈)

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；(这种屁话读起来简直就是浪费生命)
n-1趟结束，数组有序化了。

注：就是说 ——– 每次遍历数组都选一个最小的扔到最前面（跟要扔的位置的数进行交换），然后从剩下的还没排序的继续遍历，继续扔，扔了n-1次就结束了叭。

动图演示

代码实现

/**
 * 简单选择排序
 *
 * @param SortArray 原始数组
 * @return 排序数组
 */
public static int[] SelectSort(int[] SortArray) {
    int[] arr = Arrays.copyOf(SortArray, SortArray.length);
    //注意是n-1轮，一轮一个最小值，最后那个不用轮了
    for (int i = 0; i < arr.length - 1; i++) {
        //最开始默认第一个是最小的，然后进入内层循环，分别进行比较，一定要记录下min的下标，这是最后比较完交换的关键
        //每一次循环的目的就是找到一个最小值，然后与当前外部循环的值进行一个交换
        int min = i;
        for (int j = i + 1; j < arr.length; j++) {
          //min = Math.min(min,arr[j]);
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        //判断是否需要交换
        if (i != min) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }

    }
    return arr;
}

算法效率

必须要吐槽的是，这个直接选择排序是垃圾中的战斗机，因为它无视任何数组，干啥都是废物的O(n²)时间复杂度！！！！！！！

时间复杂度：O(n²) ；
空间复杂度：O(1) ；
稳定性：当然是不稳定的了，涉及到瞎鸡儿交换（不临近）的，就肯定不稳定的啦。

tips

没啥注意点，就是非常的垃圾，不要用…

堆排序

基本思想

这个牛逼勒，我个人最欣赏这个，因为java中的PriorityQueue用了堆排序…在做k个有序链表合并等问题时，用PriorityQueue简直就是神器啊…

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

算法描述

将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

动图演示

代码实现

     /**
     * 堆排序
     *
     * @param sortArray
     * @param len       注意这里是arr.length，跟之前不一样，堆排序是从1开始的
     */
    public static void heapSort(int[] sortArray, int len) {
        //建立大根堆
        BuildMaxHeap(sortArray, len);
        //每次都将根取出，然后将最底下的放到根，然后进行堆调整
        for (int i = len; i > 0; i--) {
            swap(sortArray, i, 0);
//            AdjustDown(sortArray,0,i-1);
            AdjustDown2(sortArray, 0, i - 1);
        }
        System.out.println(Arrays.toString(sortArray));

    }

    /**
     * 先写一个递归的，比较好理解
     *
     * @param sortArray
     * @param i
     * @param len
     */
    private static void AdjustDown(int[] sortArray, int i, int len) {
      //注意这里的len是length-1，然后根的序号是1，所以left是2i+1
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left <= len && sortArray[left] > sortArray[largest])
            largest = left;
        if (right <= len && sortArray[right] > sortArray[largest])
            largest = right;
        if (largest != i) {
            swap(sortArray, largest, i);
            AdjustDown(sortArray, largest, len);
        }

    }

    /**
     * 写一个非递归的吧，注意哈，这里的len是length-1，跟上面的一样
     *
     * @param sortArray
     * @param i
     * @param len
     */
    private static void AdjustDown2(int[] sortArray, int i, int len) {
        int t = i;
        for (int m = 2 * i + 1; m <= len; m = t * 2 + 1) {
            if (sortArray[m] > sortArray[t])
                t = m;
            if (m + 1 <= len && sortArray[m + 1] > sortArray[t])
                t = m + 1;
            if (t == i)
                break;
            else {
                swap(sortArray, t, (m - 1) / 2);
                i = (m - 1) / 2;
            }
        }
    }

    private static void BuildMaxHeap(int[] sortArray, int len) {
        double lens = len;
				//注意是从lens/2开始
        for (int i = (int) Math.round((lens / 2)) - 1; i >= 0; i--) {
//            System.out.println(i);
//            AdjustDown(sortArray,i,len);
            AdjustDown2(sortArray, i, len);
        }
    }

算法效率

时间复杂度：平均时间、最坏和最好情况下都一样，都是O(nlogn) 。
- 建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
- 调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);
- 堆排序的过程由n次第②步完成, 时间复杂度为O(nlgn)。
空间复杂度：O(1)。
稳定性：由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。

tips

堆排序，主要就是把根拿出来，然后剩下的调整成最大堆，所以第一个拿出来的最大的就应该放到最好一个位置，一共循环 n-1 次即可；
注意代码中的 len 是 length-1。
还有一个容易出错的地方在建立大根堆的时候，i 应该是从最后一个节点的父亲节点开始调整。
写的非递归还是不太好…虽然好像能通过，非递归中代码中的m是指节点的左孩子，如果有交换，切勿忘记更新新的父亲节点(i = (m-1)/2)，然后进行下一步和孩子节点的比较。

归并排序

基本思想

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用 分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。

算法描述

把长度为n的输入序列分成两个长度为n/2的子序列，然后子序列首端各维护一个指针，互相比较；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

动图演示

代码实现

    /**
     * 自己写一个 底层是数组
     */
    public static void mergeSort(int[] sortArray, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
           //注意和快排区分一下，这里的mid是要在递归里面的
            mergeSort(sortArray, low, mid);
            mergeSort(sortArray, mid + 1, high);
           //思路就是先一分为二再合二为一
            merge(sortArray, low, mid, high);
            System.out.println(Arrays.toString(sortArray));
        }
    }

    private static void merge(int[] sortArray, int low, int mid, int high) {
      	//牺牲了空间，引入了一个新的空间来存储排好序的数组
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= high) {
            if (sortArray[i] < sortArray[j]) {
                temp[k++] = sortArray[i++];
            } else {
                temp[k++] = sortArray[j++];
            }
        }
        //非常严重的错误，if中的j++后会影响下一个if，所以会超出索引值。数组越界
//        while(i > mid){
//            temp[k++] = sortArray[j++];
//        }
//        while(j > high){
//            temp[k++] = sortArray[i++];
//        }
        while (i <= mid) {
            temp[k++] = sortArray[i++];
        }
        while (j <= high) {
            temp[k++] = sortArray[j++];
        }
        for (int t = 0; t < temp.length; t++) {
          //这里也是易错点，注意sortArray的下标是从low开始的
            sortArray[low + t] = temp[t];
        }

    }

算法效率

时间复杂度：归并排序可算是排序算法中的”佼佼者”。假设数组长度为n，那么拆分数组共需logn, 又每步都是一个普通的合并子数组的过程，时间复杂度为O(n)，故其综合时间复杂度为O(nlogn)。注意，平均时间复杂度、最好时间复杂度、最坏时间复杂度都是O(nlogn)。
空间复杂度：需要一个额外的数组来存储排序好的数组，所以是O(N)。
稳定性：稳定。

tips

首先注意递归部分，跟快排有所区别，快排是排序一轮结束后才能返回中间节点，而归并是直接算出中间节点，并且归并的mid是要参与递归的，而快排中的基准值不需要参加递归。
合并过程。首先是要new一个新的数组来存储排序好的数组，两个指针轮流比较，如果底层是链表，两个头结点互相比较，最后合并之后返回一个头结点即可。
注意最后将合并排序好的数组放回到原数组时，下标是从 low 开始的。

计数排序

计数排序、基数排序、桶排序属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。

非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

基本思想

计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据。

计数排序的基本思想是：

对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数。所以可以把 arr[i] 放到它输出数组中的位置上。
假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。
其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

找出待排序的数组中最大和最小的元素；
统计数组中 arr[i] 的元素出现的次数，将 arr[i] - min 作为辅助数组helper的索引值；
对所有的计数累加，helper 索引值对应的值即为该 arr[i] 出现的次数；
反向填充目标数组：将 helper 中的元素根据索引依次放回原数组，索引对应的数值即为该数出现的次数，每放一个元素就将 helper[arr[i]-min] 减去1。

动图演示

代码实现

/**
 * 计数排序
 * 要有两个数组，分别是原数组，中间数组用来排序的
 *
 * @param sortArray
 */
public static void courtSort(int[] sortArray) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < sortArray.length; i++) {
        max = Math.max(max, sortArray[i]);
        min = Math.min(min, sortArray[i]);
    }
    int[] helparr = new int[max - min + 1];
    for (int i = 0; i < sortArray.length; i++) {
        helparr[sortArray[i] - min]++;
    }
    int index = 0;
    for (int i = 0; i < helparr.length; i++) {
        while (helparr[i]-- > 0) {
            sortArray[index++] = i + min;
        }
    }
    System.out.println(Arrays.toString(sortArray));
}

算法效率

时间复杂度：当输入元素是 n 个 0到 k 之间的整数时，平均时间、最坏和最好情况下都一样，都是O(n+k) 。其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
空间复杂度：O(n+k) 。
稳定性：稳定。

tips

注意：为了节省空间，helper 必须是 arr[i]-min作为索引值。
在将排序好的数组放回原数组时，别忘了把中间数组索引对应的值减去1，当为0时说明该索引代表的值不存在。

桶排序

基本思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort) 的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

算法描述

找出待排序数组中的最大值 max、最小值 min；
我们使用动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为 (max-min)/BucketSize+1；
遍历数组 arr，计算每个元素 arr[i] 放的桶；
每个桶各自排序；
遍历桶数组，把排序好的元素放进输出数组。

图片演示

代码实现

/**
 * 桶排序
 *
 * @param sortArray
 */
public static void BucketSort(int[] sortArray) {
    //1.设置固定数量的空桶
    int max = Integer.MIN_VALUE;
    int BucketSize = 5;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < sortArray.length; i++) {
        max = Math.max(max, sortArray[i]);
        min = Math.min(min, sortArray[i]);
    }
    int BucketCount = (max - min) / BucketSize + 1;
    //2.把数据放到对应桶中
    ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(BucketCount);
    for (int i = 0; i < BucketCount; i++) {
        buckets.add(new ArrayList<Integer>());
    }
    for (int i = 0; i < sortArray.length; i++) {
        int num = (sortArray[i] - min) / BucketSize;
        buckets.get(num).add(sortArray[i]);
    }
    //3.排序
    for (int i = 0; i < buckets.size(); i++) {
        //直接用的是集合自带的排序，可以选择插入或者递归使用桶排序
        Collections.sort(buckets.get(i));
    }

    System.out.println(buckets.toString());
 }

算法效率

时间复杂度：桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶中数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶的范围划分的越小，桶越多，各个桶之间的数据越少，排序所用的时间也会越少。所以最差的时间复杂度为 O(n²)，平均时间复杂度为 O(n+k)，最好的时间复杂度为 O(n)。
空间复杂度：O(n+k) 。
稳定性：稳定。

tips

桶最好是用ArrayList，里面的数据最好也是ArrayList装载，因为这样方便动态的添加数据到桶中。
桶内排序可以随便选择一种排序算法，这里采用的是java集成好的集合排序的方法。

基数排序

基本思想

基数排序（Radix Sort）是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

取得数组中的最大数，并取得位数；
arr 为原始数组，从最低位开始取每个位组成 radix 数组；
对 radix 进行计数排序（利用计数排序适用于小范围数的特点）；

动图演示

代码实现

/** 基数排序
  * 可以采用桶的思想，也可以采用队列的思想
  *
  * @param array
  */
 public static void radixSort(int[] array) {
     if (array == null || array.length < 2)
         return;
     // 1.先算出最大数的位数；
     int max = array[0];
     for (int i = 1; i < array.length; i++) {
         max = Math.max(max, array[i]);
     }
     int maxDigit = 0;
     while (max != 0) {
         max /= 10;
         maxDigit++;
     }
     int mod = 10, div = 1;
     //桶可以用二维数组实现，也可以用ArrayList实现，推荐列表，因为是动态的
     ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
     for (int i = 0; i < 10; i++) {
         bucketList.add(new ArrayList<Integer>());
     }
     for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
         for (int j = 0; j < array.length; j++) {
             int num = (array[j] % mod) / div;
             bucketList.get(num).add(array[j]);
         }
         int index = 0;
         for (int j = 0; j < bucketList.size(); j++) {
             for (int k = 0; k < bucketList.get(j).size(); k++) {
                 array[index++] = bucketList.get(j).get(k);
             }
             bucketList.get(j).clear();
         }
     }
     System.out.println(Arrays.toString(array));
 }

算法效率

时间复杂度：基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要 O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要 O(n)的时间复杂度。假如待排数据可以分为 d个关键字，则基数排序的时间复杂度将是 O(d*2n) ，当然 d 要远远小于 n，因此基本上还是线性级别的。最好、最差、平均时间复杂度都是O(n*k)级别的。
空间复杂度：O(n+k)，其中k为桶的数量。一般来说 n>>k，因此额外空间需要大概 n 个左右。
稳定性：稳定。

tips

注意每个桶内数据排序好然后返回给原数组后，记得clear；
点睛之笔是 将基数排序转换为计数排序，分别对其个位、十位…进行计数排序。

前言

概述

算法分类

算法复杂度

部分补充

冒泡排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

快速排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

简单插入排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

希尔排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

简单选择排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

堆排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

归并排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

计数排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

桶排序

基本思想

算法描述

图片演示

代码实现

算法效率

tips

基数排序

基本思想

算法描述

动图演示

代码实现

算法效率

tips

参考文献