排序API

1. Arrays类中的静态排序API

**Arrays.sort(数据类型[] a)中的排序是用的是快速排序，时间复杂度是O(nlogn)

对指定的类型数组按数字升序进行排序。不稳定

Arrays.sort(T[],Comparator<? super T> c) 、Arrays.sort(Object[] a)

根据指定比较器产生的顺序对指定对象数组进行排序，当c=null时按自然序排列

该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n*log(n) 性能。稳定

2. Collections静态排序API

Collections.sort(List list)、和Collections.sort(List list，Comparator<？super T> c);

使用的排序是稳定的，主要是对list排序

该排序算法是一个经过修改的合并排序算法（其中，如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并）。此算法提供可保证的 n log(n) 性能。
此实现将指定列表转储到一个数组中，并对数组进行排序，在重置数组中相应位置处每个元素的列表上进行迭代。这避免了由于试图原地对链接列表进行排序而产生的
n2 log(n) 性能。

3. ArrayList的排序API

list.sort(Comparator<? super T> c);对list排序，当c=null时，按自然序排列

1，对list排序，可以使用list自己的sort方法，也可以使用Collections的静态排序方法，且Collections的排序方法都是稳定的

2，Arrays的静态sort，一个是快排，一个归并排序（稳定的）

补充：常见的排序方法

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出

算法思想

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

在这里插入图片描述

①以第一个关键字 K 1 为控制字，将 [K 1 ,K 2 ,…,K n ] 分成两个子区，使左区所有关键字小于等于 K 1 ，右区所有关键字大于等于 K 1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。
②把左区作为一个整体，用①的步骤进行处理，右区进行相同的处理。（即递归）
③重复第①、②步，直到左区处理完毕。

static void quicksort(int n[],int left,int right) {
        int dp;
        if (left < right) {
            dp = partition(n, left, right);
            quicksort(n, left, dp -1);
            quicksort(n, dp +1, right);
        }
    }
 
    static int partition(int n[],int left,int right) {
        int pivot = n[left];
        while (left < right) {
            while (left < right && n[right] >= pivot)
                right--;
            if (left < right)
                n[left++] = n[right];
            while (left < right && n[left] <= pivot)
                left++;
            if (left < right)
                n[right--] = n[left];
        }
        n[left] = pivot;
        return left;
    }

归并排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

在这里插入图片描述

public static int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }
     
    public static void merge(int[] a,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(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }