桶排序
本文转载:https://mp.weixin.qq.com/s/r8mArZzAJ-uC002z48HWJw
桶排序的适用范围是,待排序的元素能够均匀分布在某一个范围[MIN, MAX]之间。
桶排序需要两个辅助空间:
-
第一个辅助空间,是桶空间B
-
第二个辅助空间,是桶内的元素链表空间
总的来说,空间复杂度是O(n)。
桶排序有两个关键步骤:
-
扫描待排序数据A[N],对于元素A[i],放入对应的桶X
-
A[i]放入桶X,如果桶X已经有了若干元素,使用插入排序,将arr[i]放到桶内合适的位置
画外音:
(1)桶X内的所有元素,是一直有序的;
(2)插入排序是稳定的,因此桶内元素顺序也是稳定的;
当arr[N]中的所有元素,都按照上述步骤放入对应的桶后,就完成了全量的排序。
桶排序的伪代码是:
bucket_sort(A[N]){
for i =1 to n{
将A[i]放入对应的桶B[X];
使用插入排序,将A[i]插入到B[X]中正确的位置;
}
将B[X]中的所有元素,按顺序合并,排序完毕;
}
桶排序(Bucket Sort),总结:
-
桶排序,是一种复杂度为O(n)的排序
-
桶排序,是一种稳定的排序
-
桶排序,适用于数据均匀分布在一个区间内的场景