一、排序算法

常见的几类排序算法：
冒泡、选择、插入
快排、归并
桶、基数

二、考虑的因素

最好、最坏、平均时间复杂度。数据的有序度不同，对于排序算法有很大的区别。需要知道排序算法在不同数据下的性能表现。
时间复杂度的系数、常熟、低阶。因为排序算法对性能要求比较高，而它们的效率相差需要更细地考虑。并且在小规模数据时，在对比同一阶时间复杂度的排序算法性能对比时，要把系数、常数、低阶也考虑进来。
比较和交换的次数。
是否未原地排序：内存的消耗。即空间复杂度为O（1）为原地排序。
排序的稳定性：相同值的数据，排序前后相对顺序不变，即稳定

三、O(nlogn)的排序

归并

最好、最坏、平均都是O(nlogn)。不是原地排序，稳定。空间复杂度因为每次合并都创建数组，但合并完成后都释放了空间，为O（n）。

public class 归并排序 {

    public int[] mergeSort(int[] arr) {
        if (arr.length < 2) {
            return arr;
        }
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    public int[] merge(int[] left, int[] right) {
        //创建一个新数组，长度为两个有序数组的长度之和
        int[] newArray = new int[left.length + right.length];

        //定义两个指针，分别代表两个数组的下标
        int lindex = 0;
        int rindex = 0;
        for (int i = 0; i < newArray.length; i++) {
            //左边数组已经排好序
            if (lindex >= left.length) {
                newArray[i] = right[rindex++];
                //右边数组已经排好序
            } else if (rindex >= right.length) {
                newArray[i] = right[rindex++];
                //左边数组的元素更小
            } else if (left[lindex] < right[rindex]) {
                newArray[i] = left[lindex++];
                //右边数组的元素更小
            } else {
                newArray[i] = right[rindex++];
            }
        }
        return newArray;
    }
}

快排

最好为nlogn，最坏-接近有序或有序时- O(n2)（可以通过合理选择pivot避免这种情况）,原地排序，不稳定。
递推公式和递归shutdow树可以分析递归的时间复杂度

例子：求数组中第k大的数。

解：选择最后一个数作为pivot，将数组分成三部分，A[0…p-1],A[p],A[p+1…n-1]; 如果p+1=k，则A[p]就是要求的元素，如果k大于，就在右边找，小于在左边找。

第一次分区对大小为n进行分区操作，第二次对n/2的数组分区，依次执行。
代码：

/**
 * @Author:Tsx
 * @Date:2021-07-15- 10:59
 */
public class 快排 {
    public void quickSort(int[] arr, int begin, int end) {
        //判断递归截止条件
        if(arr.length <=1 || begin >=end){
            return;
        }
        //进行分区 得到分区下标
        int pivotIndex = partition(arr,begin,end);
        //对分区左侧进行快排
        quickSort(arr,begin,pivotIndex-1);
        //对分区右侧进行快排
        quickSort(arr,pivotIndex+1,end);
    }

    /**
     * 分区函数
     * @param arr
     * @param begin
     * @param end
     * @return
     */
    private int partition(int[] arr, int begin, int end) {
        //默认数组中待分区区间的最后一个是pivot元素  当然也可以随机指定pivot元素
        int  pivot = arr[end];
        //定义分区后pivot元素的下标
        int pivotIndex = begin;
        for(int i= begin;i< end;i++){
            //判断如果该区间内如果有元素小于pivot则将该元素从区间头开始一直向后填充 有点类似选择排序
            if(arr[i] < pivot){

                if(i>pivotIndex){
                    swap(arr,i,pivotIndex);
                }
                pivotIndex++;
            }
        }
        swap(arr,pivotIndex,end);
        return pivotIndex;
    }

    /**
     * 交换数组内下标为i j的两个元素
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr,int i,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    /**
     * 测试快排
     */
    @Test
    public void testQuickSort(){
        //准备一个int数组
        int[] array = new int[7];
        array[0] = 5;
        array[1] = 2;
        array[2] = 6;
        array[3] = 9;
        array[4] = 0;
        array[5] = 3;
        array[6] = 4;
        //进行排序
        System.out.println(Arrays.toString(array));
        quickSort(array,0,array.length-1);
        //输出排序结果
        System.out.println(Arrays.toString(array));
    }
}

四、O(n)的排序

桶排序

要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。
最好情况是，n个数据分成m个桶，m接近于n。
最坏：数据都被分到一个桶里，退化为O（nlogn）

例子：10G订单数据按照订单金额排序。内存有限没法将所有数据都装进能内存。

/**
 * @Author:Tsx
 * @Date:2021-07-15- 14:48
 */
public class 桶排序 {

    /**
     * 桶排序
     *
     * @param array      待排序集合
     * @param bucketSize 桶中元素类型的个数，即每个桶所能放置多少个不同数值。
     *                   例如：当bucketSize=5时，该桶可以存放{1,2,3,4,5}这几种数字，但是容量不限，
     *                   即可以存放100个3
     * @return 排好序后的集合
     */
    public static List<Integer> bucketSort(List<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2 || bucketSize < 1) {
            return array;
        }
        //找出集合中元素的最大值,最小值
        int max = array.get(0);
        int min = array.get(0);
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max) {
                max = array.get(i);
            }
            if (array.get(i) < min) {
                min = array.get(i);
            }
        }
        //计算桶的个数   最大值-最小值代表了集合中元素取值范围区间
        int bucketCount = (max - min) / bucketSize + 1;
        //按序创建桶,创建一个List,List带下标是有序的,List中的每一个元素是一个桶,也用List表示
        List<List<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        //将待排序的集合依次添加到对应的桶中
        for (int j = 0; j < array.size(); j++) {
            int bucketIndex = (array.get(j) - min) / bucketSize;
            bucketList.get(bucketIndex).add(array.get(j));
        }
        //对每一个桶中的数据进行排序(可以使用别的排序方式),然后再将桶中的数据依次取出存放到一个最终的集合中
        //创建最终的集合
        List<Integer> resultList = new ArrayList<>();
        for (int j = 0; j < bucketList.size(); j++) {

            List<Integer> everyBucket = bucketList.get(j);
            //如果桶内有元素
            if (everyBucket.size() > 0) {

                //递归的使用桶排序为每一个桶进行排序
                //当某次桶排序待排序集合都分配到一个桶中时,缩小桶的范围以获得更多的桶
                if (bucketCount == 1) {
                    bucketSize--;
                }
                List<Integer> temp = bucketSort(everyBucket, bucketSize);
                for (int i = 0; i < temp.size(); i++) {
                    resultList.add(temp.get(i));
                }
            }
        }
        return resultList;
    }

    @Test
    public void testBucketSort() {
        List<Integer> list = new ArrayList<>();
        list.add(5);
        list.add(2);
        list.add(2);
        list.add(6);
        list.add(9);
        list.add(0);
        list.add(3);
        list.add(4);
        System.out.println(list);
        List<Integer> bucketSort = bucketSort(list, 2);
        System.out.println(bucketSort);
    }

}

计数排序

要排序的n个数据，所处的范围并不大。比如最大值是k，可以将数据分成k个桶，每个桶的数据值都是相同的，省掉了桶内排序。

要求：只能给非负整数排序。负数就+正数，小数就变整数

例子：50万考生的排名

基数排序

例子：十万个手机号码从小到大排序

要求：数据能分割出独立的位，位之间有递进关系，如果a数据的高位比b数据大，那剩下的地位就不用比较了。此外，每一位的数据范围不能太大，要可以用线性排序算法来排序。否则就不是O（n）了。

优化

快排优化

分区点选择：1.三数取中法 2.随机法

快速排序是用递归来实现的。我们在递归那一节讲过，递归要警惕堆栈溢出。为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决办法：第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制