//*目的:使用者的輸入做Quick_Sort*/
//*安裝版本:J2SE 5.0 以上*/
//*方法一:Scanner*/
import java.util.Scanner;
//*註解為方法二:BufferedReader*/
//import java.io.BufferedReader;
//import java.io.InputStreamReader;
import java.io.IOException;
//*ex.排序方法
public class Quick_Sort{
//*切割的點也就是取Pivot
private static int partition(int a[],int left,int right){
int i,j,temp,pivot;
i=left+1;
j=right;
pivot=a[left];
do{
while(a[i]<pivot)i++;
while(a[j]>pivot)j--;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
/* 可以做Bug的找碴~XD
System.out.print("Begin\n");
for(int k=0;k<a.length;k++){
System.out.print(a[k] + " ");
}
System.out.print("end\n");
*/
}
}while(i<j);
a[left]=a[j];
a[j]=pivot;
return j;
}
//*排序方法Quick Sort本體
private static void Main_Quick_Sort(int a[],int left,int right){
int mid;
if(left<right){
//*用上個Method找Pivot
mid = partition(a,left,right);
//*邊換邊印給你看結果[*依分割次數]
System.out.print("\n");
for(int k=0;k<a.length;k++){
System.out.print(a[k] + " | ");
}
System.out.print("\n");
Main_Quick_Sort(a,left,mid-1);
Main_Quick_Sort(a,mid+1,right);
}else{
//*我搞笑用~XD
//System.out.print("@");
}
}
//*主執行程式
public static void main(String args[])throws IOException
{
//*要存的陣列宣告a
int b[] = new int[10];
//*讀取輸入值
//BufferedReader br=
// new BufferedReader(new InputStreamReader(System.in));
Scanner scanner = new Scanner(System.in);
System.out.print("1.計算輸入10個值的Quick Sort排序~\n"+
"請輸入(都整數喔!!):");
for(int k=0;k<b.length;k++){
b[k] = scanner.nextInt();
}
//*做銀幕的Check
System.out.println("\n2.原本10個整數順序:");
for(int k=0;k<b.length;k++){
System.out.print(b[k] + " | ");
}
System.out.println("\n\n3.轉換過程:");
//**關鍵底枷啦!!要傳陣列給排序方法做
Main_Quick_Sort(b, 0, b.length-1);
System.out.println("\n4.排序後10個整數順序:");
for(int k=0;k<b.length;k++){
System.out.print(b[k] + " | ");
}
//*System.exit(0);
}
}
沒有留言:
張貼留言