2015年9月23日 星期三

【筆記】用Java來做氣泡排序法的簡單範例

一直以來,想給自己補一下在演算法等基礎的不足,所以就從最基本的排序法開始,希望可以持續下去,XD

下列程式是拜歐依書中的範例改成Java版本的。
package idv.jk.study.algorithm.sort;

import java.util.Scanner;

/**
 * Created by javakid on 15/9/22.
 */
public class BubbleSort
{
    public static void main(String[] args)
    {
        int scores[] = new int[100];
        int size;
        System.out.println("輸入分數的總數...");
        Scanner scanner = new Scanner(System.in);

        size = scanner.nextInt();

        System.out.println("輸入分數(用,隔開)...");
        String strNumbers = scanner.next();

        String numbers[] = strNumbers.split(",");

        //把輸入的數字存入到陣列中
        for(int i = 0; i < numbers.length; i++)
        {
            scores[i] = Integer.parseInt(numbers[i]);
        }

        int temp;   //於大小比對時暫存數字的變數

        //開始對所有數字做排列
        for(int i = 0; i < size; i++)
        {
            //size - i表第2次只要比對size-1個數字,
            // 第3次只要比對size-2個數字,以此類推
            for (int j = 0; j < size - i; j++)
            {
                //由小至大,兩兩比對做數字交換
                if (scores[j] < scores[j+1])
                {
                    temp = scores[j];
                    scores[j] = scores[j+1];
                    scores[j+1] = temp;
                }
            }
        }

        //印出結果
        for(int i = 0; i < size; i++)
        {
            System.out.printf("%d ", scores[i]);
        }
    }
}
重點
  • 若有 n 個數字要進行排多,只需將 n-1 個數字歸位
  • 相鄰的數字比較後,依需要做大小交換
  • 時間複雜度為O(N2)

若真想打好演算法的底子,建議您拜歐正在念的這本:



沒有留言: