1. 冒泡/选择/插入

2. 计数排序

算法思想：
用空间换时间，并不是基于元素的比较，而是利用数组的索引确定元素的位置
统计每个元素的个数sum，将sum放入与元素相同的下标位置处
数组中元素处于一个区间内，创建一个length等于max-min+1的数组
算法原理：

找出数组nums中最大值max和最小值min，创建一个新数组arr[max-min+1]
遍历数组中第i个元素nums[i]，将nums[i]与arr的下标相同的位置处arr[nums[i]-min] += 1
将原数组修改为排序后的数组

代码实现：

/*
	计数排序
*/
public  void countSort(int[] nums){
        //1.获取数组最大/小值
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();
        //2.创建新数组
        int[] arr = new int[max-min+1];
        //3.遍历元素个数,将个数填入与元素对应的下标处
        // 找到元素与索引对应的位置,让索引处的值+1
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]-min] += 1;
        }
        //4.填充目标数组
        int curIndex = 0;//记录遍历填充数组的索引
        for (int i = 0; i< arr.length; i++) {
            while (arr[i]>0){
            	//原数组元素-min = 存储索引  原数组元素 = 存储索引 + min
                nums[curIndex++] = i+min;
                arr[i]--;
            }
        }
    }

3. 快速排序

算法思想：
从数组中找一个基准值 v，使得每次排序后的数组中比v小的都在v的左边，比v大的都在v的右边
放好 v 的位置后，再对左边分区or右边分区排序

算法原理：

选取一个元素作为基准值。可以使用random随即获取一个元素作为基准值，防止在数组偏向顺序or逆序时快排性能退化
将大于等于 v 的元素放到 v 的右边，小于 v 的放在 v 的左边，一次操作称为分区
每次分区后，分别递归地对两边的区域进行分区，直到排序完成

代码实现：

	/**
     * 快速排序
     * @param nums 目标数组
     */
    public void quickSort(int[] nums){
        quickSort(nums, 0, nums.length-1);
    }

    /**
     * 快速排序
     * @param nums 目标数组
     * @param left 左边界
     * @param right 右边界
     */
    private   void quickSort(int[] nums, int left, int right) {
        //递归终止条件
        if(left>=right){
            return;
        }

        //随机化基准值,防止遇顺序或逆序数组性能退化
        int ran = left +1 + random.nextInt(right-left);
        swap(nums,left,ran);

        //递归操作
        int val = nums[left];//找一个基准值
        int i = left + 1; //当前操作元素的索引
        int j = left; //指向 小于V 的最后一个元素的索引
        for (; i <= right; i++) {
            if(nums[i]<val){
                swap(nums,i,++j);
            }
        }
        if(j!=left){
            swap(nums,j, left);
        }
        // 递归调用
        quickSort(nums, left, j - 1);
        quickSort(nums, j + 1, right);
    }
    
    //交换数组中的两个元素
	private  void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

4. 双路快排

单路快排是将=v的元素放在左侧or右侧
数组中有大量重复元素时,会导致左右两侧元素数量不平衡,性能下降
如图所示:

双路快排的思想是将等于v 的元素平均分配在两侧
步骤:

建立索引
left 左边界,
right 右边界
i 判断所指元素是否< V
j 判断所指元素是否> V
选取随机元素作为基准值
遍历数组
循环若 i 所指元素 < v，指针后移（当i>right 结束）
循环若 j 所指元素 > v，指针前移（当j<left+1 结束）
两次循环结束,交换i,j位置的元素, i++; j–
当 i 与 j 重合后,结束本次排序, j所指位置就是=v的,直接与nums[left]交换
递归调用

代码实现:

/**
* 双路快排
* @param nums 目标数组
*/
public void sort2Ways(int[] nums){
   if (nums == null || nums.length == 0) {
       throw new IllegalArgumentException("nums is empty");
   }
   sort2Way(nums, 0, nums.length - 1);
}

private void sort2Way(int[] nums, int left, int right) {
   //递归到底
   if (left >= right) {
       return;
   }

   //随机化基准值,防止遇顺序或逆序数组性能退化
   int ran = left + 1 + random.nextInt(right - left);
   swap(nums, left, ran);

   //选取基准值
   int v = nums[left];
   //创建辅助索引
   int i = left + 1;//比较当前元素是否 < v
   int j = right;   //比较当前元素是否 > v
   while (true){
       //若 i 所指元素 < v,将i后移,当 nums[i] >v && i>right时结束遍历
       while (nums[i]<v && i<=right){
           i++;
       }
       //若 j 所指元素 > v,将j后移,当nums[j]<v && j<left+1时结束遍历
       while (nums[j]>v && j>=left+1){
           j--;
       }
       if(i>j){
           break;
       }
       //将左边的大值与右边的小值交换
       swap(nums,i,j);
       //交换完,指针后移,继续遍历
       i++;
       j--;
   }
   //找到基准值的位置-->每次交换完后j所指的位置
   swap(nums, left, j);
   //对分区分别排序
   sort2Way(nums, left, j-1);
   sort2Way(nums, j+1, right);
}


private void swap(int[] arr, int a, int b) {
   int temp = arr[a];
   arr[a] = arr[b];
   arr[b] = temp;
}

5. 三路快排

重复元素越多,三路快排效率越高
算法思想：
将数组分为 <V 、=V、 >V 三个部分

在遍历完成后，将数组划分为3个部分，对<V 、>V的部分递归调用三路快排
算法原理：

建立辅助索引
lt 小于V的最后一个元素索引（lt是<v和=v的分界）
gt 大于V的第一个元素索引 (gt是>v和=v的分界）
i 当前遍历的索引
```
//操作元素
int i = left + 1; 
//小于val的最后一个元素  注意: lt不能使用left-1,否则会在第一次交换时出问题
int lt = left;  
//大于val的第一个元素,    虚拟位置,初始并没有大于val的区域
int gt = right + 1;
```
遍历数组
1. 若当前 i 所指元素等于 V ,直接跳过.
```
i++;
```
2. 若当前 i 所指元素小于 V, 将该元素与 ==v 部分的第一个元素做交换.lt指针后移 ,i 前移
```
swap(nums, i, lt + 1);
lt++;
i++;
```
3. 若当前 i 所指元素大于 V ,将该元素与 >V 区域第一个元素的前一个元素(nums[gt-1])做交换.
注意:此时 i 不用++ ,因为是和 gt-1 处换过来的元素,还没有遍历过
```
swap(nums, i, gt - 1);
gt--;
```
4. 当 i 与 gt 重合时,遍历结束

此时将left处的V与 lt 所指的元素交换,就完成了一轮排序.

5. 之后对 >V 和 <V 的部分递归调用三路排序的方法,==V 部分的第一次就排好了.

代码实现：

	/**
     * 三路快排
     * @param nums array
     */
    public void sort3Ways(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("nums is empty");
        }
        sort3Way(nums, 0, nums.length - 1);
    }

    /**
     * 三路快排递归方法
     * @param left  左边界
     * @param right 右边界
     * @nums array
     */
    private void sort3Way(int[] nums, int left, int right) {
        //递归到底
        if (left >= right) {
            return;
        }

        //随机化基准值,防止遇顺序或逆序数组性能退化
        int ran = left + 1 + random.nextInt(right - left);
        swap(nums, left, ran);

        //递归操作
        int val = nums[left]; //基准元素
        int i = left + 1; //操作元素
        int lt = left;   //小于val的最后一个元素  注意: lt不能使用left-1,否则会在第一次交换时出问题
        int gt = right + 1;//大于val的第一个元素,    虚拟位置,初始并没有大于val的区域
        //i<=right  nums.length-1=right
        for (; i <= right && i < gt; i++) {
            int curElem = nums[i];
            if (curElem == val) {
                //1.若当前元素 = 基准元素val,指针后移
                continue;
            } else if (curElem < val) {
                //2.当前元素 < 基准元素
                swap(nums, i, lt + 1);
                lt++;
            } else {
                //3.当前元素 > 基准元素
                swap(nums, i, gt - 1);
                gt--;
                //i指向的是交换后的未遍历的元素,不用++
                i--;
            }
        }
        swap(nums, left, lt);
        sort3Way(nums, left, lt - 1);
        sort3Way(nums, gt, right);
    }

    private void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }