手写板

/*
    测试用例:
    1. 数组长度为1的数组
    2. 数组长度为2的数组
    3. 数组长度为3的数组
    3. 数组长度为4的数组
    4. 前三个的常规输入是 s≤e ，如果输入的 s>r
*/

/*
    在数组 array 中 s~m 和 m~e 是两个已经拍好序的子序列，
    分别将它们拷贝到两个新数组中然后将两个新数组归并到 array 的 s~e 位置
    需要注意是否存在 (s==m||m==e) 的情况

    @param array 输入的数组
    @param s    : 数组的起始索引 (s)tart
    @param m    : 数组的中点索引 (m)iddle
    @param e    : 数组的终止索引 (e)nd
*/
public void merge(int[] array, int s, int m, int e){
    //将 s~m 拷贝到新数组 lArray
    int[] lArray = new int[m-s+1];
    for(int i = 0; i<lArray.length; i++){
        lArray[i] = array[s+i];
    }
    //将 m+1~e 拷贝到新数组 rArray
    int[] rArray = new int[e-m];
    for(int i = 0; i<rArray.length; i++){
        rArray[i] = array[m+1+i];
    }
    //归并 lArray 和 rArray
    for(int i=s,l=0,r=0; i<=e; i++){
        if(lArray[l]>rArray[r]){
            array[i] = rArray[r];
            r++;
        }else{
            array[i] = lArray[l];
        }
    }
}

/*
    @param array: 输入的数组
    @param s    : 数组的起始索引 (s)tart
    @param e    : 数组的终止索引 (e)nd
    首次启动本方法的时候 s = 0 ; e = n-1 。
*/
public mergeShort(int[] array,int s,int e){
    if(s>=e){
        if(s-e==1||s==e){
            println("要排序的子序列只有一个元素，不必排序和归并了。");
        }else{
            println("错误输入 s = " + s + ";e = " + e + ";");
        }
        return;
    }

    int m = (e+s)/2;            //计算出索引区间[(s)tart,(e)nd]中点处的索引 (m)iddle。
    mergeShort(array,s,m);
    mergeShort(array,m+1,e);    //当 s==e 的时候会造成 s>e 的输入。
    merge(array,s,m,e);
}

/*冒泡排序*/
public void bubbleShort(int[] array){
    //(s)tart 表示序列索引的开始索引
    //(e)nd 表示序列索引的结束索引
    int temp = 0; //交换空间
    for(int e=array.length-1; e>0; e--){
        for(int s=1; s<=e; s++){
            if(array[s-1]>array[s]){
                temp = array[s];
                array[s] = array[s-1];
                array[s-1] = tmep;
            }//此语句块执行完成之后 array[s] 就是我们期望的本次轮循的最大值
        }
    }
}

/*
    快速排序测试用例:
    1. 数组长度为1的数组
    2. 数组长度为2的数组
    3. 数组长度为3的数组
    3. 数组长度为4的数组
    4. 前三个的常规输入是 s≤e ，如果输入的 s>r
*/

/*
    @param array: 长度为 n 数组
    @param s    : 数组的起始索引 (s)tart
    @param e    : 数组的终止索引 (e)nd
    首次启动本方法的时候 s = 0 ; e = n-1 。
*/
public void quickShort(int[] array, int s, int e){
    if(s>=e){
        if(s==e||(s-e)==1){
            println("要排序的子序列只有一个或零个元素，不必操作了。");
        }else /*if((s-e)>1)*/{
            println("输入错误");
        }
        return;
    }
    int m = partition(array,s,e);
    quickShort(array,s,m-1);
    quickShort(array,m+1,e);
}

/*
    以给定子序列中的最后一个元素当做中值，并遍历子序列中的其他元素最终将最后一个元素放到预定位置。

    @param array: 长度为 n 数组
    @param s    : 需要处理的子序列的起始索引 (s)tart
    @param e    : 需要处理的子序列的终止索引 (e)nd

    @return m   : 给定索引区间的中值所在的索引(这个中值的位置是我们的操作调换产生的)
*/
public int partition(int[] array, int s, int e){
    int midVal = array[e];
    int j = s-1;//指向小于等于 midVal 的最后一个元素
    int temp = 0;//交换空间
    for(int i = s; i<=e-1; i++){
        //期望 i 指向大于 midVal 的一个元素
        if(array[i] <= midVal){
            j += 1;
            temp = array[j];
            array[j] = array[i]
            array[i] = temp;
        }
    }//循环完成之后 [s,j] 区间内的元素均小于等于 midVal, [j+1,e-1]区间内的元素均大于 midVal
    //调整 midVal 的位置
    j += 1;
    temp = array[j];
    array[j] = array[e];
    array[e] = temp;
    return j+1;
}