排序

排序的稳定性：

假设Ki=Kj，且在排序前的序列中ri领先于rj（即i<j）。如果排序后i<j，则称所用的排序方法是稳定的。如果前后顺序顺序发生变化，则称所用的排序方法不是稳定的。

原地排序：

基本上不需要额外辅助的的空间,允许少量额外的辅助变量进行的排序。就是在原来的排序数组中比较和交换的排序。

———————————————————冒泡排序———————————————————

一种交换排序。基本思想是：两两比较相邻记录关键字，如果反序则交换，直到没有反序的记录为止。元素交换的次数等于原始数据的逆序度。时间复杂度O(n*2) 原地排序、稳定

    public static int[] bubbleSort(int[] data) {
        for (int i = 0; i < data.length; i++) {

            //data.length-i-1--->i次循环已有i个数据排序完成（i从0开始）。排序完成的数据不需要继续比较
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }

        return data;
    }

优化版冒泡排序：

    public static int[] bubbleSort(int[] data) {

        for (int i = 0; i < data.length; i++) {
            //增加标识未，是否发送交换。
            boolean swap = false;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    swap = true;
                }

            }

            //未发生交换，表明数据已经有序。
            if(!swap){
                break;
            }

        }

        return data;
    }

———————————————————插入排序———————————————————

将一个记录插入到已经排序号的有序表中，从而得到一个新的，记录数增1的有序表。时间复杂度：O(n*2) 原地排序、稳定

public static int[] insertSort(int[] data) {

        int j;
        int temp;
        for (int i = 1; i < data.length; i++) {

            j = i;

            //哨兵左右，作比较使用
            temp = data[i];

            while (j > 0 && data[j - 1] > temp) {
                data[j] = data[j - 1];
                j--;
            }

            //找到当前要插入的元素
            data[j] = temp;

        }

        return data;
    }

———————————————————选择排序———————————————————

通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换。O(n*2) 原地排序、不稳定

    public static int[] selectSort(int[] data) {

        int min;
        for (int i = 0; i < data.length -1; i++) {
            min = i;

            for (int j = i + 1; j < data.length; j++) {

                //选择出最小的值
                if (data[min] > data[j]) {
                    min = j;
                }

            }

            //如果当前不是最小的值，交换
            if (i != min) {

                int temp = data[i];
                data[i] = data[min];
                data[min] = temp;
            }
        }

        return data;

    }

———————————————————希尔排序———————————————————

先将整个待排记录序列分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录'基本有序'，再对全体记录进行一次直接插入排序。最后一次分割’增量‘一定要是1。O(n*2) 原地排序、不稳定

 public static int[] shellSort(int[] data) {
        int d = data.length / 2;
        int j;
        int temp;
        while (d >= 1) {
            //从d开始，减少遍历次数
            for (int i = d; i < data.length; i++) {
                j = i - d;
                temp = data[i];
                //前面的数据大于后面的，将前面的数据放置在后面，类似直接插入排序
                while (j >= 0 && data[j] > temp) {
                    data[j + d] = data[j];
                    j = j - d;
                }
                data[j + d] = temp;
            }
            //间隔数据为原来1/2
            d = d / 2;
        }
        return data;
    }

———————————————————归并排序———————————————————

利用归并思想排序的方法。假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列....如此重复，知道得到一个长度为n的有序序列为止，这样的排序方法称为2路归并排序。O(n*logn) 非原地排序、稳定

递归实现：

    public static void mergeSort(int[] a, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(a, start, mid);
            mergeSort(a, mid + 1, end);
            merge(a, start, mid, end);
        }
    }
   public static void merge(int[] a, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int p1 = left, p2 = mid + 1, k = 0;

        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                tmp[k++] = a[p1++];
            } else {
                tmp[k++] = a[p2++];
            }
        }


        while (p1 <= mid) {
            tmp[k++] = a[p1++];
        }

        while (p2 <= right) {
            tmp[k++] = a[p2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            a[left + i] = tmp[i];
        }
    }

非递归实现：

public static void mergeSort2(int[] arr) {
        int len = arr.length;
        int k = 1;

        //以2的倍数，
        while (k < len) {
            mergePass(arr, k, len);
            k *= 2;
        }
    }

    public static void mergePass(int[] arr, int k, int n) {
        int i = 0;
        //从前往后,将2个长度为k的子序列合并为1个
        while (i < n - 2 * k + 1) {
            merge(arr, i, i + k - 1, i + 2 * k - 1);
            i += 2 * k;
        }

        //在最后一次k的数据中，不满足while循环，剩余最后几个数据。合并到数组中
        if (i < n - k) {
            merge(arr, i, i + k - 1, n - 1);
        }

    }
   public static void merge(int[] a, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int p1 = left, p2 = mid + 1, k = 0;

        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                tmp[k++] = a[p1++];
            } else {
                tmp[k++] = a[p2++];
            }
        }


        while (p1 <= mid) {
            tmp[k++] = a[p1++];
        }

        while (p2 <= right) {
            tmp[k++] = a[p2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            a[left + i] = tmp[i];
        }
    }

———————————————————快速排序———————————————————

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。O(n*logn) 原地排序、不稳定

 public static void quickSort(int[] data, int low, int high) {

        if (low < high) {
            //选择枢轴
            int partitionIndex = partition(data, low, high);

            //枢轴不在再次排序之内，枢轴左右的数据进行排序
            quickSort(data, low, partitionIndex - 1);
            quickSort(data, partitionIndex + 1, high);
        }

    }
public static int partition(int[] data, int low, int high) {
        int pivotKey = data[low];
        while (low < high) {
            while (low < high && data[high] >= pivotKey) {
                high--;
            }

            data[low] = data[high];

            while (low < high && data[low] <= pivotKey) {
                low++;
            }

            data[high] = data[low];

        }

        data[low] = pivotKey;

        return low;

    }

———————————————————堆排序———————————————————

堆是具有下列性质的完全二叉树：
每个节点的值都大于或等于其左右孩子结点的值，成为大顶堆；
每个节点的值都小于或等于其孩子结点，称为小顶堆。
将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构成成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列。O(n*logn) 原地排序、不稳定

大顶堆排序：

    public static int[] heapSort(int[] data) {

        //从有孩子节点的双亲进行调整
        for (int i = data.length / 2 - 1; i >= 0; i--) {
            bigHeapAdjust(data, i, data.length);
        }

        for (int i = data.length - 1; i > 0; i--) {
            //将堆顶元素换到数组末尾，末尾元素不再参与堆的调整
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;

            bigHeapAdjust(data, 0, i);
        }

        return data;
    }


    public static void bigHeapAdjust(int[] data, int index, int length) {

        //从该结点的左子结点开始，也就是2i+1处开始
        int temp = data[index];
        for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {

            if (i + 1 < length && data[i] < data[i + 1]) {
                //左孩子节点小于右孩子节点，指向右孩子
                i++;
            }

            //如果该结点比最大的孩子节点大，退出
            if (temp >= data[i]) {
                break;
            }

            //将最大的孩子结点的值赋值给该结点
            data[index] = data[i];
            index = i;
        }

        data[index] = temp;
    }

小顶堆排序：

    public static int[] heapSort(int[] data) {

        //从有孩子节点的双亲进行调整
        for (int i = data.length / 2 - 1; i >= 0; i--) {
            smallHeapAdjust(data, i, data.length);
        }

        for (int i = data.length - 1; i > 0; i--) {
            //将堆顶元素换到数组末尾，末尾元素不再参与堆的调整
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;

            smallHeapAdjust(data, 0, i);
        }

        return data;
    }
 public static void smallHeapAdjust(int[] data, int index, int length) {

        //从该结点的左子结点开始，也就是2i+1处开始
        int temp = data[index];
        for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {

            if (i + 1 < length && data[i] > data[i + 1]) {
                //左孩子节点大于右孩子节点，指向右孩子
                i++;
            }

            //如果该结点比最大的孩子节点大，退出
            if (temp < data[i]) {
                break;
            }

            //将最大的孩子结点的值赋值给该结点
            data[index] = data[i];
            index = i;
        }

        data[index] = temp;
    }

———————————————————计数排序———————————————————

计数排序是一种非比较性质的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作，根据元素本身的值，将每个元素出现的次数记录到辅助空间后，通过对辅助空间内数据的计算，即可确定每一个元素最终的位置。

    public static int[] countingSort(int[] a) {
        //获取数组元素最大值
        int k = max(a);

        //初始化a的数据值，a对应位置上，存储着data数据对应的值
        //例如data[1] =5,则c[5]=1;5出现一次
        int[] c = new int[k + 1];
        for (int i = 0; i < a.length; i++) {
            c[a[i]] = c[a[i]] + 1;
        }

        //将C数组元素值累加
        for (int i = 1; i < k + 1; i++) {
            c[i] = c[i] + c[i - 1];
        }

        //b数组存储排序后数组
        int[] b = new int[a.length];
        for (int i = a.length - 1; i >= 0; i--) {
            b[c[a[i]] - 1] = a[i];
            c[a[i]] = c[a[i]] - 1;
        }

        return b;
    }

    public static int max(int[] data){
        int max = 0;
        for (int i = 0; i < data.length; i++) {
            if(data[i] >max){
                max = data[i];
            }
        }
        return max;
    }

———————————————————基数排序———————————————————

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

     public static int[] radixSort(int[] data) {
        int max = BaseSort.max(data);

        //从低位--->个位开始比较
        int size = 10;
        for (int exp = 1; max / exp > 0; exp *= size) {
            //内部排序使用计数排序

            int[] c = new int[size];

            for (int i = 0; i < data.length; i++) {
                //取模
                c[data[i] / exp % size] += 1;
            }

            for (int i = 1; i < c.length ; i++) {
                c[i] = c[i] + c[i - 1];
            }

            int[] b = new int[data.length];
            //从后向前，保持稳定
            for (int i = data.length -1; i >=0; i--) {
                b[c[data[i] / exp % size] - 1] = data[i];
                c[data[i] / exp % size]--;

            }

            System.arraycopy(b, 0,data,0,data.length);

        }

        return data;
    }
    public static int max(int[] data){
        int max = 0;
        for (int i = 0; i < data.length; i++) {
            if(data[i] >max){
                max = data[i];
            }
        }
        return max;
    }

———————————————————桶排序———————————————————

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

    public static void main(String[] args) {
        int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156,
            194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109};

    }

    public static int[] bucketSort(int[] data) {


        List<LinkedList<Integer>> buckets = new ArrayList<>();
        int size = 3;
        for (int i = 0; i < size; i++) {
            buckets.add(new LinkedList<>());
        }

        for (int f : data) {
            //根据长度分桶
            int index = bucketIndex(f);
            insertSort(buckets.get(index - 1), f);
        }

        int i = 0;
        for (LinkedList<Integer> linkedList : buckets) {
            for (Integer integer : linkedList) {
                data[i++] = integer;
            }
        }

        return data;
    }



    public static int bucketIndex(Integer f) {
        return f.toString().length();
    }

    public static void insertSort(LinkedList<Integer> linkedList, int f) {

        ListIterator<Integer> integerIterator = linkedList.listIterator();
        Boolean flag = false;
        while (integerIterator.hasNext()) {
            if (f <= integerIterator.next()) {
                integerIterator.previous();
                integerIterator.add(f);
                flag = true;
                break;
            }
        }

        if (!flag) {
            linkedList.add(f);
        }

    }