橙色企业网站,海南建设局相关网站,网站开发基础培训,新网站建设需要什么引入
桶排序#xff0c;顾名思义#xff0c;会用到“桶”#xff0c;核心思想是将要排序的数据分到几个有序的桶里#xff0c;每个桶里的数据再单独进行排序。桶内排完序之后#xff0c;再把每个桶里的数据按照顺序依次取出#xff0c;组成的序列就是有序的了。
桶排序…引入
桶排序顾名思义会用到“桶”核心思想是将要排序的数据分到几个有序的桶里每个桶里的数据再单独进行排序。桶内排完序之后再把每个桶里的数据按照顺序依次取出组成的序列就是有序的了。
桶排序与之前提到的排序的本质区别就是它是不基于比较的排序。 桶排序是一种基于分治思想的排序算法它将数据分布到有限数量的桶中每个桶再分别排序最后按顺序合并。
实现原理 确定桶的数量和范围根据数据的取值范围和数据量计算需要的桶的数量。每个桶代表一个特定的区间范围。 分配数据到桶遍历待排序的数据根据每个数据的值将其分配到相应的桶中。 对每个桶进行排序可以使用其他排序算法如插入排序、快速排序等对每个桶中的数据进行排序。 收集结果按照桶的顺序将所有桶中的数据依次取出合并到一个数组中得到最终的有序结果。
优点 高效对于数据分布均匀的情况桶排序的时间复杂度接近 O(n)。 稳定桶排序是稳定的排序算法能保持相等元素的原始相对顺序。 桶排序的时间复杂度为什么是 O(n) 呢 如果要排序的数据有 n 个我们把它们均匀地划分到 m 个桶内每个桶里就有 kn/m 个元素。每个桶内部使用快速排序时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)因为 kn/m所以整个桶排序的时间复杂度就是 O(n*log(n/m))。 当桶的个数 m 接近数据个数 n 时log(n/m) 就是一个非常小的常量这个时候桶排序的时间复杂度接近 O(n)。 缺点 数据分布要求高如果数据分布不均匀可能导致部分桶过载影响整体效率。 空间消耗大需要额外的空间存储桶对于大规模数据空间复杂度可能较高。
应用场景 数据分布均匀且范围明确当待排序数据分布均匀且范围已知时桶排序能充分利用数据特性实现高效排序。 高效内部排序算法可用若桶内排序可选用计数排序、基数排序等线性时间复杂度的排序算法桶排序的整体效率将显著提升。 对稳定性有要求在需要保持相等元素原始相对顺序的场景中桶排序的稳定性使其成为理想选择。 桶排序看起来很优秀那它是不是可以替代我们之前讲的排序算法呢 答案当然是否定的。实际上桶排序对要排序数据的要求是非常苛刻的。 首先要排序的数据需要很容易就能划分成 m 个桶并且桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后桶与桶之间的数据不需要再进行排序。 其次数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后有些桶里的数据非常多有些非常少很不平均那桶内数据排序的时间复杂度就不是常量级了。在极端情况下如果数据都被划分到一个桶里那就退化为 O(nlogn) 的排序算法了。 桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中数据量比较大内存有限无法将数据全部加载到内存中。 下面我们重点看桶排序思想下的排序计数排序 基数排序 注意 桶排序思想下的排序都是不基于比较的排序时间复杂度为O(N)额外空间负载度O(M)应用范围有限需要样本的数据状况满足桶的划分 计数排序Counting Sort
计数排序计数排序其实是桶排序的一种特殊情况适用于整数或有限范围内的数据排序。当要排序的 n 个数据所处的范围并不大的时候比如最大值是 k我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的省掉了桶内排序的时间。
计数排序只能用在数据范围不大的场景中如果数据范围k比要排序的数据n大很多就不适合用计数排序了。而且计数排序只能给非负整数排序如果要排序的数据是其他类型的要将其在不改变相对大小的情况下转化为非负整数。
代码示例
下面是一个简单的计数排序案例
public void countSort(int[] arr) {// 如果数组为空或长度小于2无需排序直接返回if (arr null || arr.length 2) {return;}// 找出数组中的最大值用于确定计数桶的大小int max Integer.MIN_VALUE;for (int i 0; i arr.length; i) {max Math.max(max, arr[i]);}// 创建计数桶索引代表数字值代表该数字在数组中的出现次数int[] bucket new int[max 1];// 遍历数组统计每个数字的出现次数for (int i 0; i arr.length; i) {bucket[arr[i]]; // 例如如果数组中有数字5那么bucket[5]会增加1}// 根据计数桶中的计数将数字按顺序重新放回原数组int i 0; // 用于跟踪原数组中的当前位置for (int j 0; j bucket.length; j) {// 当前数字为j出现次数为bucket[j]while (bucket[j]-- 0) {arr[i] j; // 将数字j放入原数组的正确位置}}
} 当然我们还可以如下实现
// 计数排序适用于非负整数数组
public void countingSort(int[] a, int n) {if (n 1) return; // 如果数组长度小于等于1无需排序// 查找数组中数据的范围int max a[0];for (int i 1; i n; i) {if (max a[i]) { // 找到数组中的最大值max a[i];}}// 申请一个计数数组 c下标大小从 0 到 maxint[] c new int[max 1];for (int i 0; i max; i) {c[i] 0; // 初始化计数数组为0}// 计算每个元素的个数放入计数数组 c 中for (int i 0; i n; i) {c[a[i]]; // 统计每个元素出现的次数}// 依次累加得到当前元素排序后的位置for (int i 1; i max; i) {c[i] c[i-1] c[i]; // 累加得到每个元素的累计个数}// 创建临时数组 r存储排序之后的结果int[] r new int[n];// 根据计数数组计算排序的关键步骤for (int i n - 1; i 0; --i) { // 逆序遍历原数组int index c[a[i]] - 1; // 获取当前元素在临时数组中的位置r[index] a[i]; // 将元素放入临时数组c[a[i]]--; // 减少计数确保相同元素的位置正确}// 将临时数组的结果拷贝回原数组for (int i 0; i n; i) {a[i] r[i]; // 更新原数组为排序后的结果}
}
假设输入数组为 [3, 6, 4, 1, 3, 4, 1, 4]经过计数排序后 最大值为6计数桶大小为7索引0-6。 计数桶统计结果为 bucket[0] 0 bucket[1] 2 bucket[2] 0 bucket[3] 2 bucket[4] 3 bucket[5] 0 bucket[6] 1 重建数组时按顺序将数字放入原数组 1出现2次写入索引0和1。 3出现2次写入索引2和3。 4出现3次写入索引4、5和6。 6出现1次写入索引7。 排序后的数组为 [1, 1, 3, 3, 4, 4, 4, 6]。
实现原理 确定数据范围找到待排序数据的最大值和最小值确定数据的范围。 创建计数数组创建一个计数数组用于统计每个数据出现的次数。 统计次数遍历待排序数据统计每个数据在计数数组中的出现次数。 重建排序结果根据计数数组中的次数从大到小或从小到大重建排序结果。
优点
线性时间复杂度计数排序的时间复杂度为 O(n k)其中 n 是数据量k 是数据的范围。
稳定计数排序是稳定的排序算法能保持相等元素的原始相对顺序。
缺点
适用范围有限计数排序只适用于整数或有限范围内的数据不适用于负数和浮点数。
空间复杂度高需要额外的空间存储计数数组当数据范围较大时空间复杂度较高。
应用场景
整数排序适用于整数数据的排序尤其是数据范围较小的情况。
字符串排序可以用于固定长度的字符串排序通过字符位来排序。
基数排序Radix Sort
基数排序是一种非比较型整数排序算法它按照数字的每一位进行比较和交换。基数排序的核心思想是将待排序数组分成若干个段然后对每个段进行局部排序。
基数排序对要排序的数据是有要求的需要可以分割出独立的“位”来比较而且位之间有递进的关系如果 a 数据的高位比 b 数据大那剩下的低位就不用比较了。除此之外每一位的数据范围不能太大要可以用线性排序算法来排序否则基数排序的时间复杂度就无法做到 O(n) 了。
代码示例
// 该基数排序方法仅适用于非负数
public void radixSort(int[] arr) {// 如果数组为空或长度小于2无需排序直接返回if (arr null || arr.length 2) {return;}// 调用基数排序的辅助方法传入起始索引、结束索引和最大位数radixSort(arr, 0, arr.length - 1, maxbits(arr));
}// 计算数组中最大值的位数
public int maxbits(int[] arr) {int max Integer.MIN_VALUE; // 初始化最大值for (int i 0; i arr.length; i) {max Math.max(max, arr[i]); // 找出数组中的最大值}int res 0; // 记录最大值的位数while (max ! 0) { // 通过不断除以10来统计位数res;max / 10;}return res; // 返回最大值的位数
}// 对数组的子数组进行基数排序
// arr: 待排序数组
// L: 子数组的起始索引
// R: 子数组的结束索引
// digit: 数组中最大值的位数
public void radixSort(int[] arr, int L, int R, int digit) {final int radix 10; // 基数为10因为使用十进制int i 0, j 0;// 辅助数组用于存储排序过程中的中间结果int[] help new int[R - L 1];// 根据数字的位数循环处理每一位for (int d 1; d digit; d) { // d 表示当前处理的是第几位从低位到高位int[] count new int[radix]; // 计数数组统计当前位各个数字的出现次数// 统计当前位各个数字的出现次数for (i L; i R; i) {j getDigit(arr[i], d); // 获取当前数字的第d位数字count[j];}// 计算计数数组的前缀和用于确定每个数字的位置for (i 1; i radix; i) {count[i] count[i] count[i - 1];}// 将数字按照当前位的大小放入辅助数组for (i R; i L; i--) { // 从右到左遍历原数组保证排序的稳定性j getDigit(arr[i], d); // 获取当前数字的第d位数字help[count[j] - 1] arr[i]; // 将数字放入辅助数组的正确位置count[j]--; // 减少计数确保相同位的数字顺序正确}// 将辅助数组中的有序数字复制回原数组for (i L, j 0; i R; i, j) {arr[i] help[j];}}
}// 获取数字x的第d位上的数字
public int getDigit(int x, int d) {return ((x / ((int) Math.pow(10, d - 1))) % 10); // 例如x123d2返回 2
}
实现原理 确定最大位数找到待排序数据中的最大值确定最大位数。 按位排序从最低位开始按照每一位对数组进行排序。可以使用计数排序或桶排序作为子排序算法。 合并结果按照位数顺序逐步合并排序结果最终得到完全排序的数组。
优点
线性时间复杂度基数排序的时间复杂度为 O(d * (n k))其中 d 是数字中的最大位数n 是数组的长度k 是每一位的取值范围。
稳定基数排序是稳定的排序算法前一位的排序结果在下一位排序中不会改变。
缺点
空间复杂度高需要额外的空间来存储中间结果空间复杂度较高尤其在处理大数据时。
适用范围有限基数排序适合数值或字符串等可以按位操作的数据不适合复杂数据类型。
应用场景
大规模整数排序适用于大规模的整数数据排序尤其是位数不多且取值范围有限的情况。
字符串排序可以用于固定长度的字符串排序通过字符位来排序。
图像处理中的颜色排序基数排序可用于按色彩通道分量进行排序。
排序算法总结 时间复杂度 额外空间复杂度 稳定性 选择排序 O(N^2) O(1) 无 冒泡排序 O(N^2) O(1) 有 插入排序 O(N^2) O(1) 有 归并排序 O(N* logN) O(N) 有 随机快排 O(N* logN) O(logN) 无 堆排序 O(N* logN) O(1) 无 计数排序 O(N) O(M) 有 基数排序 O(N) O(N) 有
不基于比较的排序对样本数据有严格要求不易改写基于比较的排序只要规定好两个样本怎么比大小就可以直接复用基于比较的排序时间复杂度的极限是O(N*logN)时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并
