1、递归

递归就是程序运行时调用自己，具备的条件有：

子问题必须与原问题做同样的事，且更为简单；
不能无限制地调用本身，必须有个出口结束递归；
递归的时间复杂度符合master公式，即T [n] = aT[n/b] + T (N^d)，有如下解法：
①当d<logb a时，时间复杂度为O(n^(logb a))
②当d=logb a时，时间复杂度为O((n^d)*logn)
③当d>logb a时，时间复杂度为O(n^d)

2、归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
归并排序的时间复杂度为O(n*logn),空间复杂度为O(n)，稳定排序。

    public int[] mergeSort(int[] arr,int left,int right) {
        if(left == right) {
            //只有一个数，结束递归
            return null;
        }

        //求中点
        int mid = left + (right - left)/2;

        //排序左边
        mergeSort(arr,left,mid);
        //排序右边
        mergeSort(arr,mid+1,right);

        //排序
        int[] temp = new int[right - left + 1];//临时数组
        int i=left,j=mid+1;//右边左边下标
        int k=0;//临时数组下标
        while (i<=mid && j<=right) {
            temp[k++]= arr[i]<=arr[j]? arr[i++]: arr[j++];
        }
        while (i<=mid) {
            temp[k++] = arr[i++];
        }
        while (j<=right) {
            temp[k++] = arr[j++];
        }
        //放回原数组
        i = left;
        for(j=0; j<k; j++) {
            arr[i++] = temp[j];
        }

        return arr;
    }

3、荷兰国旗问题

取一个数，将数组分为三分，左边都小于该数，中间等于该数，右边大于该数。解题如下：

//荷兰国旗问题
    public void problem(int[] arr,int num) {
        int n = arr.length;//数组长度
        int i=0,j=n-1;//下标
        int temp;

        for(int k=0; k<=j; ) {
            if(arr[k]<num) {
                //与左边界外第一个交换并下移
                temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
                i++;
                k++;
            } else if(arr[k]==num) {
                //下移
                k++;
            } else if(arr[k]>num) {
                //与右边界外第一个交换
                temp = arr[k];
                arr[k] = arr[j];
                arr[j] = temp;
                j--;
            }
        }
    }

4、快速排序

快速排序基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程：
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
(3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。

//快速排序
public void quicklySort(int[] arr,int left,int right) {
  if(left == right) {
       //只有一个数
       return;
   }

   //排序
   int i=left,j=right;//下标
   int num = arr[left];//左边值

   while (i<j) {
       //右边小于
       while (arr[j]>=num && i<j) {
           j--;
       }
       arr[i] = arr[j];

       //左边大于
       while(arr[i]<=num && i<j) {
           i++;
       }
       arr[j] = arr[i];
   }
   arr[i] = num;

   //排序左边
   quicklySort(arr,left,i);
   //排序右边
   quicklySort(arr,i+1,right);
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/106588.html