- 作者:老汪软件技巧
- 发表时间:2024-09-25 17:01
- 浏览量:
希尔排序
原理:希尔排序就是按照一定的gap值,不断地对数组进行插入排序。不一样的希尔排序算法可能采用不一样的gap值。经典希尔算法的gap值为N/2, N/4, ......直到gap值为1,这里的N为数组的长度。
希尔排序是一种插入排序的算法,它是对简单的插入排序进行改进后,更高效的版本。
优势:
劣势:
实现:
function shellSort (arr) {
let len = arr.length;
let gap = parseInt(len / 2);
while (gap) {
//从第gap个元素开始遍历
for (let i = gap; i < len; i++) {
// 逐步和前面其他的组成员进行比较和交换
for (let j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
};
};
};
gap = parseInt(gap / 2);
};
};
};
堆排序
原理:堆排序可以认为是选择排序的改进版,像选择排序一样将数组划分为已排序和待排序,它的核心是先建堆,再排序。
什么是堆,堆是满足下几点的完全二叉树:
除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列
堆可以用一个数组表示,给定最后一个非叶子节点的下标i( i = Math.floor(array.length / 2) - 1) ,那么左子节点为A[2i+1],右子节点为A[2i+2]。
优势:
劣势:
实现:
function heapSort(arr){
const len = arr.length;
if(len <= 1) return arr; // 如果数组长度为1,直接返回
buildMaxHeap(arr);//构建一个大顶堆
// 调整为大顶堆后,顶元素为最大元素并与末尾元素交互
while(len > 0) {// 当len<=0时,说明已经到堆顶
[arr[0], array[len - 1]] = [arr[len - 1], arr[0]]; // 交换
len--; // 交换之后相当于把树中的最大值弹出去了,所以length--
adjustHeap(arr, 0, len); // 交换值并剔除了最大值后,继续进行调整使之再次成为大顶堆
};
return arr;
};
// 将原数组调整为一个对应数组的大顶堆
function buildMaxHeap(arr) {
// 大顶堆的构建是从最后一个非叶子节点开始,从下往上,从右往左调整
// 最后一个非叶子节点的位置:Math.floor(arr.length/2) - 1
for(let i = Math.floor(arr.length/2) - 1; i >= 0; i--;) {
adjustHeap(arr, i, arr.length);
};
};
/**
* 调整
* @param i 最后一个非叶子节点
* @param length 数组的长度
*/
function adjustHeap(arr, i, len) {
const maxIndex = i;// 最大值索引
const left = i * 2 + 1; // 左子节点索引
const right = i * 2 + 2;// 右子节点索引
// 判断是否有子节点,再比较父节点和左右子节点的大小
// 因为i是最后一个非叶子节点,所以如果有左右子节点则节点的位置都小于数组的长度
if(left < len && arr[left] > arr[maxIndex] {//若左子节点比父节点大
maxIndex = left;
};
if(right < len && arr[right] > arr[maxIndex]){//若右子节点比父节点大
maxIndex = right;
};
if(maxIndex != i) {
[arr[maxIndex],arr[i]] = [arr[i], arr[maxIndex]];
adjustHeap(arr, maxIndex, len); //交换之后递归再次调整比较
};
};
桶排序
原理:
优势:
缺点:
实现:
值得注意的是,桶的个数是人为指定的,不随着数组大小和数值大小改变(可以根据文件大小和内存大小,得到桶的个数)。
function bucketSort(arr, bucketSize = 5){
if(arr.length <= 1) return arr;
const buckets = createBuckets(arr, bucketSize);// 创建桶并将元素分布到不同的桶中
return sortBuckets(buckets);
};
function createBuckets(arr, bucketSize){// bucketSize 表示桶的数量
const maxValue = Math.max(...arr);
const minValue = Math.min(...arr);
const bucketCount = Math.ceil((maxValue - minValue) / bucketSize);// 桶排序的第一个重要步骤是计算每个桶中需要分布的元素个数
const buckets = [];
for(let i = 0; i < bucketCount; i++) {
buckets[i] = [];// 将每个桶置空初始化
};
for(let i = 0; i< arr.length; i++) {
const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);//计算要将元素放到哪个桶中
buckets[bucketIndex].push(arr[i]);
};
return buckets
}
// 利用插入排序方法对每个桶进行排序
function sortBuckets(buckets){
const sortArr = [];
for(let i = 0; i < buckets.length; i++){
sortArr.push(...insertSort(buckets[i]));
};
};
计数排序
原理:将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
时间复杂度上是O(n + k); 其中k代表着数组最大值 - 最小值的差;这意味着计数排序适合什么时候使用呢?当然是数值越接近的数组越适合用计数排序。
优势:
劣势:
数据范围很大,比较稀疏,会导致辅助空间很大,造成空间的浪费
实现:
function countingSort(arr){
const maxValue = Math.max(...arr);
const minValue = Math.min(...arr);
const counts = new Array(maxValue - minValue + 1);//创建计数数组
// 生成计数数组
arr.forEach((item,index) => {
if(!counts[item]) {
counts[item] = 0;
};
counts[item]++;
});
// 开始排序数组,由于是最大值有多大,索引就有多大,所以对应的i即为原数组arr对应的值
let sortIndex = 0;
counts.forEach((count, i)=>{
while(count > 0) {
arr[sortIndex++) = i;
count--;
};
});
return arr;
};
基数排序
原理:将整数按位数切割成不同的数字, 然后按每个位数分别比较。即将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
优势:
劣势:
在某个数字可能很大的时候,基数排序没有任何性能上的优势,还会浪费非常多的内存。
实现:非负整数+升序
function radixSort(arr) {
// 获取数组中最大整数的位数
const max = Math.max(...arr);
const maxDigits = max === 0? 1 : Math.floor(Math.log10(max)) + 1;
// 基数排序循环
for (let i = 0; i < maxDigits; i++) {
const buckets = Array.from({ length: 10 }).map(() => []);
// 分配
for (const num of arr) {
// 获取数字的指定位数上的数字
const dest = Math.floor(((num / Math.pow(10, i)) % 10));
buckets[dest].push(num);
};
// 收集
let pos = 0;
for (const bucket of buckets) {
for (const num of bucket) {
arr[pos++] = num;
};
};
};
return arr;
};