簡單易用的排序—簡單桶排序(Bucket Sort) - 筆記長也NotesHazuya

簡單易用的排序—簡單桶排序(Bucket Sort)

2018-04-03 15:47:28   演算法

桶排序算法分析

概念

桶排序假設要排序的資料在一範圍內分布,將這些資料劃分為數個範圍,也就是桶。並將這些數值放入這些桶當中,再把桶內的資料排序,並將這些桶內排序過的資料取出合併。

複雜度

桶排序的時間複雜度受到了每個桶子排序的時間複雜度所影響,當每個桶內的資料愈少,排序的時間當然也越少。也就是說,當資料被分為較多的桶子時,其所耗費的排序時間越少,但要耗用較多的空間。

穩定度

桶排序是穩定的排序法。

實例

這裡介紹一個簡單桶排序的範例,例如有一資料:[ 2,2,8,9,5 ] 將要被排序(由小至大),我們會建立一個數為10的陣列,如下圖

之後開始進行排序,遇到 2 就將陣列索引 2 的資料內容+1,如下圖

再遇到2就將索引值2再+1

之後以此類推,最後結果如下

總結來說,將資料作為陣列索引值,而陣列的內容則存放該資料的數量,若我們從陣列[0]開始輸出,最後會得到結果[2,2,5,8,9] ,這樣就完成排序了。

Java範例

import java.util.Scanner;

public class Bucket {

    public static void main(String[] args) {
        int[] lv = new int[1001];//表示可以排序0~1000範圍間的資料
        int key = 0;//暫存輸入的資料
        Scanner input = new Scanner(System.in);
        while (key >= 0) {  //輸入負數時結束輸入
            System.out.print("請輸入資料");
            key = input.nextInt();
            if (key <= 1000 && key >= 0) {
                lv[key]++;
            } else if (key > 1000) {
                System.out.println("資料超過範圍");
            }
        }
        //將資料取出
        for (int i = 0; i < lv.length; i++) {
            for (int j = 0; j < lv[i]; j++)//出現幾次就取出幾次
            {
                System.out.printf("%d ", i);
            }
        }
    }

}

這個範例是由小至大,若要大至小,將迴圈改為for(int i = lv.length;i>=0;i--)就好

參考資料

  1. 最快最简单的排序——桶排序
  2. 桶排序(Bucket sort) | Adoo's blog

關於作者


長也

資管菸酒生,嘗試成為網頁全端工程師(laravel / React),技能樹成長中,閒暇之餘就寫一些筆記。 喔對了,也愛追一些劇,例如火神跟遺物整理師,推推。最愛的樂團應該是告五人吧(?)