java基础算法、递归调用、字符串切割详解

KLQ 2020-08-12 15:02:23 java常见问答 9132

下面要给大家分享的是一些比较简单的java基础知识,具体包括了java基础算法、递归调用、字符串切割,一起来了解一下吧。

算法

1、桶排序

/* 桶排序  */
public static void booleanSort()
{
    int[] sortlist = new int[]
    {
        1
        , 14
        , 9
        , 33
        , 11
        , 45
        , 32
    };
    boolean[] sortboolean = new boolean[46];
    for (int index: sortlist)
    {
        sortboolean[index] = true;
    }
    for (int i = sortboolean.length - 1; i >= 0; i--)
    {
        if (sortboolean[i]) System.out.print(i + "--");
    }
}

这个还是存在一定的局限性的,首先是你一定要知道数组的最大值,其次就是在数组当中不可以存在重复值,都则的话,就只会显示一个了,在这,数组当中不能为负数,但是,假如你知道负数的最小值的话,那么,这个也是可以的,你可以将数组当中的元素进行操作,将他们都编程正数,之后,在最后输出时进行反向操作就可以了。

2、冒泡排序

/* 冒泡排序1(从右向左冒泡)  */
public static void bubbleSortFromRight()
{
    int[] sortlist = new int[]
    {
        1
        , 14
        , 9
        , 33
        , 11
        , 45
        , 32
    };
    int tmp = 0;
    for (int i = 0; i < sortlist.length; i++)
    {
        for (int j = 0; j < sortlist.length - i - 1; j++)
        {
            if (sortlist[j] > sortlist[j + 1])
            {
                tmp = sortlist[j + 1];
                sortlist[j + 1] = sortlist[j];
                sortlist[j] = tmp;
            }
        }
    }
    for (int sortednum: sortlist)
    {
        System.out.println(sortednum);
    }
}
/* 冒泡排序2(从左向右冒泡)  */  
public static void bubbleSortFromLeft(){  
    int[] sortlist = new int[]{1,14,9,33,11,45,32};  
    int tmp = 0;  
    for(int i=0;i<sortlist.length;i++){  
        for(int j=sortlist.length-1;j>i;j--){  
            if(sortlist[j-1] > sortlist[j]){  
                tmp = sortlist[j-1];  
                sortlist[j-1] = sortlist[j];  
                sortlist[j] = tmp;  
            }  
        }  
    }  
    for(int sortednum : sortlist){  
        System.out.println(sortednum);  
    }  
}

3、快速排序算法

public class QuickSort
{
    public static void main(String[] args)
    {
        // int[] iArgs = new int[]{72,6,57,88,60,42,83,73,48,85};    
        int iLength = 10;
        int[] iArgs = new int[iLength];
        for (int i = 0; i < iLength; i++)
        {
            Random objRandom = new Random();
            iArgs[i] = objRandom.nextInt(100);
        }
        QuickSort quickSort = new QuickSort();
        //快速排序    
        quickSort.recursive(iArgs, 0, iArgs.length - 1);
        for (int i = 0; i < iArgs.length; i++)
        {
            System.out.print(iArgs[i] + " ");
        }
    }
    /**  
     * 递归循环数据  
     *   
     * @param args 数组  
     * @param left 数组左下标 (第一次调用的时候,为0) 
     * @param right 数组右下标 (第一次调用的时候,为数组长度-1) 
     * @return  
     */
    private void recursive(int[] args, int left, int right)
    {
        if (left < right)
        {
            //数据从left到right坐标的数据进行排序 ,排序后以基准值为目标,左边都是小于它的值,右边都是大于它的值  
            int iIndex = qucikSort(args, left, right); //iIndex 是基数放在数据位置    
            //递归算法,对于基数左边排序    
            recursive(args, left, iIndex - 1);
            //递归算法,对于基数右边排序    
            recursive(args, iIndex + 1, right);
        }
    }
    /**  
     * 确定基数左边的数都比它小,右边的数都比它大  
     *  
     *  
     * 实例说明:假如比较int[] args = {20,4,9,5,49}; 
     * 1、首次调用该方法时获取基准值iBase=args[0]=20; 
     * 2、从右向左找比基准数小的数,从左向右找比基准数大的数;接下来模拟while循环(r:right,l:left): 
     *  20(l) 4    9    5    49(r)  -- 循环前的状态 
     *  ------------------------------------------------- 
     *  20(l) 4    9    5(r) 49     -- 首先开始第2步循环。比较49(args[r])和20(iBase),因为args[r] > iBase,所以right--; 
     *  ------------------------------------------------- 
     *   5(l) 4    9    5(r) 49     -- 比较5(args[r])和20(iBase),因为args[r] < iBase,所以args[l] = 5(args[r]); 
     *  ------------------------------------------------- 
     *   5    4(l) 9    5(r) 49     -- 此时开始第3步循环。比较5(args[l])和20(iBase),因为args[l] < iBase,所以left++; 
     *  ------------------------------------------------- 
     *   5    4    9(l) 5(r) 49     -- 比较4(args[l])和20(iBase),因为args[l] < iBase,所以left++; 
     *  ------------------------------------------------- 
     *   5    4    9    5(lr) 49    -- 比较9(args[l])和20(iBase),因为args[l] < iBase,所以left++; 
     *  ------------------------------------------------- 
     *   5    4    9    5(lr) 49    -- 此时第3步循环的while条件left<right不成立,args[r] = 5(args[l]); 
     *  ------------------------------------------------- 
     *   5    4    9    20(lr) 49   -- 最外面的while(left < right)不成立,进行第4步args[left]= 20(iBase); 
     *  ------------------------------------------------ 
     *   5    4    9    [20]   49   -- 至此为止,完成了qucikSort(),确定了基数左右的数,并且返回left值,即基数值的索引。然后以基数索引为中心,分别对其左边和右边的数组进行同样规则的递归排序。   
     * @param args  数组  
     * @param left  数组左下标  
     * @param right 数组右下标  
     * @return  
     */
    private int qucikSort(int[] args, int left, int right)
    {
        //第1步.获取基准数  
        int iBase = args[left]; //基准数  
        while (left < right)
        {
            //第2步.从右向左找出第一个比基准数小的数(查找原理:从右向左,把每个数跟iBase比较,<iBase时,把索引为left的值(args[left])替换为索引为right的值(args[right]);然后开始第3步)  
            while (left < right && args[right] >= iBase)
            {
                right--;
            }
            args[left] = args[right];
            //第3步.从左向右找出第一个比基准数小的数 (查找原理跟第2步相仿)  
            while (left < right && args[left] <= iBase)
            {
                left++;
            }
            args[right] = args[left];
        }
        //第4步.因为第2步和第3步已经把iBase给替换掉了,所以重新复制到arg[left]。  
        args[left] = iBase;
        return left;
    }
}

4、插入排序算法

/** 
 * 插入排序算法 
 * @param args 
 */
public void insertSort(int args[])
{
    for (int i = 1; i < args.length; i++)
    {
        int iBase = args[i];
        int j = i - 1;
        while (j >= 0 && args[j] > iBase)
        {
            args[j + 1] = args[j];
            j--;
        }
        args[j + 1] = iBase;
    }
    System.out.println(Arrays.toString(args));
}
public static void main(String[] args)
{
    int iLength = 10;
    int[] iArgs = new int[iLength];
    for (int i = 0; i < iLength; i++)
    {
        Random objRandom = new Random();
        iArgs[i] = objRandom.nextInt(100);
    }
    QuickSort quickSort = new QuickSort();
    quickSort.insertSort(iArgs);
}

5、二分查找算法

/** 
 * 二分查找算法 
 *  
 * 前提:数组是已排好序的。 
 * 原理:假设要找到的值为X,首先找到数组中间的值M。 
 *       若X<M,则只需在数组右边的数值中查找; 
 *       若X>M,只需在数组左边的数值中查找; 
 *       若X=M,返回下标索引。 
 * 实例:int[] sortList = {1,2,3,4,5,6,7,8,9,10}; 假定查询数值 7: 
 * (1).首先找到中间的值是5(索引值为4:start=0,end=9,middle=(start+end)/2=4); 
 * (2).拿5和要查询的数值7比较,7>5(对应X>M),只需在数组左边数值中查询,即只要在{6,7,8,9,10}中查询; 
 * (3).查询的数组不变,需要设置start=middle+1,end不变,然后获取到的中间值即为8(索引值为7:start=5,end=9,middle=(5+9)/2=7); 
 * (4).循环1,2,3步即可。 
 * @param sortedList   排序好的数组 
 * @param start        开始位置 
 * @param end          结束位置 
 * @param findvalue    需要找到的数值  
 * @return             返回该值所在数组中的索引(从0开始,查询不到返回-1) 
 */
public static int binarySearch(int[] sortedList, int start, int end, int findValue)
{
    int middle = (start + end) / 2;
    if (start > end)
    {
        return -1;
    }
    else if (start + 1 == end)
    {
        if (sortedList[start] == findValue)
        {
            return start;
        }
        else
        {
            return end;
        }
    }
    else if (sortedList[middle] == findValue)
    {
        return middle;
    }
    else if (sortedList[middle] > findValue)
    {
        return binarySearch(sortedList, start, middle - 1, findValue);
    }
    else if (sortedList[middle] < findValue)
    {
        return binarySearch(sortedList, middle + 1, end, findValue);
    }
    return -1;
}

最后的话放上一个排序的时间复杂度表格。

排序时间复杂度表格

递归算法

/* 递归算法(1+2+3+...+n=?) */
public static int circle(int param)
{
    if (param == 1)
    {
        return 1;
    }
    return param + circle(param - 1);
}
/* 将一整数逆序后放入一数组中(要求递归实现) 例如 : 1234 变为 {4,3,2,1} */
public static int inverse(int[] result, int number, int i)
{ //4321  
    if (i < result.length)
    {
        int value = number % 10;
        result[i] = value;
        number = (number - number % 10) / 10;
        return inverse(result, number, i + 1);
    }
    else
    {
        return 0;
    }
}
/* 递归实现回文判断(如:abcdedbca就是回文字符串)  */
public static boolean loopword(String str, int i)
{
    if (str.charAt(i) == str.charAt(str.length() - i - 1))
    {
        if (i == (str.length() - 1) / 2) return true;
        return loopword(str, i + 1);
    }
    else
    {
        return false;
    }
}
/* 反转字符串(如:abcdef反转后为fedcba)  */
public static String reverseString(String str)
{
    if (str.length() == 0) return str;
    return reverseString(str.substring(1)) + str.charAt(0);
}

字符串切割(包含中文)

问题:截取字符串时,里面有中文以及字母结合的时候,如何来进行切割呢?

注意:一个是汉字的字节数<0,另外一个就是,汉字在gbk编码当中,占用2个字节,在utf-8编码当中,占用3个字节。

public static String splitStr(String str, int len) throws Exception
{
    byte[] bt = str.getBytes("gbk");
    int wordIndex = 0, chineseIndex = 0, count = 0;
    if (bt.length > len)
    {
        for (int index = 0; index < len; index++)
        {
            if (bt[index] < 0)
            { //汉字的byte<0   
                //在gbk编码,汉字占用2个字节;utf-8编码,汉字占3个字节;若字符集编码为utf-8,count%3。    
                if (++count > 0 && count % 2 == 0)
                {
                    chineseIndex++;
                }
            }
            else
            { //英文byte>0    
                wordIndex++;
            }
        }
        return str.substring(0, wordIndex + chineseIndex);
    }
    else
    {
        return "字符截取数太大。";
    }
}

你还想了解更多的java基础知识吗?更多相关基础内容,请多多的关注奇Q工具网来进行了解吧。

推荐阅读:

java基础之string算法,五个练习题目

java二叉树后序遍历递归和非递归实现

求二叉树深度的递归算法java