package wek5;

public class Sorting {
    /**
     * Sorts the specified array of integers using the selection
     * sort algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<? super T>>
    void selectionSort(T[] data)//选择排序
    {
        int min;
        T temp;

        for (int index = 0; index < data.length - 1; index++)//控制放哪
        {
            min = index;
            for (int scan = index + 1; scan < data.length; scan++)//遍历找最小
                if (data[scan].compareTo(data[min]) < 0)
                    min = scan;

            // 交换元素;
            temp = data[min];
            data[min] = data[index];
            data[index] = temp;
        }
    }

    /**
     * Swaps to elements in an array. Used by various sorting algorithms.
     *
     * @param data   the array in which the elements are swapped
     * @param index1 the index of the first element to be swapped
     * @param index2 the index of the second element to be swapped
     */
    private static <T extends Comparable<T>>
    void swap(T[] data, int index1, int index2)//互换
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    /**
     * Sorts the specified array of objects using an insertion
     * sort algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
    void insertionSort(T[] data)//插入排序
    {
        for (int index = 1; index < data.length; index++)//下一个插入值在数组中的索引
        {
            T key = data[index];
            int position = index;

            // shift larger values to the right
            while (position > 0 && data[position - 1].compareTo(key) > 0)//当前插入值和存储在更小索引处的值进行比较，以找到应插入的位置
            {
                data[position] = data[position - 1];//把数值大的数换到了右边
                position--;//position变成左边数的索引
            }

            data[position] = key;
        }
    }

    /**
     * Sorts the specified array of objects using a bubble sort
     * algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
    void bubbleSort(T[] data)//冒泡排序
    {
        int position, scan;
        T temp;

        for (position = data.length - 1; position >= 0; position--)//n-1轮数据遍历
        {
            for (scan = 0; scan <= position - 1; scan++)//从头至尾进行扫描和比较1
            {
                if (data[scan].compareTo(data[scan + 1]) > 0)
                    swap(data, scan, scan + 1);
            }//第一个循环里面是第一次两个两个比较到列表末尾
        }//第二个循环里面是一共进行内循环的次数，其次数与列表元素个数-1相等
    }


    /**
     * Sorts the specified array of objects using the quick sort algorithm.
     *
     * @param data the array to be sorted快速排序法
     */
    public static <T extends Comparable<T>>
    void quickSort(T[] data) {
        quickSort(data, 0, data.length - 1);
    }

    /**
     * Recursively sorts a range of objects in the specified array using the
     * quick sort algorithm.
     *
     * @param data the array to be sorted
     * @param min  the minimum index in the range to be sorted
     * @param max  the maximum index in the range to be sorted
     */
    private static <T extends Comparable<T>>
    void quickSort(T[] data, int min, int max)//快速排序法
    {
        if (min < max) {
            // 创建分区
            int indexofpartition = partition(data, min, max);

            // 对左分区排序（较低的值）
            quickSort(data, min, indexofpartition - 1);//递归，创分区排序

            // 对右分区排序（较高的值）
            quickSort(data, indexofpartition + 1, max);//递归，创分区排序
        }
    }

    /**
     * Used by the quick sort algorithm to find the partition.
     *
     * @param data the array to be sorted
     * @param min  the minimum index in the range to be sorted
     * @param max  the maximum index in the range to be sorted
     */
    private static <T extends Comparable<T>>
    int partition(T[] data, int min, int max) {//快速查找法依赖于这个方法
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        // 使用中间数据值作为隔断元素
        partitionelement = data[middle];
        // 现在就把它移开
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right) {
            // search for an element that is > the partition element
            while (left < right && data[left].compareTo(partitionelement) <= 0)//用于寻找错误分区的交换元素
                left++;

            // search for an element that is < the partition element
            while (data[right].compareTo(partitionelement) > 0)
                right--;

            // swap the elements
            if (left < right)
                swap(data, left, right);
        }

        // 将分区元素移动到适当的位置
        swap(data, min, right);

        return right;
    }


    /**
     * Sorts the specified array of objects using the merge sort
     * algorithm.
     *
     * @param data the array to be sorted
     */
    public static <T extends Comparable<T>>
    void mergeSort(T[] data) {
        mergeSort(data, 0, data.length - 1);
    }

    /**
     * Recursively sorts a range of objects in the specified array using the
     * merge sort algorithm.
     *
     * @param data the array to be sorted
     * @param min  the index of the first element
     * @param max  the index of the last element
     */
    private static <T extends Comparable<T>>
    void mergeSort(T[] data, int min, int max) {//递归
        if (min < max) {
            int mid = (min + max) / 2;
            mergeSort(data, min, mid);
            mergeSort(data, mid + 1, max);
            merge(data, min, mid, max);
        }
    }

    /**
     * Merges two sorted subarrays of the specified array.
     *
     * @param data  the array to be sorted
     * @param first the beginning index of the first subarray
     * @param mid   the ending index fo the first subarray
     * @param last  the ending index of the second subarray
     */
    @SuppressWarnings("unchecked")
    private static <T extends Comparable<T>>
    void merge(T[] data, int first, int mid, int last) {
        T[] temp = (T[]) (new Comparable[data.length]);

        int first1 = first, last1 = mid;  // endpoints of first subarray第一个子数组的端点
        int first2 = mid + 1, last2 = last;  // endpoints of second subarray第二个子数组的端点
        int index = first1;  // next index open in temp array下一个索引在临时数组中打开

        //  Copy smaller item from each subarray into temp until one of the subarrays is exhausted
        //将每个子数组中的小项复制到temp中，直到其中一个子数组被耗尽
        while (first1 <= last1 && first2 <= last2) {
            if (data[first1].compareTo(data[first2]) < 0) {
                temp[index] = data[first1];
                first1++;
            } else {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }

        //从第一个子数组中复制剩余的元素，如果有的话
        while (first1 <= last1) {
            temp[index] = data[first1];
            first1++;
            index++;
        }

        //  Copy remaining elements from second subarray, if an复制第二个子数组中的剩余元素，如果有的话
        while (first2 <= last2) {
            temp[index] = data[first2];
            first2++;
            index++;
        }

        //  将合并后的数据复制到原始数组中
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }

}