package com.test.suanfa;

public class BaseTest {
    public static void main(String[] args) {
        int arr[] = {20,23,43,2,4,67,8,6,65,33,10,19};
        printArray(arr);
        System.out.println("------------bubbleSort----------------");
       // bubbleSort(arr);
        System.out.println("--------------insertSort--------------");
       // insertSort(arr);
        System.out.println("-------------selectSort---------------");
        //selectSort(arr);
        System.out.println("------------quickSort----------------");
       //quickSort(arr,0,arr.length-1);

    }

    /*
    冒泡算法：这个应该不用说太多，简单说下就是首先是两两数据进行比较 比如0 1 ； 1 2 ；2 3；3 4这样
    可以知道，当我们运行到第一次之后，我们是知道这个时候最大的数是在末尾end了
    然后第二次比较的时候，我们就只用比较到end-1的情况，后面依次递减
     */
    static void bubbleSort(int[] arr){
        int length = arr.length -1;
        for (int i = length; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }

        }
        printArray(arr);
    }

    /*
    插入算法:你可以把它想象成摸牌的时候，你摸第一张牌是不用排序的，但是当你摸了第2张牌的时候，
    你就需要对这两张牌进行排序，拍好序后，开始摸第三张牌，然后在对这张牌进行排序，后面第4张牌，5张牌，
    只是你排序的方式会有所不同，毕竟不是摸牌嘛。
    比如我们现在一个数，2   不用排序
    现在多了一个数 3  然后3 是大于2的，不用交换顺序
    然后现在是2 3了，我们现在是有一个1了，我们1先和3比较，因为小于3，所以交换位置，然后在和2比较，在交换位置
    现在就是1 2 3了，反正我们每次比较的时候，都是要像前面进行比较。
     */
    static void insertSort(int[] arr){
        int length = arr.length -1;
        for (int i = 0; i <= length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
                swap(arr ,j,j-1);
            }
        }
        printArray(arr);
    }
    /*
    选择排序：选择排序 0-n是先选择最小的数放在第一份，然后把原来第一位的数放在最小数的位置
    然后在判断1-n 中最小的数，然后把其中最小的数放在第1的位置，然后把第1位置的数放在最小数的位置
    然后在判断2-n中最小的数，然后把其中最小的数放在第2的位置，然后把第2位置的数放在最小数的位置
    ...
    依次类推，我们每次比较的数据都是从0开始，一次往后，前面的数据都是比较好了的，那么上代码
     */
    static void selectSort(int[] arr){
        int length = arr.length-1;
        for (int i = 0; i <= length; i++) {
            int minValue = i;
            for (int j = i; j < length; j++) {
                if(arr[minValue] > arr[j+1]){
                    minValue = j+1;
                }
            }
            swap(arr,minValue,i);

        }
        printArray(arr);
    }

    /*
    快速排序：快排的话，就有点像分治的方式，但又不完全是
    该方法的基本思想是：1.先从数列中取出一个数作为基准数。
                     2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
                     3．再对左右区间重复第二步，直到各区间只有一个数。
    比如20,23,43,2,4,67,8
    第1次8,23,43,2,4,67,8 ---先从右往左进行判断 这里判断的标准是arr[0] = 20 ;
    第2次8,23,43,2,4,67,23  ---当右边返回后，在判断左边 后面依次
    第3次8,23,43,2,4,67,23
    第4次8,4,43,2,4,67,23
    第5次8,4,43,2,43,67,23
    第6次8,4,2,2,43,67,23
    然后就变成了8,4,2,20,43,67,23
     */
    static void quickSort(int[] arr,int l,int r) {
        if(l<r) {
            int left = l;
            int right = r;
            int tmp = arr[left];
            while (left < right) {
                while (left < right && tmp < arr[right]) {
                    right--;
                }
                arr[left] = arr[right];
                while (left < right && tmp > arr[left]) {
                    left++;
                }
                arr[right] = arr[left];
            }
            arr[left] = tmp;
            quickSort(arr, l, left-1 );
            quickSort(arr, left+1, r);
        }
        printArray(arr);
    }

    private static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp ;
    }



}