2019-07-20

import java.net.Socket;
import java.util.Arrays;
import java.util.ConcurrentModificationException;

/**
 * @ClassName SortDemo
 * @Author wangyudi
 * @Date 2019/7/20 14:44
 * @Version 1.0
 * @Description
 */
public class SortDemo {
    /**
     * 选择排序:每次选择排列一个位置
     * 注意点：数组最后一个位置不需要选择
     * 每次和最小值进行比较
     *
     * @param a
     */
    public void selectSort(Comparable[] a) {
        if (a == null) return;
        int length = a.length;
        if (a.length == 0 || a.length == 1) return;

        int min = 0;//每次选择排序中，最小数的索引值
        for (int i = 0; i < length - 1; i++) {
            min = i;//用于记录最小值所在的索引
            for (int j = i + 1; j < length; j++) {
                if (less(a[j], a[min])) min = j; //注意
            }
            exch(a, i, min);
        }
    }

    ;

    /**
     * 插入排序：将当前指针所指的元素插入到前面的排序数组中
     * 注意点：插入排序从索引为1 的元素开始插入排序
     *
     * @param arr
     */
    public void insertSort(Comparable[] arr) {
        if (arr == null) return;
        int length = arr.length;
        if (arr.length == 0 || arr.length == 1) return;
        for (int i = 1; i < length; i++) {
            for (int j = i; j > 0 && less(arr[j], arr[j - 1]); --j) {
                exch(arr, j, j - 1);
            }
        }
    }

    /**
     * 希尔排序：将数组以h为间隔分为若干个数组；解决了插入排序中，交换次数过多的情况
     * 注意点：最后一次希尔排序h为1；
     *
     * @param arr
     */
    public void hillSort(Comparable[] arr) {
        if (arr == null) return;
        int length = arr.length;
        if (arr.length == 0 || arr.length == 1) return;
        int h = 1;
        while (h < length / 3) h *= 3;
        while (h >= 1) {
            for (int i = h; i < length; i++) {
                for (int j = i; j > h - 1 && less(arr[j], arr[j - h]); j -= h) {
                    exch(arr, j, j - h);
                }
            }
            h = h / 3;
        }
    }

    /**
     * 归并排序（递归）：将数组不断地等分，然后归并；
     * 归并：将两个有序的数组归并后任然是有序数组
     * 这里使用的是非原地归并，为了避免在归并排序中平频繁地创建数组，这里初始时创建了和输入数组一样大的数组
     *
     * @param arr
     */
    public void mergeSort(Comparable[] arr) {
        if (arr == null) return;
        int length = arr.length;
        if (arr.length == 0 || arr.length == 1) return;
        Comparable[] temp = new Comparable[length]; //用于归并的辅助数组
        mergeSortCore(arr, 0, length - 1, temp);
    }

    private void mergeSortCore(Comparable[] arr, int lo, int hi, Comparable[] temp) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSortCore(arr, lo, mid, temp);
        mergeSortCore(arr, mid + 1, hi, temp);
        merge(arr, lo, mid, hi, temp);
    }

    private void merge(Comparable[] arr, int lo, int mid, int hi, Comparable[] temp) {
        for (int i = lo; i <= hi; i++) {
            temp[i] = arr[i];
        }
        int p = lo;
        int q = mid + 1;
        for (int i = lo; i <= hi; i++) {
            if (p > mid) arr[i] = temp[q++];
            else if (q > hi) arr[i] = temp[p++];
            else if (less(arr[p], arr[q])) arr[i] = temp[p];
            else arr[i] = temp[q];
        }
    }

    /**
     * 归并排序（自下而上）：从11 22 44合并数组
     */

    public void mergeSort2(Comparable[] arr) {
        if (arr == null) return;
        int length = arr.length;
        if (arr.length == 0 || arr.length == 1) return;
        Comparable[] temp = new Comparable[length];
        for (int size = 1; size < length; size *= 2) { //遍历所有长度的子数组 1，2，4，8……
            for (int i = 0; i < length - size; i = i + 2 * size) {//遍历所有需要遍历的两个子数组
                merge2(arr, i, i + size - 1, min(i + 2 * size - 1, length - 1), temp);
            }
        }
    }

    private int min(int a, int b) {
        return a < b ? a : b;
    }

    private void merge2(Comparable[] arr, int lo, int mid, int hi, Comparable[] temp) {
        for (int i = lo; i <= hi; i++) {
            temp[i] = arr[i];
        }
        int p = lo;
        int q = mid + 1;
        for (int i = lo; i <= hi; i++) {
            if (p > mid) arr[i] = temp[q++];
            else if (q > hi) arr[i] = temp[p++];
            else if (less(arr[p], arr[q])) arr[i] = temp[p];
            else arr[i] = temp[q];
        }
    }

    /**
     * 快速排序：选择排序数组中的一个数，然后对其进行分割
     */
    public void quickSort(Comparable[] arr) {
        if (arr == null) return;
        int length = arr.length;
        if (arr.length == 0 || arr.length == 1) return;
        quickSortCore(arr, 0, length - 1);
    }

    public void quickSortCore(Comparable[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int mid = partition(arr, lo, hi);
        quickSortCore(arr, lo, mid - 1);
        quickSortCore(arr, mid + 1, hi);
    }

    /**
     * 将数组切分，并返回切分比较值所在的索引
     *
     * @param arr
     * @param lo
     * @param hi
     * @return
     */
    private int partition(Comparable[] arr, int lo, int hi) {
        Comparable v = arr[lo];
        int i = lo;
        int j = hi + 1;
        while (true) {
            //i指向数组范围内比基准数大的值，或者数组最后一个元素
            //j指向数组范围内比基准数小的值，或者数组第一个元素
            while (arr[++i].compareTo(v) <= 0) if (i == hi) break;
            while (arr[--j].compareTo(v) >= 0) if (j == lo) break;
            if (i >= j) break;
            exch(arr, i, j);
        }
        exch(arr, lo, j);
        return j;
    }


    /**
     * 三向切分 快速排序方法：适用于数组中有大量相同元素的排序算法
     * 将数组分为 小于 等于 大于三部分
     * partition3Way 需要两个指针和遍历指针
     */
    public void quickSort3Way(Comparable[] arr) {
        if (arr == null) return;
        int length = arr.length;
        if (arr.length == 0 || arr.length == 1) return;
        quickSort3WayCore(arr, 0, length - 1);
    }

    private void quickSort3WayCore(Comparable[] arr, int lo, int hi) {
        if (lo >= hi) return;
        int[] result = partition3Way(arr, lo, hi);
        quickSort3WayCore(arr, lo, result[0] - 1);
        quickSort3WayCore(arr, result[1] + 1, hi);

    }

    private int[] partition3Way(Comparable[] arr, int lo, int hi) {
        int lp = lo;//指向小于部分尾部
        int gp = hi;//指向大于部分头部
        Comparable value = arr[lo];
        int i=lo+1;
        while(i<=gp) { //i是用于遍历数组来切分的指针变量
            int cmp = arr[i].compareTo(value);
            if (cmp > 0) {//arr[i]比较大
                exch(arr, i, gp--);
            } else if (cmp < 0) {
                exch(arr, lp++, i++); //注意，这里会调节数组
            }
        }
        int[] result = new int[]{lp, gp};
        return result;
    }

    /**
     * 堆排序：用一个数组实现最大堆（最大优先队列）
     * 注意点：保存数据的第一个索引没有使用
     * 这里实现的堆排序中，使用了数组的第一个元素 k 2k+1 2k+2
     *
     * @param arr
     */
    public void heapSort(Comparable[] arr) {
        if (arr == null) return;
        int length = arr.length;
        if (arr.length == 0 || arr.length == 1) return;
        //堆有序化， 从倒数第二排开始 sink
        for (int i = (length - 1) / 2; i >= 0; i--) {
            sink(arr, i, length - 1);
        }
        //排序，将堆顶最大的数交换到数组的末尾，然后堆顶数据sink
        int last = length - 1;
        while(last!=0){
            exch(arr,0,last--);
            sink(arr,0,last);
        }
    }

    private void sink(Comparable[] arr, int k, int last) {
        while ((2 * k + 1) <= last) { //有子节点
            int j = 2 * k + 1;
            if ((j + 1) <= last) if (arr[j].compareTo(arr[j + 1]) < 0) j += 1; //去子节点中的较大者
            if (arr[k].compareTo(arr[j]) >= 0) break;
            exch(arr, k, j);
            k = j; //替换比较对象索引
        }
    }

    /**
     * 交换
     *
     * @param a
     * @param i
     * @param j
     */
    public static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * 比较
     *
     * @param a
     * @param b
     * @return
     */
    public static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 显示当前数组
     *
     * @param a
     */
    public static void show(Comparable[] a) {
        System.out.println(Arrays.toString(a));
    }

    /**
     * 判断数组是否有序
     *
     * @param a
     * @return
     */
    public static boolean isSorted(Comparable[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i].compareTo(a[i + 1]) > 0) {
                System.out.println("false");
                return false;
            }
        }
        System.out.println("true");
        return true;
    }
}


class TestCase {
    public static void main(String[] args) {
        SortDemo sortDemo = new SortDemo();
        Integer[] a = new Integer[]{34, 2, 5, 4, 45, 6, 22};
//        sortDemo.selectSort(a);
//        SortDemo.isSorted(a);

//        sortDemo.insertSort(a);
//        SortDemo.isSorted(a);

//        sortDemo.mergeSort(a);
//        SortDemo.isSorted(a);

//        sortDemo.mergeSort2(a);
//        SortDemo.isSorted(a);

//        sortDemo.quickSort(a);
//        SortDemo.isSorted(a);

//        sortDemo.quickSort3Way(a);
//        SortDemo.isSorted(a);

//        sortDemo.heapSort(a);
//        SortDemo.isSorted(a);
    }
}