PKU 1007文字列逆シーケンス
2162 ワード
0/1の危害ですね、joel on softwareで言及したことがありますが、やはり、めちゃくちゃに書いてあります.
public class Measure {
private char[] sequence;
private int measure;
public Measure() {
this("");
}
public Measure(String seqString) {
this.sequence = seqString.toCharArray();
this.measure = 0;
}
public int calculate() {
this.mergeSort(0, this.sequence.length - 1);
return this.measure;
}
private void mergeSort(int begin, int end) {
int middle = (begin + end) / 2;
if (begin < end) {
this.mergeSort(begin, middle);
this.mergeSort(middle + 1, end);
this.merge(begin, middle, end);
}
}
private void merge(int begin, int middle, int end) {
int from = begin;
int to = end;
int temoMiddle = middle;
char[] tempSeq = new char[end + 1];
int position = 0;
while (begin <= temoMiddle && middle + 1 <= end){
if (this.sequence[begin] < this.sequence[middle + 1]) {
tempSeq[position] = this.sequence[begin++];
} else {
this.measure += (temoMiddle + 1) - begin;
tempSeq[position] = this.sequence[middle + 1];
middle++;
}
position++;
}
while (begin <= temoMiddle) {
tempSeq[position++] = this.sequence[begin++];
}
while (middle < end) {
tempSeq[position++] = this.sequence[middle + 1];
middle++;
}
System.arraycopy(tempSeq, 0, this.sequence, from, to - from + 1);
System.out.println("measure:" + measure);
System.out.println("seq " + new String(this.sequence));
}
public int getMeasure() {
return measure;
}
public void setMeasure(int measure) {
this.measure = measure;
}
public String getSequence() {
return new String(sequence);
}
public void setSequence(String sequence) {
this.sequence = sequence.toCharArray();
}
}