バブル+高速+スタックソート
12858 ワード
package xie.struct;
import java.util.ArrayList;
public class Sort<T extends Comparable<T>> {
public static final int QuickSort = 1;
public static final int SelectMin = 4;
public static final int MaoPao = 3;
public static final int HeapSort = 2;
private ArrayList<T> data;//
public Sort() {
}
public void runSort(int mode) {
switch (mode) {
case 1:
System.out.println(" :");
this.QuickSort(data, 0, data.size() - 1);
break;
case 2:
System.out.println(" :");
this.heapSort();
break;
case 3:
System.out.println(" :");
this.MaoPao();
break;
case 4:
break;
default:
break;
}
}
public void setData(ArrayList<T> a) {
this.data = a;
}
public void addData(T data) {
this.data.add(data);
}
public String toString() {
for (int i = 0; i < data.size(); i++)
System.out.print(data.get(i) + "/");
return null;
}
public void MaoPao()
{
int i,j;
int n=this.data.size();
for(i=0;i<n;i++)
for(j=1;j<n-i;j++){
if(this.data.get(j-1).compareTo(this.data.get(j))>0)
{
T swap=this.data.get(j);
this.data.set(j,this.data.get(j-1));
this.data.set(j-1,swap);
}
}
}
/*
*
*/
private void QuickSort(ArrayList<T> a, int left, int right) {
if (left < right) {
int low = left;
int high = right;
T key = a.get(low);
while (low < high) {
while (low < high && a.get(high).compareTo(key) >= 0)
high--;
a.set(low, a.get(high));
while (low < high && a.get(low).compareTo(key) < 0)
low++;
a.set(high, a.get(low));
}
a.set(low, key);
QuickSort(a, left, low - 1);
QuickSort(a, low + 1, right);
}
}
/*
*
*
*/
private void buildHeap() {
int len = this.data.size();
int i;
for (i = len / 2 - 1; i >= 0; i--)
this.adjustHeap(i);
}
private void adjustHeap(int index) {
int len = this.data.size();
int left = index * 2 + 1;
int right = index * 2 + 2;
int smaller = left;
T swap;
if (left > len - 1)
return;
if (right < len
&& this.data.get(left).compareTo(this.data.get(right)) > 0) {
smaller = right;
}
if (smaller < len
&& this.data.get(index).compareTo(this.data.get(smaller)) > 0) {
swap = this.data.get(smaller);
this.data.set(smaller, this.data.get(index));
this.data.set(index, swap);
this.adjustHeap(smaller);
}
}
private void heapSort() {
this.buildHeap();
int len = this.data.size();
while (len > 0) {
System.out.print(this.data.get(0)+"/");
this.data.set(0, this.data.get(len - 1));
this.data.remove(len - 1);
len--;
this.adjustHeap(0);
}
}
/*
*
*
*/
public static void main(String args[]) {
ArrayList<String> array = new ArrayList<String>();
array.add("A");
array.add("D");
array.add("G");
array.add("H");
array.add("S");
array.add("J");
array.add("B");
Sort<String> sort = new Sort<String>();
sort.setData(array);
sort.runSort(Sort.QuickSort);
sort.toString();
sort.setData(array);
sort.runSort(Sort.MaoPao);
sort.toString();
sort.setData(array);
sort.runSort(Sort.HeapSort);
}
}
クイックソート出力:A/B/D/G/H/J/S/
泡立ちソート出力:A/B/D/G/H/J/S/
ヒープソート出力:A/B/D/G/H/J/S/