java基础算法、递归调用、字符串(含中文)切割

aokunsang

浏览: 816089 次
性别:
来自: 北京

最近访客更多访客>>

xuchengzhong83

Crow00

chenxinba

beyond0851

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

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+"--");
		}
	}

不过它有局限性：

1、你必须知道数组的最大值；

2、数组中一定不能有重复值，否则只会显示一个；

3、数组中不能为负数【但是如果你知道负数的最小值，这个也是允许的，你可以先把数组中的元素进行操作，把它们都变为正数，然后在最后输出的时候反向操作一次就行了】

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、插入排序算法

说明：插入排序理解原理后很简单，参考：http://zhdkn.iteye.com/blog/1136253

  /**
   * 插入排序算法
   * @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、其他排序算法

引用CSDN上某位网友的博客，写的很不错(c语言写的，原理描述的很清楚)。

1、选择排序算法(较简单，但不稳定)

2、归并排序算法(自底向上) 和归并排序算法(自顶向下)

6、二分查找算法

/**
	 * 二分查找算法
	 * 
	 * 前提：数组是已排好序的。
	 * 原理：假设要找到的值为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) ;
	}

二、字符串（包含中文）切割

截取字符串时候，里面有中文和字母相结合时候(如：abc我d是中df国人)，怎么合理进行切割使得不会切割出来半个汉字。只需要记住两点：

1、汉字的字节数<0；

2、汉字在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 "字符截取数太大。";  
        }  
    }