/**
 * 冒泡排序
 * 每次循环最大的数都到最后面
 * 1.确定循环次数
 * 2.比较当前位置j和下一个位置j+1处值的大小，将大数往后挪
 * @param num
 */
public static void sort1(int[] num){
    int temp;
    for(int i=0;i<num.length;i++){
        for(int j=0;j<num.length-i-1;j++){
            if(num[j] > num[j+1]){
                temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
            }
        }
    }
}

/**
 * 简单选择排序
 * 每次循环最小的数到最前面
 * 1.确定循环次数
 * 2.记录当前位置p和当前位置的值v
 * 3.从未排好序的位置开始循环，找出最小的
 * 4.最小的值和当前位置的值交换
 * @param num
 */
public static void sort2(int[] num){
    for(int i=0;i<num.length;i++){
        int v = num[i];
        int p = i;
        for(int j=i+1;j<num.length;j++){
            if(v > num[j]){
                v = num[j];
                p = j;
            }
        }
        num[p] = num[i];
        num[i] = v;
    }
}

/**
 * 直接插入排序
 * 当前位置的值插入到已经排好序的数据列中
 * 1.确定循环次数，第一个数默认已经排好序，从第二个数开始循环
 * 2.记录当前位置的值v
 * 3.已经排好序的个数j
 * 4.排好序的序列从后向前遍历，排好序的序列中的值大于当前位置的值，则向后移一位
 * 5.直到排好序的序列中的值不大于当前位置的值，循环结束，将当前位置的值插入
 * @param num
 */
public static void sort3(int[] num){
    for(int i=1;i<num.length;i++){
        int v = num[i];
        int j = i-1;//i-1是因为数组长度length-1
        while(j>=0 && num[j]>v){
            num[j+1] = num[j];
            j--;
        }
        //for(;j>=0&&num[j]>v;j--){
        //    num[j+1] = num[j];
        //}
        num[j+1] = v;//j+1是因为循环中j提前-1
    }
}

/**
 * 快速排序
 * 1.选择一个基准值，默认第一个
 * 2.循环比较数组中每个值和基准值的大小
 *   2.1从前向后循环，如果第i个比基准值小，指针+1位，继续循环
 *   2.2从后向前循环，如果第j个比基准值大，指针-1位，继续循环
 *   2.3前面两个循环都停止，说明第i个比基准值大，第j个比基准值小，将两个值交换位置
 * 3.重复上面的步骤，左侧是所有比基准值小的，右侧是比基准值大的
 * 4.遍历完跳出循环，进行回调，分为开始位置到i，j到结束位置
 * 5.重复上面的操作
 * @param num
 * @param start
 * @param end
 */
public static void sort4(int[] num, int start, int end){
    if(start < end){
        int p = num[start];
        int i = start, j = end;
        int temp;
        while(i <= j){
            while(num[i]<p && i<end){
                i++;
            }
            while(num[j]>p && j>start){
                j--;
            }
            if(i<=j){
                temp = num[i];
                num[i] = num[j];
                num[j] = temp;
                i++;
                j--;
            }
        }
        if(start < j){
            sort4(num, start, j);
        }
        if(end > i){
            sort4(num, i, end);
        }
    }
}