插入排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class InsertSort implements SortUtil.Sort{
??? /* (non-Javadoc)
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? int temp;
??????? for(int i=1;i<data.length;i++){
??????????? for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
??????????????? SortUtil.swap(data,j,j-1);
??????????? }
??????? }???????
??? }
}
冒泡排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class BubbleSort implements SortUtil.Sort{
??? /* (non-Javadoc)
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? int temp;
??????? for(int i=0;i<data.length;i++){
??????????? for(int j=data.length-1;j>i;j--){
??????????????? if(data[j]<data[j-1]){
??????????????????? SortUtil.swap(data,j,j-1);
??????????????? }
??????????? }
??????? }
??? }
}
選擇排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class SelectionSort implements SortUtil.Sort {
??? /*
???? * (non-Javadoc)
???? *
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? int temp;
??????? for (int i = 0; i < data.length; i++) {
??????????? int lowIndex = i;
??????????? for (int j = data.length - 1; j > i; j--) {
??????????????? if (data[j] < data[lowIndex]) {
??????????????????? lowIndex = j;
??????????????? }
??????????? }
??????????? SortUtil.swap(data,i,lowIndex);
??????? }
??? }
}
Shell排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class ShellSort implements SortUtil.Sort{
??? /* (non-Javadoc)
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? for(int i=data.length/2;i>2;i/=2){
??????????? for(int j=0;j<i;j++){
??????????????? insertSort(data,j,i);
??????????? }
??????? }
??????? insertSort(data,0,1);
??? }
??? /**
???? * @param data
???? * @param j
???? * @param i
???? */
??? private void insertSort(int[] data, int start, int inc) {
??????? int temp;
??????? for(int i=start+inc;i<data.length;i+=inc){
??????????? for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
??????????????? SortUtil.swap(data,j,j-inc);
??????????? }
??????? }
??? }
}
快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class QuickSort implements SortUtil.Sort{
??? /* (non-Javadoc)
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? quickSort(data,0,data.length-1);???????
??? }
??? private void quickSort(int[] data,int i,int j){
??????? int pivotIndex=(i+j)/2;
??????? //swap
??????? SortUtil.swap(data,pivotIndex,j);
???????
??????? int k=partition(data,i-1,j,data[j]);
??????? SortUtil.swap(data,k,j);
??????? if((k-i)>1) quickSort(data,i,k-1);
??????? if((j-k)>1) quickSort(data,k+1,j);
???????
??? }
??? /**
???? * @param data
???? * @param i
???? * @param j
???? * @return
???? */
??? private int partition(int[] data, int l, int r,int pivot) {
??????? do{
?????????? while(data[++l]<pivot);
?????????? while((r!=0)&&data[--r]>pivot);
?????????? SortUtil.swap(data,l,r);
??????? }
??????? while(l<r);
??????? SortUtil.swap(data,l,r);???????
??????? return l;
??? }
}
改進后的快速排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class ImprovedQuickSort implements SortUtil.Sort {
??? private static int MAX_STACK_SIZE=4096;
??? private static int THRESHOLD=10;
??? /* (non-Javadoc)
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? int[] stack=new int[MAX_STACK_SIZE];
???????
??????? int top=-1;
??????? int pivot;
??????? int pivotIndex,l,r;
???????
??????? stack[++top]=0;
??????? stack[++top]=data.length-1;
???????
??????? while(top>0){
??????????? int j=stack[top--];
??????????? int i=stack[top--];
???????????
??????????? pivotIndex=(i+j)/2;
??????????? pivot=data[pivotIndex];
???????????
??????????? SortUtil.swap(data,pivotIndex,j);
???????????
??????????? //partition
??????????? l=i-1;
??????????? r=j;
??????????? do{
??????????????? while(data[++l]<pivot);
??????????????? while((r!=0)&&(data[--r]>pivot));
??????????????? SortUtil.swap(data,l,r);
??????????? }
??????????? while(l<r);
??????????? SortUtil.swap(data,l,r);
??????????? SortUtil.swap(data,l,j);
???????????
??????????? if((l-i)>THRESHOLD){
??????????????? stack[++top]=i;
??????????????? stack[++top]=l-1;
??????????? }
??????????? if((j-l)>THRESHOLD){
??????????????? stack[++top]=l+1;
??????????????? stack[++top]=j;
??????????? }
???????????
??????? }
??????? //new InsertSort().sort(data);
??????? insertSort(data);
??? }
??? /**
???? * @param data
???? */
??? private void insertSort(int[] data) {
??????? int temp;
??????? for(int i=1;i<data.length;i++){
??????????? for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
??????????????? SortUtil.swap(data,j,j-1);
??????????? }
??????? }??????
??? }
}
歸并排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class MergeSort implements SortUtil.Sort{
??? /* (non-Javadoc)
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? int[] temp=new int[data.length];
??????? mergeSort(data,temp,0,data.length-1);
??? }
???
??? private void mergeSort(int[] data,int[] temp,int l,int r){
??????? int mid=(l+r)/2;
??????? if(l==r) return ;
??????? mergeSort(data,temp,l,mid);
??????? mergeSort(data,temp,mid+1,r);
??????? for(int i=l;i<=r;i++){
??????????? temp[i]=data[i];
??????? }
??????? int i1=l;
??????? int i2=mid+1;
??????? for(int cur=l;cur<=r;cur++){
??????????? if(i1==mid+1)
??????????????? data[cur]=temp[i2++];
??????????? else if(i2>r)
??????????????? data[cur]=temp[i1++];
??????????? else if(temp[i1]<temp[i2])
??????????????? data[cur]=temp[i1++];
??????????? else
??????????????? data[cur]=temp[i2++];???????????
??????? }
??? }
}
改進后的歸并排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class ImprovedMergeSort implements SortUtil.Sort {
??? private static final int THRESHOLD = 10;
??? /*
???? * (non-Javadoc)
???? *
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? int[] temp=new int[data.length];
??????? mergeSort(data,temp,0,data.length-1);
??? }
??? private void mergeSort(int[] data, int[] temp, int l, int r) {
??????? int i, j, k;
??????? int mid = (l + r) / 2;
??????? if (l == r)
??????????? return;
??????? if ((mid - l) >= THRESHOLD)
??????????? mergeSort(data, temp, l, mid);
??????? else
??????????? insertSort(data, l, mid - l + 1);
??????? if ((r - mid) > THRESHOLD)
??????????? mergeSort(data, temp, mid + 1, r);
??????? else
??????????? insertSort(data, mid + 1, r - mid);
??????? for (i = l; i <= mid; i++) {
??????????? temp[i] = data[i];
??????? }
??????? for (j = 1; j <= r - mid; j++) {
??????????? temp[r - j + 1] = data[j + mid];
??????? }
??????? int a = temp[l];
??????? int b = temp[r];
??????? for (i = l, j = r, k = l; k <= r; k++) {
??????????? if (a < b) {
??????????????? data[k] = temp[i++];
??????????????? a = temp[i];
??????????? } else {
??????????????? data[k] = temp[j--];
??????????????? b = temp[j];
??????????? }
??????? }
??? }
??? /**
???? * @param data
???? * @param l
???? * @param i
???? */
??? private void insertSort(int[] data, int start, int len) {
??????? for(int i=start+1;i<start+len;i++){
??????????? for(int j=i;(j>start) && data[j]<data[j-1];j--){
??????????????? SortUtil.swap(data,j,j-1);
??????????? }
??????? }
??? }
}
堆排序:
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class HeapSort implements SortUtil.Sort{
??? /* (non-Javadoc)
???? * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
???? */
??? public void sort(int[] data) {
??????? MaxHeap h=new MaxHeap();
??????? h.init(data);
??????? for(int i=0;i<data.length;i++)
??????????? h.remove();
??????? System.arraycopy(h.queue,1,data,0,data.length);
??? }
???? private static class MaxHeap{
????????
???????
??????? void init(int[] data){
??????????? this.queue=new int[data.length+1];
??????????? for(int i=0;i<data.length;i++){
??????????????? queue[++size]=data[i];
??????????????? fixUp(size);
??????????? }
??????? }
????????
??????? private int size=0;
??????? private int[] queue;
???????????????
??????? public int get() {
??????????? return queue[1];
??????? }
??????? public void remove() {
??????????? SortUtil.swap(queue,1,size--);
??????????? fixDown(1);
??????? }
??????? //fixdown
??????? private void fixDown(int k) {
??????????? int j;
??????????? while ((j = k << 1) <= size) {
??????????????? if (j < size && queue[j]<queue[j+1])
??????????????????? j++;
??????????????? if (queue[k]>queue[j]) //不用交換
??????????????????? break;
??????????????? SortUtil.swap(queue,j,k);
??????????????? k = j;
??????????? }
??????? }
??????? private void fixUp(int k) {
??????????? while (k > 1) {
??????????????? int j = k >> 1;
??????????????? if (queue[j]>queue[k])
??????????????????? break;
??????????????? SortUtil.swap(queue,j,k);
??????????????? k = j;
??????????? }
??????? }
??? }
}
?
SortUtil:
package org.rut.util.algorithm;
import org.rut.util.algorithm.support.BubbleSort;
import org.rut.util.algorithm.support.HeapSort;
import org.rut.util.algorithm.support.ImprovedMergeSort;
import org.rut.util.algorithm.support.ImprovedQuickSort;
import org.rut.util.algorithm.support.InsertSort;
import org.rut.util.algorithm.support.MergeSort;
import org.rut.util.algorithm.support.QuickSort;
import org.rut.util.algorithm.support.SelectionSort;
import org.rut.util.algorithm.support.ShellSort;
/**
?* @author treeroot
?* @since 2006-2-2
?* @version 1.0
?*/
public class SortUtil {
??? public final static int INSERT = 1;
??? public final static int BUBBLE = 2;
??? public final static int SELECTION = 3;
??? public final static int SHELL = 4;
??? public final static int QUICK = 5;
??? public final static int IMPROVED_QUICK = 6;
??? public final static int MERGE = 7;
??? public final static int IMPROVED_MERGE = 8;
??? public final static int HEAP = 9;
??? public static void sort(int[] data) {
??????? sort(data, IMPROVED_QUICK);
??? }
??? private static String[] name={
??????????? "insert","bubble","selection","shell","quick","improved_quick","merge","improved_merge","heap"
??? };
???
??? private static Sort[] impl=new Sort[]{
??????????? new InsertSort(),
??????????? new BubbleSort(),
??????????? new SelectionSort(),
??????????? new ShellSort(),
??????????? new QuickSort(),
??????????? new ImprovedQuickSort(),
??????????? new MergeSort(),
??????????? new ImprovedMergeSort(),
??????????? new HeapSort()
??? };
??? public static String toString(int algorithm){
??????? return name[algorithm-1];
??? }
???
??? public static void sort(int[] data, int algorithm) {
??????? impl[algorithm-1].sort(data);
??? }
??? public static interface Sort {
??????? public void sort(int[] data);
??? }
??? public static void swap(int[] data, int i, int j) {
??????? int temp = data[i];
??????? data[i] = data[j];
??????? data[j] = temp;
??? }
}
?JAVA中金額的中文大寫方式
?
題意:
讀入一個浮點數值,將其轉化為中文金額的大寫方式.
試驗要求:
當金額為整數時,只表示整數部分,省略小數部分,并添加"整"字.
當金額中含有連續的0時,只需要一個"零"即可.
10的表示方式.例如110--壹佰一拾元整,10---一拾元整
? 1import java.io.*;
? 2class chineseMoney...{
? 3??? private String number[]=...{"","壹","貳","叁","肆","伍","陸","柒","捌","玖"};
? 4??? private String unit[]=...{"元","拾","佰","仟","萬","拾","佰","仟","億","拾","佰"};
? 5??? private String small[]=...{"角","分"};
? 6??? private String strNumber,strUnit,strAll;
? 7
? 8??? private String onlyInt(int intInt)
? 9??? ...{
10??????? String strInt;
11??????? strInt=String.valueOf(intInt);
12??????? strNumber="";strUnit="";strAll="";
13??????? int l=strInt.length ();
14??????? int j,k,zeorCount;
15??????? zeorCount=0;
16??????? for (k=0;k<l;k++)
17??????? ...{
18??????????? String strTemp=strInt.substring(k,k+1);
19??????????? int intTemp=Integer.parseInt(strTemp);
20??????????? strNumber=number[intTemp];
21??????????? j=l-1-k;
22??????????? strUnit=unit[j];
23??????????? if (intTemp==0)
24??????????? ...{
25??????????????? if (zeorCount==0)
26??????????????? ...{
27??????????????????? strUnit=strUnit.replace('拾','零');
28??????????????????? strUnit=strUnit.replace('佰','零');
29??????????????????? strUnit=strUnit.replace('仟','零');
30??????????????????? strUnit=strUnit.replace('萬','零');???
31??????????????? }
32??????????????? else
33??????????????? ...{
34??????????????????? strUnit=strUnit.replaceAll("拾","");
35??????????????????? strUnit=strUnit.replaceAll("佰","");
36??????????????????? strUnit=strUnit.replaceAll("仟","");
37??????????????????? strUnit=strUnit.replaceAll("萬","");???????
38??????????????? }
39??????????????? zeorCount++;
40??????????? }???????
41??????????? strAll+=strNumber+strUnit;
42??????? }
43??????? return strAll;
44???
45??? }
46???
47??? private String onlySmall(int intSmall)
48??? ...{
49???????
50??????? strNumber="";strUnit="";strAll="";
51??????? String strSmall,strTemp;
52??????? strSmall=String.valueOf(intSmall);
53??????? int i;
54??????? if (intSmall>=10)
55??????? ...{
56??????????? for (i=0;i<strSmall.length();i++)
57??????????? ...{
58??????????????? strTemp=String.valueOf(intSmall).substring(i,i+1);
59??????????????? if (Integer.parseInt(strTemp)!=0)
60??????????????? ...{
61??????????????????? strNumber=number[Integer.parseInt(strTemp)];
62??????????????????? strUnit=small[i];???
63??????????????????? strAll+=strNumber+strUnit;
64??????????????? }
65??????????? }
66??????? }
67??????? else
68??????? ...{
69??????????? if (intSmall!=0)
70??????????? ...{
71??????????????? strNumber=number[intSmall];
72??????????????? strUnit=small[1];???
73??????????????? strAll+=strNumber+strUnit;
74??????????? }
75??????? }
76
77??????? return strAll;
78??? }
79???
80??? public String getChineseMoney(double number)
81??? ...{
82??????? //四舍五入
83??????? number=(number*100+0.5)/100;
84???????
85??????? String strAll,strChineseInt,strChineseSmall,strZheng;;
86??????? int intInt,intSmall;
87??????? strChineseInt="";strChineseSmall="";strZheng="";
88???????
89??????? //整數部分
90??????? intInt=(int)( number*100/100);
91??????? if (intInt!=0)
92??????? ...{
93??????????? strChineseInt=onlyInt(intInt);
94??????? }
95??????? //小數部分
96??????? double temp=(number-intInt)*100*100/100;
97??????? //對小數部分四舍五入
98??????? intSmall=(int)(temp*100+0.5)/100;
99??????? if (intSmall!=0)
100??????? ...{
101??????????? strChineseSmall=onlySmall(intSmall);
102??????? }
103??????? else
104??????? ...{
105??????????? strZheng="整";
106??????? }
107??????? strAll=strChineseInt+strChineseSmall+strZheng;
108??????? return strAll;
109??? }
110??? public static void main(String args[]) throws IOException
111??? ...{
112??????? chineseMoney cm=new chineseMoney();
113??????? double money;
114??????? String strMoney,strChineseMoney;
115??????? strMoney="";
116??????? //讀取
117??????? System.out.println("輸入貨幣(四舍五入):");
118??????? BufferedReader cin = new BufferedReader(new InputStreamReader( System.in));
119??????? strMoney = cin.readLine();
120??????? money=Double.parseDouble(strMoney);
121??????? strChineseMoney=cm.getChineseMoney(money);
122??????? System.out.println(strChineseMoney);
123??? }
124}
?