package com.lb;
public class ArrayIns {
private Student[] theArray;
public int nElements;
public ArrayIns(int max){
theArray = new Student[max];
nElements = 0;
}
public void insert(Student value){
theArray[nElements] = value;
nElements++;
}
public void display(){
System.out.println("A=");
for(int i=0;i<nElements;i++){
System.out.println(theArray[i]+" ");
}
System.out.println();
}
public void quickSort(){
recQuickSort(0,nElements-1);
}
public void recQuickSort(int left,int right){
if(right-left<=0){
return;
}else{
Student pivot = theArray[right];
int partion = partionIt(left,right,pivot);
recQuickSort(left,partion-1);//递归 前一部分划分
recQuickSort(partion+1,right);//递归 后一部分划分
}
}
public int partionIt(int left,int right,Student pivot){
int leftPtr = left-1;
int rightPtr = right;
while(true){
while(theArray[++leftPtr].compareTo(pivot)<0);
while(rightPtr>0&&theArray[--rightPtr].compareTo(pivot)>0);
if(leftPtr>=rightPtr){
break;
}else{
swap(leftPtr,rightPtr);
}
}
swap(leftPtr, right);
return leftPtr;
}
public void swap(int idx1,int idx2){
Student tmp = theArray[idx1];
theArray[idx1] = theArray[idx2];
theArray[idx2] = tmp;
}
}
<span style="font-size:32px;">package com.lb;
public class Student implements Comparable<Student>{
private int age;
private String name;
private int score;
public int getAge() {
return age;
}
public Student(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student [age=" + age + "]";
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
@Override
public int compareTo(Student o) {
if(this.getAge()-o.getAge()==0){
if(this.getName().compareTo(o.getName())==0){
return this.getScore()-o.getScore();
}
return this.getName().compareTo(o.getName());
}
return this.getAge()-o.getAge();
}
}
</span>
<span style="font-size:32px;">package com.lb;
public class QuickApp {
public static void main(String[] args) {
int maxSize = 16;
ArrayIns arr;
arr = new ArrayIns(maxSize);
/*for(int j=0;j<maxSize;j++){
int n = (int)(Math.random()*99);
arr.insert(new Student(n));
}*/
arr.insert(new Student(3));
arr.insert(new Student(1));
arr.insert(new Student(5));
arr.insert(new Student(10));
arr.insert(new Student(105));
arr.insert(new Student(2));
arr.display();
long start = System.currentTimeMillis();
arr.quickSort();
long end = System.currentTimeMillis();
System.out.println(end-start);
arr.display();
}
}</span>
输出:
A=
Student [age=3]
Student [age=1]
Student [age=5]
Student [age=10]
Student [age=105]
Student [age=2]
0
A=
Student [age=1]
Student [age=2]
Student [age=3]
Student [age=5]
Student [age=10]
Student [age=105]