package top.xudj.sf;


import java.util.Arrays;

/**
 * description 排序算法，正序
 * 参考：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
 *
 * @author xudj
 * @version 1.0
 * @date 2021-10-27 15:23
 **/
public class SortAlgorithm {


    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 4, 7, 5, 6, 10, 2};
        // 冒泡排序 时间：O(n^2) | 空间：O(1)
//        int[] sortArr = bubbleSort(arr);

        // 选择排序 时间：O(n^2) | 空间：O(1)
//        int[] sortArr = selectionSort(arr);

        // 插入排序 时间：O(n^2) | 空间：O(1)
//        int[] sortArr = insertSort(arr);

        // 希尔排序 时间：O(n*log n) | 空间：O(1)
//        int[] sortArr = shellSort(arr);

        // 归并排序 时间：O(n*log n) | 空间：O(n)
//        int[] sortArr = mergeSort(arr);

        // 快排 时间：O(n*log n) ｜ 空间：O(n)
//        int[] sortArr = quickSort(arr);
        int[] sortArr = quickSort2(arr);

        // 展示
        Arrays.stream(sortArr).forEach(i -> {
            System.out.print(i + " ");
        });
        System.out.println();
    }


    /**
     * 6.2、快排（网上写法，精简了）
     * 选择一个基数，然后排序，将小于基数的放左边，大于基数的放右边，然后在基数两边的子序列进行重复
     **/
    private static int[] quickSort2(int[] arr) {
        int[] sortArr = Arrays.copyOf(arr, arr.length);
        quick2(sortArr, 0, sortArr.length - 1);
        return sortArr;
    }

    private static void quick2(int[] sortArr, int start, int end) {
        if (start >= end) {
            return;
        }
        // 计算基于基数排完序的基数下标，下标左边都是小于的数，下标右边都是大于的数
        int index = partition(sortArr, start, end);
        quick2(sortArr, start, index - 1);
        quick2(sortArr, index + 1, end);
    }

    private static int partition(int[] sortArr, int start, int end) {
        // 基数
        int point = start;
        int index = point + 1;
        // 一个for循环，比较有意思。注意这里end需要等于，因为第一个end已经是length-1了，end已经在范围内了。
        for (int i = index; i <= end; i++) {
            if (sortArr[i] < sortArr[point]) {
                int temp = sortArr[i];
                sortArr[i] = sortArr[index];
                sortArr[index] = temp;
                index++;
            }
        }
        // 将基数 与 index-1的位置进行替换，完成一次基数的处理
        int tem = sortArr[point];
        sortArr[point] = sortArr[index - 1];
        sortArr[index - 1] = tem;
        return index - 1;
    }


    /**
     * 6、快排
     * 选择一个基数，然后排序，将小于基数的放左边，大于基数的放右边，然后在基数两边的子序列进行重复
     **/
    private static int[] quickSort(int[] arr) {
        int[] sortArr = Arrays.copyOf(arr, arr.length);

        if (arr.length <= 1) {
            return arr;
        }

        int start = 0;
        int end = sortArr.length - 1;
        quick(sortArr, start, end);

        return sortArr;
    }
    private static void quick(int[] sortArr, int start, int end) {
        if (start >= end) {
            return;
        }
        int copyStart = start;
        int copyEnd = end;

        while (start < end) {
            while (start < end) {
                if (sortArr[end] < sortArr[start]) {
                    int tem = sortArr[start];
                    sortArr[start] = sortArr[end];
                    sortArr[end] = tem;
                    start++;
                    break;
                }
                end--;
            }
            while (start < end) {
                if (sortArr[start] > sortArr[end]) {
                    int tem = sortArr[start];
                    sortArr[start] = sortArr[end];
                    sortArr[end] = tem;
                    end--;
                    break;
                }
                start++;
            }
        }
        quick(sortArr, copyStart, start - 1);
        quick(sortArr, start + 1, copyEnd);

    }


    /**
     * 5、归并排序
     * 分而治之，采用递归的方式，将数据一次次分成2份，然后进行操作
     **/
    private static int[] mergeSort(int[] arr) {
        // 排序串
        int[] sortArr = Arrays.copyOf(arr, arr.length);
        if (sortArr.length <= 1) {
            return sortArr;
        }

        int middle = sortArr.length / 2;
        int[] leftArr = Arrays.copyOfRange(sortArr, 0, middle);
        int[] rightArr = Arrays.copyOfRange(sortArr, middle, sortArr.length);

        return merge(mergeSort(leftArr), mergeSort(rightArr));
    }
    /**
     * 两个子序列进行排序，通过归并的方式，合并到一个有序序列中
     **/
    private static int[] merge(int[] leftSort, int[] rightSort) {
        int[] result = new int[leftSort.length + rightSort.length];
        int i = 0;
        int leftIndex = 0;
        int rightIndex = 0;
        while (leftSort.length > leftIndex && rightSort.length > rightIndex) {
            if (leftSort[leftIndex] > rightSort[rightIndex]) {
                result[i ++] = rightSort[rightIndex ++];
            } else {
                result[i ++] = leftSort[leftIndex ++];
            }
        }

        while (leftSort.length > leftIndex) {
            result[i ++] = leftSort[leftIndex ++];
        }

        while (rightSort.length > rightIndex) {
            result[i ++] = rightSort[rightIndex ++];
        }

        return result;
    }


    /**
     * 4、希尔排序
     * 改进版的插入排序，将数组按步长分组进行插入排序，步长越来越小，当步长为1的时候，最后将整个数组进行插入排序
     **/
    private static int[] shellSort(int[] arr) {
        int length = arr.length;
        int temp;
        for (int step = length / 2; step >= 1; step = step / 2) {

            for (int i = step; i < length; i++) {
                temp = arr[i];

                int j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j = j - step;
                }
                // j的位置不为最大数，未调整位置
                if (j != i - step) {
                    arr[j + step] = temp;
                }
            }
        }
        return arr;
    }


    /**
     * 3、插入排序（类似打扑克牌）
     * 第一个元素是一个新序列，从第2个开始遍历，将其有序插入到新序列中
     **/
    private static int[] insertSort(int[] arr) {
        int[] sortArr = Arrays.copyOf(arr, arr.length);

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

            int num = sortArr[i + 1];
            // 遍历新序列（i之前）
            for (int j = i ; j >= 0; j --) {
                if (sortArr[j] >= num) {
                    sortArr[j + 1] = sortArr[j];
                    if (j == 0) {
                        sortArr[j] = num;
                    }
                } else {
                    sortArr[j + 1] = num;
                    break;
                }
            }
        }
        return sortArr;
    }

    /**
     * 2、选择排序（每次 选择（找）一个）
     * 每次循环找到最小（大）的数组成新数组，然后剩余的继续该动作
     **/
    private static int[] selectionSort(int[] arr) {
        int[] sortArray = Arrays.copyOf(arr, arr.length);

        // 比较少1轮
        for (int i = 0; i < sortArray.length - 1; i ++) {
            // 最小值的下标
            int minIndex = i;
            for (int j = i + 1; j < sortArray.length; j ++) {
                if (sortArray[j] < sortArray[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int temp = sortArray[minIndex];
                sortArray[minIndex] = sortArray[i];
                sortArray[i] = temp;
            }
        }

        return sortArray;
    }

    /**
     * 1、冒泡排序（1个1个网上冒）
     * 两次循环，每次都找到一个最大的放到数组的后面
     **/
    private static int[] bubbleSort(int[] arr) {
        // 如果不想改变arr，可以copy一下
        int[] sortArr = Arrays.copyOf(arr, arr.length);
        // i从1开始，最后一个不用遍历到，少一次循环
        for (int i = 1; i < sortArr.length; i++) {
            boolean changeFlag = false;
            for (int j = 0; j < sortArr.length - i; j++) {
                if (sortArr[j] > sortArr[j + 1]) {
                    int temp = sortArr[j];
                    sortArr[j] = sortArr[j + 1];
                    sortArr[j + 1] = temp;

                    changeFlag = true;
                }
            }
            if (!changeFlag) {
                break;
            }
        }
        return sortArr;
    }


}

其它四种排序待更新...