以下採用三種不同的氣泡排序將學生成績由高至低排好.
方法一 內層迴圈所指位置與外層迴圈比大小(都是由左至右比較)
程式碼
import java.io.*;
class C7P155
{
public static void main(String[] args) throws IOException
{
int student_num = 0, maxgr = 0, mingr = 0, maxid = 0, minid = 0, sum = 0, ccount = 0, scount = 0;
boolean status = false;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("學生成績分析程式 ");
do{
System.out.print("請輸入學生人數 ");
try{
student_num = Integer.parseInt(br.readLine());
status = false;
} catch ( NegativeArraySizeException e ){
System.out.println("請輸入正整數的學生人數.");
status = true;
} catch ( NumberFormatException e ){
System.out.println("請輸入學生人數.");
status = true;
}
} while (status);
int grade[] = new int[student_num];
System.out.println("\n開始輸入學生成績");
for(int i = 0; i < student_num; i++){
status = false;
do{
System.out.print("學生 " + (i+1) + " 成績 ");
try{
grade[i] = Integer.parseInt(br.readLine());
sum += grade[i];
if( i == 0 ){
maxgr = mingr = grade[i];
}else{
if(grade[i] > maxgr){
maxgr = grade[i]; maxid = i;
} else if(grade[i] < mingr){
mingr = grade[i]; minid = i;
}
}
status = false;
} catch ( NumberFormatException e ){
System.out.println("請輸入正整數的成績.");
status = true;
}
} while (status);
}
System.out.println("\n開始輸出學生成績");
for(int i = 0; i < grade.length; i++){
System.out.println("學生 " + (i+1) + " 成績 " + grade[i]);
}
System.out.println("\n最高最低成績");
System.out.println("最高成績 第 " + (maxid+1) + " 號學生成績" + grade[maxid]);
System.out.println("最低成績 第 " + (minid+1) + " 號學生成績" + grade[minid]);
System.out.println("\n平均成績 " + (float)sum/(float)grade.length);
System.out.println("\n成績排行榜");
// Generate student id array
int stid[] = new int[grade.length];
for(int i = 0; i < grade.length; i++){ stid[i] = i; }
// Sort by grade via bubble sort
System.out.print("成績排序中 ");
for(int i = 0; i < (grade.length - 1); i++){
for(int j = i+1; j < grade.length; j++){
if(grade[j] > grade[i]){
// swap
int tmpgr = grade[j];
int tmpid = stid[j];
grade[j] = grade[i];
stid[j] = stid[i];
grade[i] = tmpgr;
stid[i] = tmpid;
scount++;
System.out.print("s");
} else {
System.out.print(".");
}
ccount++;
}
}
System.out.println("\nSwap / Total comparison : " + scount + " / " + ccount);
System.out.println("\n成績排序結果");
int rank = 1;
for(int i = 0; i < grade.length; i++){
if( i != 0 && grade[i] != grade[i-1] ){ rank++; }
System.out.println("名次 " + (i+1) + " 第 " + (stid[i]+1) + " 號學生成績 " + grade[i]);
}
}
}
物件導向版
import java.io.*;
class Student
{
int sid;
int grade;
public void setGrade(int sid, int grade)
{
this.sid = sid;
this.grade = grade;
}
public int getGrade()
{
return this.grade;
}
public int getSid()
{
return this.sid;
}
}
class C8P158
{
public static void main(String[] args) throws IOException
{
int student_num = 0, maxgr = 0, mingr = 0, maxid = 0, minid = 0, sum = 0, ccount = 0, scount = 0;
boolean status = false;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("學生成績分析程式 ");
do{
System.out.print("請輸入學生人數 ");
try{
student_num = Integer.parseInt(br.readLine());
status = false;
} catch ( NegativeArraySizeException e ){
System.out.println("請輸入正整數的學生人數.");
status = true;
} catch ( NumberFormatException e ){
System.out.println("請輸入學生人數.");
status = true;
}
} while (status);
Student grade[] = new Student[student_num];
System.out.println("\n開始輸入學生成績");
for(int i = 0; i < student_num; i++){
status = false;
int tmpgrade = 0;
do{
System.out.print("學生 " + (i+1) + " 成績 ");
try{
tmpgrade = Integer.parseInt(br.readLine());
grade[i] = new Student();
grade[i].setGrade( i + 1, tmpgrade );
sum += grade[i].getGrade();
if( i == 0 ){
maxgr = mingr = grade[i].getGrade();
}else{
if(grade[i].getGrade() > maxgr){
maxgr = grade[i].getGrade(); maxid = i;
} else if(grade[i].getGrade() < mingr){
mingr = grade[i].getGrade(); minid = i;
}
}
status = false;
} catch ( NumberFormatException e ){
System.out.println("請輸入正整數的成績.");
status = true;
}
} while (status);
}
System.out.println("\n開始輸出學生成績");
for(int i = 0; i < grade.length; i++){
System.out.println("學生 " + (grade[i].getSid()) + " 成績 " + grade[i].getGrade());
}
System.out.println("\n最高最低成績");
System.out.println("最高成績 第 " + grade[maxid].getSid() + " 號學生成績" + grade[maxid].getGrade());
System.out.println("最低成績 第 " + grade[minid].getSid() + " 號學生成績" + grade[minid].getGrade());
System.out.println("\n平均成績 " + (float)sum/(float)grade.length);
System.out.println("\n成績排行榜");
// Sort by grade via bubble sort
System.out.print("成績排序中 ");
for(int i = 0; i < (grade.length - 1); i++){
for(int j = i+1; j < grade.length; j++){
if(grade[j].getGrade() > grade[i].getGrade()){
// swap
Student tmpgr = grade[j];
grade[j] = grade[i];
grade[i] = tmpgr;
scount++;
System.out.print("s");
} else {
System.out.print(".");
}
ccount++;
}
}
System.out.println("\nSwap / Total comparison : " + scount + " / " + ccount);
System.out.println("\n成績排序結果");
int rank = 1;
for(int i = 0; i < grade.length; i++){
if( i != 0 && grade[i].getGrade() != grade[i-1].getGrade() ){ rank++; }
System.out.println("名次 " + (rank) + " 第 " + grade[i].getSid() + " 號學生成績 " + grade[i].getGrade());
}
}
}
方法二 外層迴圈由右至左, 為限制內層迴圈比較的右邊界. 內層迴圈迴圈由左至右, 相近位置兩兩比較大小.
程式碼
import java.io.*;
class C7P155_1
{
public static void main(String[] args) throws IOException
{
int student_num = 0, maxgr = 0, mingr = 0, maxid = 0, minid = 0, sum = 0, scount = 0, ccount = 0;
boolean status = false;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("學生成績分析程式 ");
do{
System.out.print("請輸入學生人數 ");
try{
student_num = Integer.parseInt(br.readLine());
status = false;
} catch ( NegativeArraySizeException e ){
System.out.println("請輸入正整數的學生人數.");
status = true;
} catch ( NumberFormatException e ){
System.out.println("請輸入學生人數.");
status = true;
}
} while (status);
int grade[] = new int[student_num];
System.out.println("\n開始輸入學生成績");
for(int i = 0; i < student_num; i++){
status = false;
do{
System.out.print("學生 " + (i+1) + " 成績 ");
try{
grade[i] = Integer.parseInt(br.readLine());
sum += grade[i];
if( i == 0 ){
maxgr = mingr = grade[i];
}else{
if(grade[i] > maxgr){
maxgr = grade[i]; maxid = i;
} else if(grade[i] < mingr){
mingr = grade[i]; minid = i;
}
}
status = false;
} catch ( NumberFormatException e ){
System.out.println("請輸入正整數的成績.");
status = true;
}
} while (status);
}
System.out.println("\n開始輸出學生成績");
for(int i = 0; i < grade.length; i++){
System.out.println("學生 " + (i+1) + " 成績 " + grade[i]);
}
System.out.println("\n最高最低成績");
System.out.println("最高成績 第 " + (maxid+1) + " 號學生成績" + grade[maxid]);
System.out.println("最低成績 第 " + (minid+1) + " 號學生成績" + grade[minid]);
System.out.println("\n平均成績 " + (float)sum/(float)grade.length);
System.out.println("\n成績排行榜");
// Generate student id array
int stid[] = new int[grade.length];
for(int i = 0; i < grade.length; i++){ stid[i] = i; }
// Sort by grade via bubble sort
System.out.print("成績排序中 ");
for(int i = grade.length - 1; i > 0; i--){
for(int j = 0; j < i; j++){
if(grade[j+1] > grade[j]){
// swap
int tmpgr = grade[j+1];
int tmpid = stid[j+1];
grade[j+1] = grade[j];
stid[j+1] = stid[j];
grade[j] = tmpgr;
stid[j] = tmpid;
scount++;
System.out.print("s");
} else {
System.out.print(".");
}
ccount++;
}
}
System.out.println("\nSwap / Total comparison : " + scount + " / " + ccount);
System.out.println("\n成績排序結果");
int rank = 1;
for(int i = 0; i < grade.length; i++){
if( i != 0 && grade[i] != grade[i-1] ){ rank++; }
System.out.println("名次 " + (rank) + " 第 " + (stid[i]+1) + " 號學生成績 " + grade[i]);
}
}
}
物件導向版
import java.io.*;
class Student
{
int sid;
int grade;
public void setGrade(int sid, int grade)
{
this.sid = sid;
this.grade = grade;
}
public int getGrade()
{
return this.grade;
}
public int getSid()
{
return this.sid;
}
}
class C8P158_1
{
public static void main(String[] args) throws IOException
{
int student_num = 0, maxgr = 0, mingr = 0, maxid = 0, minid = 0, sum = 0, scount = 0, ccount = 0;
boolean status = false;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("學生成績分析程式 ");
do{
System.out.print("請輸入學生人數 ");
try{
student_num = Integer.parseInt(br.readLine());
status = false;
} catch ( NegativeArraySizeException e ){
System.out.println("請輸入正整數的學生人數.");
status = true;
} catch ( NumberFormatException e ){
System.out.println("請輸入學生人數.");
status = true;
}
} while (status);
Student grade[] = new Student[student_num];
System.out.println("\n開始輸入學生成績");
for(int i = 0; i < student_num; i++){
status = false;
do{
System.out.print("學生 " + (i+1) + " 成績 ");
try{
grade[i] = new Student();
grade[i].setGrade( i + 1, Integer.parseInt(br.readLine()) );
sum += grade[i].getGrade();
if( i == 0 ){
maxgr = mingr = grade[i].getGrade();
}else{
if(grade[i].getGrade() > maxgr){
maxgr = grade[i].getGrade(); maxid = i;
} else if(grade[i].getGrade() < mingr){
mingr = grade[i].getGrade(); minid = i;
}
}
status = false;
} catch ( NumberFormatException e ){
System.out.println("請輸入正整數的成績.");
status = true;
}
} while (status);
}
System.out.println("\n開始輸出學生成績");
for(int i = 0; i < grade.length; i++){
System.out.println("學生 " + grade[i].getSid() + " 成績 " + grade[i].getGrade());
}
System.out.println("\n最高最低成績");
System.out.println("最高成績 第 " + grade[maxid].getSid() + " 號學生成績" + grade[maxid].getGrade());
System.out.println("最低成績 第 " + grade[minid].getSid() + " 號學生成績" + grade[minid].getGrade());
System.out.println("\n平均成績 " + (float)sum/(float)grade.length);
System.out.println("\n成績排行榜");
// Sort by grade via bubble sort
System.out.print("成績排序中 ");
for(int i = grade.length - 1; i > 0; i--){
for(int j = 0; j < i; j++){
if(grade[j+1].getGrade() > grade[j].getGrade()){
// swap
Student tmpgr = grade[j+1];
grade[j+1] = grade[j];
grade[j] = tmpgr;
scount++;
System.out.print("s");
} else {
System.out.print(".");
}
ccount++;
}
}
System.out.println("\nSwap / Total comparison : " + scount + " / " + ccount);
System.out.println("\n成績排序結果");
int rank = 1;
for(int i = 0; i < grade.length; i++){
if( i != 0 && grade[i].getGrade() != grade[i-1].getGrade() ){ rank++; }
System.out.println("名次 " + (rank) + " 第 " + grade[i].getSid() + " 號學生成績 " + grade[i].getGrade());
}
}
}
方法三 方法二的進化版. 將最後交換位置設為 sentinel, 讓比較次數減少.
程式碼
import java.io.*;
class C7P155_2
{
public static void main(String[] args) throws IOException
{
int student_num = 0, maxgr = 0, mingr = 0, maxid = 0, minid = 0, sum = 0, scount = 0, ccount = 0;
boolean status = false;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("學生成績分析程式 ");
do{
System.out.print("請輸入學生人數 ");
try{
student_num = Integer.parseInt(br.readLine());
status = false;
} catch ( NegativeArraySizeException e ){
System.out.println("請輸入正整數的學生人數.");
status = true;
} catch ( NumberFormatException e ){
System.out.println("請輸入學生人數.");
status = true;
}
} while (status);
int grade[] = new int[student_num];
System.out.println("\n開始輸入學生成績");
for(int i = 0; i < student_num; i++){
status = false;
do{
System.out.print("學生 " + (i+1) + " 成績 ");
try{
grade[i] = Integer.parseInt(br.readLine());
sum += grade[i];
if( i == 0 ){
maxgr = mingr = grade[i];
}else{
if(grade[i] > maxgr){
maxgr = grade[i]; maxid = i;
} else if(grade[i] < mingr){
mingr = grade[i]; minid = i;
}
}
status = false;
} catch ( NumberFormatException e ){
System.out.println("請輸入正整數的成績.");
status = true;
}
} while (status);
}
System.out.println("\n開始輸出學生成績");
for(int i = 0; i < grade.length; i++){
System.out.println("學生 " + (i+1) + " 成績 " + grade[i]);
}
System.out.println("\n最高最低成績");
System.out.println("最高成績 第 " + (maxid+1) + " 號學生成績" + grade[maxid]);
System.out.println("最低成績 第 " + (minid+1) + " 號學生成績" + grade[minid]);
System.out.println("\n平均成績 " + (float)sum/(float)grade.length);
System.out.println("\n成績排行榜");
// Generate student id array
int stid[] = new int[grade.length];
for(int i = 0; i < grade.length; i++){ stid[i] = i; }
// Sort by grade via bubble sort
System.out.print("成績排序中 ");
for(int i = grade.length - 1, lastj = grade.length - 1; i > 0; i--){
// For debug
// System.out.print("(" + i + ")[" + lastj + "]");
boolean swapstatus = false;
for(int j = 0; j < i; j++){
if(grade[j+1] > grade[j]){
// swap
int tmpgr = grade[j+1];
int tmpid = stid[j+1];
grade[j+1] = grade[j];
stid[j+1] = stid[j];
grade[j] = tmpgr;
stid[j] = tmpid;
lastj = j;
swapstatus = true;
scount++;
System.out.print("s");
} else {
System.out.print(".");
}
ccount++;
}
if(swapstatus){ i = lastj + 1; } else { break;}
}
System.out.println("\nSwap / Total comparison : " + scount + " / " + ccount);
System.out.println("\n成績排序結果");
int rank = 1;
for(int i = 0; i < grade.length; i++){
if( i != 0 && grade[i] != grade[i-1] ){ rank++; }
System.out.println("名次 " + (rank) + " 第 " + (stid[i]+1) + " 號學生成績 " + grade[i]);
}
}
}
物件導向版
import java.io.*;
class Student
{
int sid;
int grade;
public void setGrade(int sid, int grade)
{
this.sid = sid;
this.grade = grade;
}
public int getGrade()
{
return this.grade;
}
public int getSid()
{
return this.sid;
}
}
class C8P158_2
{
public static void main(String[] args) throws IOException
{
int student_num = 0, maxgr = 0, mingr = 0, maxid = 0, minid = 0, sum = 0, scount = 0, ccount = 0;
boolean status = false;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("學生成績分析程式 ");
do{
System.out.print("請輸入學生人數 ");
try{
student_num = Integer.parseInt(br.readLine());
status = false;
} catch ( NegativeArraySizeException e ){
System.out.println("請輸入正整數的學生人數.");
status = true;
} catch ( NumberFormatException e ){
System.out.println("請輸入學生人數.");
status = true;
}
} while (status);
Student grade[] = new Student[student_num];
System.out.println("\n開始輸入學生成績");
for(int i = 0; i < student_num; i++){
status = false;
do{
System.out.print("學生 " + (i+1) + " 成績 ");
try{
grade[i] = new Student();
grade[i].setGrade( i + 1, Integer.parseInt(br.readLine()) );
sum += grade[i].getGrade();
if( i == 0 ){
maxgr = mingr = grade[i].getGrade();
}else{
if(grade[i].getGrade() > maxgr){
maxgr = grade[i].getGrade(); maxid = i;
} else if(grade[i].getGrade() < mingr){
mingr = grade[i].getGrade(); minid = i;
}
}
status = false;
} catch ( NumberFormatException e ){
System.out.println("請輸入正整數的成績.");
status = true;
}
} while (status);
}
System.out.println("\n開始輸出學生成績");
for(int i = 0; i < grade.length; i++){
System.out.println("學生 " + grade[i].getSid() + " 成績 " + grade[i].getGrade());
}
System.out.println("\n最高最低成績");
System.out.println("最高成績 第 " + grade[maxid].getSid() + " 號學生成績" + grade[maxid].getGrade());
System.out.println("最低成績 第 " + grade[minid].getSid() + " 號學生成績" + grade[minid].getGrade());
System.out.println("\n平均成績 " + (float)sum/(float)grade.length);
System.out.println("\n成績排行榜");
// Sort by grade via bubble sort
System.out.print("成績排序中 ");
for(int i = grade.length - 1, lastj = grade.length - 1; i > 0; i--){
// For debug
// System.out.print("(" + i + ")[" + lastj + "]");
boolean swapstatus = false;
for(int j = 0; j < i; j++){
if(grade[j+1].getGrade() > grade[j].getGrade()){
// swap
Student tmpgr = grade[j+1];
grade[j+1] = grade[j];
grade[j] = tmpgr;
lastj = j;
swapstatus = true;
scount++;
System.out.print("s");
} else {
System.out.print(".");
}
ccount++;
}
if(swapstatus){ i = lastj + 1; } else { break;}
}
System.out.println("\nSwap / Total comparison : " + scount + " / " + ccount);
System.out.println("\n成績排序結果");
int rank = 1;
for(int i = 0; i < grade.length; i++){
if( i != 0 && grade[i].getGrade() != grade[i-1].getGrade() ){ rank++; }
System.out.println("名次 " + (rank) + " 第 " + grade[i].getSid() + " 號學生成績 " + grade[i].getGrade());
}
}
}
測試範例 : 七位學生的成績
範例一 : 1 2 3 4 5 6 7
反轉表
1 2 3 4 5 6 7
0 1 2 3 4 5 6
方法一 : 21/21.
方法二 : 21/21.
方法三 : 21/21.
範例二 : 7 6 5 4 3 2 1
反轉表
1 2 3 4 5 6 7
0 0 0 0 0 0 0
方法一 : 0/21.
方法二 : 0/21.
方法三 : 0/6.
範例三 : 5 7 4 1 6 3 2
反轉表
1 2 3 4 5 6 7
0 1 1 0 0 3 1
方法一 : 6/21.
方法二 : 6/21.
方法三 : 6/14.
範例四 : 1 6 7 4 5 2 3
反轉表
1 2 3 4 5 6 7
0 1 2 1 2 1 2
方法一 : 9/21.
方法二 : 9/21.
方法三 : 9/15.
