关于javascript:排序算法桶排序

56次阅读

共计 828 个字符,预计需要花费 3 分钟才能阅读完成。

桶排序 (Bucket Sort),是一种工夫复杂度为 O(n) 的排序。

桶排序的适用范围是,待排序的元素可能 均匀分布在某一个范畴 [MIN, MAX] 之间

很多业务场景是合乎这一场景,待排序的元素在某一范畴内,且是均匀分布的

桶排序须要两个辅助空间:

(1)第一个辅助空间,是桶空间 B;
(2)第二个辅助空间,是桶内的元素链表空间;

总的来说,空间复杂度是 O(n)。

桶排序有两个关键步骤:

(1)扫描待排序数据 A[N],对于元素 A[i],放入对应的桶 X
(2)A[i] 放入桶 X,如果桶 X 曾经有了若干元素,应用插入排序,将 arr[i] 放到桶内适合的地位

桶 X 内的所有元素,是始终有序的;
插入排序是稳固的,因而桶内元素程序也是稳固的;

当 arr[N] 中的所有元素,都依照上述步骤放入对应的桶后,就实现了全量的排序。

桶排序的伪代码是:

bucket_sort(A[N]){
  for i =1 to n{将 A[i]放入对应的桶 B[X];
    应用插入排序,将 A[i]插入到 B[X]中正确的地位;
  }
  将 B[X]中的所有元素,按程序合并,排序结束;
}

举个栗子:

假如待排序的数组均匀分布在 [0, 99] 之间:

{5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22}

能够设定 10 个桶,申请额定的空间 bucket[10] 来作为辅助空间。其中,每个桶 bucket[i] 来寄存 [10*i, 10*i+9] 的元素链表。

上图所示:

(1)待排序的数组为 unsorted[16]
(2)桶空间是 buket[10]
(3)扫描所有元素之后,元素被放到了本人对应的桶里;
(4)每个桶内,应用插入排序,保障始终是有序的;

例如,标红的元素 66, 67, 62 最终会在一个桶里,并且应用插入排序桶内放弃有序。

最终,每个桶依照 秩序输入,排序结束

桶排序 (Bucket Sort),总结:

(1)桶排序,是一种 复杂度为 O(n) 的排序;
(2)桶排序,是一种 稳固的 排序;
(3)桶排序,实用于数据均匀分布在一个区间内的场景;

正文完
 0