
import java.util.*;

/**
 * 排序算法
 * @Author Gwl·Q
 * @ClassName SortTest
 * @Date 2020/11/6 10:39 AM
 */
public class SortTest {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 10000000; i++) {
            list.add(random.nextInt(100));
        }
        /*long bubbleSortStart = System.currentTimeMillis();
        Integer[] bubbleSort = bubbleSort(list.toArray(new Integer[list.size()]));
        long bubbleSortEnd = System.currentTimeMillis() - bubbleSortStart;
        System.out.println("冒泡排序耗时：" + bubbleSortEnd + "ms");
        System.out.println(Arrays.toString(bubbleSort) + "\n");*/

        /*long selectSortStart = System.currentTimeMillis();
        Integer[] selectSort = selectSort(list.toArray(new Integer[list.size()]));
        long selectSortEnd = System.currentTimeMillis() - selectSortStart;
        System.out.println("选择排序耗时：" + selectSortEnd + "ms");
        System.out.println(Arrays.toString(selectSort).substring(0, 100) + "\n");

        long insertSortStart = System.currentTimeMillis();
        Integer[] insertSort = insertSort(list.toArray(new Integer[list.size()]));
        long insertSortEnd = System.currentTimeMillis() - insertSortStart;
        System.out.println("插入排序耗时：" + insertSortEnd + "ms");
        System.out.println(Arrays.toString(insertSort).substring(0, 100) + "\n");

        long shellSortStart = System.currentTimeMillis();
        Integer[] shellSort = shellSort(list.toArray(new Integer[list.size()]));
        long shellSortEnd = System.currentTimeMillis() - shellSortStart;
        System.out.println("希尔排序耗时：" + shellSortEnd + "ms");
        System.out.println(Arrays.toString(shellSort).substring(0, 100) + "\n");*/

        long mergeSortStart = System.currentTimeMillis();
        Integer[] mergeSort = mergeSort(list.toArray(new Integer[list.size()]));
        long mergeSortEnd = System.currentTimeMillis() - mergeSortStart;
        System.out.println("归并排序耗时：" + mergeSortEnd + "ms");
        System.out.println(Arrays.toString(mergeSort).substring(0, 100) + "\n");

        /*long quickSortStart = System.currentTimeMillis();
        Integer[] quickSort = quickSort(list.toArray(new Integer[list.size()]), 0, list.size() - 1);
        long quickSortEnd = System.currentTimeMillis() - quickSortStart;
        System.out.println("快速排序耗时：" + quickSortEnd + "ms");
        System.out.println(Arrays.toString(quickSort).substring(0, 100)+ "\n");*/

        Integer[] countingSort = {2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2};
        long countingSortStart = System.currentTimeMillis();
        Integer[] counting = countingSortSelf(list.toArray(new Integer[list.size()]));
        long countingSortEnd = System.currentTimeMillis() - countingSortStart;
        System.out.println("耗时：" + countingSortEnd + "ms");
        System.out.println(Arrays.toString(counting).substring(0,1000));
    }
    
    /**
     * 冒泡排序  
     * @return:
     * @Date: 2020/11/6 10:41 AM
     */
    public static Integer[] bubbleSort(Integer[] array) {
        if (array == null || array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                // 如果下一个元素大于当前元素，则进行位置替换
                if (array[j + 1] < array[j]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

    /**
     * 选择排序
     * @param array
     * @return:
     * @Date: 2020/11/6 5:45 PM
     */
    public static Integer[] selectSort(Integer[] array) {
        if (array == null || array.length == 0) {
            return array;
        }
        // 每个元素逐个与其他元素做比较
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                // 以当前元素为坐标，找到小于当前数的最小的那一个，并记录
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
        return array;
    }

    /**
     * 插入排序
     * @param array
     * @return:
     * @Date: 2020/11/9 11:49 AM
     */
    public static Integer[] insertSort(Integer[] array) {
        if (array == null || array.length == 0) {
            return array;
        }
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            // 记录下一个元素值
            current = array[i + 1];
            int index = i;
            // 比较当前值是否大于下一个值
            while (index >= 0 && array[index] > current) {
                // 将当前值赋值给下一个值，并且index - 1
                array[index + 1] = array[index];
                index--;
            }
            array[index + 1] = current;
        }
        return array;
    }

    /**
     * 希尔排序
     * temp:当前索引值
     * preIndex:当前索引 - 排序因子
     * @param array
     * @return:
     * @Date: 2020/11/9 6:42 PM
     */
    public static Integer[] shellSort(Integer[] array) {
        if (array == null || array.length <= 0) {
            return array;
        }
        int gap = array.length / 2;
        while (gap > 0) {
            for (int i = gap; i < array.length; i++) {
                // 保存当前索引值
                int temp = array[i];
                // 倒推索引
                int preIndex = i - gap;
                while (preIndex >= 0 && temp < array[preIndex]) {
                    // 尝试把索引继续往前推进
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                // 如果while中的条件执行过一次，索引必须往前推进一个排序因子
                // 否则 i = preIndex + gap
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return array;
    }

    /**
     * 归并排序
     * @param array
     * @return:
     * @Date: 2020/11/10 4:25 PM
     */
    public static Integer[] mergeSort(Integer[] array) {
        if (array.length < 2) {
            return array;
        }
        int mid = array.length / 2;
        Integer[] left = Arrays.copyOfRange(array, 0, mid);
        Integer[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 归并两个序列
     * @param left
     * @param right
     * @return:
     * @Date: 2020/11/10 4:25 PM
     */
    private static Integer[] merge(Integer[] left, Integer[] right) {
        if (left.length <= 0 || right.length <= 0) {
            return new Integer[0];
        }
        Integer[] merge = new Integer[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < merge.length; index++) {
            if (i >= left.length) {
                merge[index] = right[j++];
            } else if (j >= right.length) {
                merge[index] = left[i++];
            } else if (left[i] > right[j]) {
                merge[index] = right[j++];
            } else {
                merge[index] = left[i++];
            }
        }
        return merge;
    }

    /**
     * 快速排序
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static Integer[] quickSort(Integer[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) {
            return null;
        }
        int smallIndex = partition(array, start, end);
        // 切割数组
        if (smallIndex > start) {
            quickSort(array, start, smallIndex - 1);
        }
        if (smallIndex < end) {
            quickSort(array, smallIndex + 1, end);
        }
        return array;
    }

    private static int partition(Integer[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        // 将基准值与数组最后的值进行位置替换
        swap(array, pivot, end);
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                // 可能是数组第一个元素
                if (i > smallIndex) {
                    // smallIndex类似于哨兵，所停留的位置一定是大于基准值的
                    swap(array, i, smallIndex);
                }
            }
        }
        return smallIndex;
    }

    private static void swap(Integer[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 计数排序
     * @param array
     * @return:
     * @Date: 2020/12/4 4:36 PM
     */
    public static Integer[] countingSort(Integer[] array) {
        if (array.length == 0) return array;
        int bias, min = array[0], max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        bias = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index++;
            } else {
                i++;
            }
        }
        return array;
    }

    /**
     * 自己写的计数排序
     * @param array
     * @return:
     * @Date: 2020/12/4 4:36 PM
     */
    private static Integer[] countingSortSelf(Integer[] array) {
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        Integer[] bucket = new Integer[max + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i;
                bucket[i]--;
                index++;
            } else {
                i++;
            }
        }
        return array;
    }

}









