箱排序（也稱為桶排序）是一種排序算法，其工作原理是將數組分到有限數量的桶子裡，每個桶子再個別進行排序。這種算法的主要優點是它的時間複雜度可以達到O(n)，尤其是在要被排序的數組內的數值是均勻分配的情況下。箱排序並不是一種比較排序算法，因此不受O(n log n)的下限影響。
箱排序的實現方式有多種，一種簡單的方法是假設待排序數組全為整數，首先遍歷待排序數組，得到該數組中的最大值N，然後創建一個長度為N+1的數組bin，遍歷待排序數組時，遍歷到數組元素i，將bin[i] += 1，最後，數組bin中不為0的位置都為待排序數組中出現過的元素，bin[i]的值代表i在待排序數組中出現過幾次。然後順序遍歷數組bin中不為0的值，令bin[i] -= 1直到bin[i] == 0，並將i順序裝入待排序數組中。
另一種更複雜的實現方式是首先確定桶的個數，將數據均勻地分散到各個桶中，然後對各個桶進行局部的排序，最後再按序將各個桶中的數輸出，即可得到排好序的數。
總的來說，箱排序的排序過程無需比對數值，只需要將遍歷到的數值放到對應的「箱子」里，最後再統計箱子即可，這是一種分配-收集的思想。