package com.sxt.review;

/*内部排序：（在内存）
 * 插入排序-->希尔排序
 * 冒泡排序-->快速排序
 * 选择排序-->堆排序
 * 归并排序
 * 基数排序
 * 外部排序：（排序过程需访问外存）
 */
import java.util.Arrays;

public class TestSort {
    public static void main(String[] args) {
        int[] arr = { 2, 45, 3, 0, 7, 9, 2, 88 };
        // BubbleSort(arr);
        // System.out.println("冒泡排序："+Arrays.toString(arr));
        // ChoiceSort(arr);
        // System.out.println("选择排序："+Arrays.toString(arr));
        // InsertSort(arr);
        // System.out.println("插入排序：" + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("快速排序：" + Arrays.toString(arr));
    }
    //快速排序---------------------------------------------------------------
    //快速排序:通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，
    //       然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
    private static void quickSort(int[] arr, int left, int right) {
        // 设置两个运动标记 记录所操作的数的下标
        int i = left;
        int j = right;
        // 递归结束条件 每趟都是i==j时确定基准值位置
        if (i < j) {
            // 一趟快速排序
            int midValue = http://www.mamicode.com/arr[i]; // 每次以左边第一个数作为基准值midValue 记录midValue并为插入小的数做准备
            while (i < j) {
                while (i < j && arr[j] >= midValue) { // 循环！ 从后往前依次和基准值比较
                                                        // 注意保证i<j ！！
                    j--; // 最后一次  i指向小于基准值的数
                }
                if (i < j) {
                    arr[i] = arr[j];// 小的数插入左边标记（i）的位置
                    i++;// 左边标记向右移动一位 做准备
                }

                while (i < j && arr[i] <= midValue) {// 循环！ 从前往后依次和基准值比较
                    i++; // 最后一次  i指向大于基准值的数
                }
                if (i < j) {
                    arr[j] = arr[i];// 大的数插入右边标记（j）的位置（数据已记录）
                    j--;//右边的标记向左移动一位  做准备
                }
            }
            arr[i] = midValue;// i==j时 确定基准值的位置！
            // 递归体
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }
    //插入排序---------------------------------------------------------------
    // 插入排序 从第二个数开始将无序表数据依次插入到有序表的适当位置
    private static void InsertSort(int[] arr) {
        // 控制趟数
        for (int i = 1; i < arr.length; i++) {// 从第二个数开始依次比较插入 第一个数为有序表
            int insertVal = arr[i];// 记录要插入的数 防止有序表后移的数覆盖
            int insertPos = i - 1;// 记录插入的初始位置：无序表的前一位置（即从从本位置开始往前判断）
            while (insertPos >= 0 && insertVal < arr[insertPos]) {// index>=0:防止有序表越界
                arr[insertPos + 1] = arr[insertPos];// 大的后移（当前数后移）
                insertPos--;// 迭代条件 有序表继续往前判断
            }
            // 无序表待插入的值 插入 到有序表的最终位置
            arr[insertPos + 1] = insertVal;// +1：因为上面迭代-1
            System.out.println("插入排序：" + Arrays.toString(arr));
        }
    }
    //选择排序---------------------------------------------------------------
    // 选择排序：每次选择一个最值放到最终位置 （以最小值为例）每趟的数最小值放到最前
    private static void ChoiceSort(int[] arr) {
        int temp = 0;
        for (int i = 0; i < arr.length - 1; i++) {// n-1趟
            int minIndex = i;// 初始最小值
            for (int j = i + 1; j < arr.length; j++) {// i:每次前面少排序一个数
                                                        // +1：从初始i的下个数开始比较
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;// 记录真实最小值下标 为交换做准备
                }
            }
            // 初始最小值和真实最小值交换位置
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    //冒泡排序---------------------------------------------------------------
    // 冒泡排序 两两交换 大的一路向右
    private static void BubbleSort(int[] arr) {
        int temp = 0;
        for (int i = 0; i < arr.length - 1; i++) {// n-1趟
            boolean flag = true;
            for (int j = 0; j < arr.length - i - 1; j++) {// -i:每次少排一个数 -1
                                                            // arr[j+1]防止越界
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {// 如果没有发生交换说明已经有序 可以直接退出循环
                break;
            }
        }
    }

}