【JS 排序算法】

排序算法

    • 冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 堆排序
    • 计数排序
    • 桶排序
    • 基数排序

冒泡排序

冒泡排序是一种简单的排序算法,它的基本思想是重复地比较相邻两个元素的大小,并交换它们,直到整个序列都有序为止。冒泡排序的时间复杂度为 O(n^2)。

下面是 JavaScript 中实现冒泡排序的代码:

function bubbleSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换相邻两个元素的值
      }
    }
  }
  return arr;
}

在这个代码中,我们使用了两个循环来遍历整个数组。外层循环控制比较轮数,内层循环控制每轮比较的次数。每次内层循环比较相邻两个元素的大小,并交换它们的位置,这样可以保证每轮循环之后,最大的元素都被移到了数组的最后面。最终,整个数组都会被排序好,我们将它返回即可。

使用示例:

let arr = [3, 1, 6, 2, 9, 4, 0, 5];
bubbleSort(arr); // [0, 1, 2, 3, 4, 5, 6, 9]

选择排序

选择排序(Selection Sort)是一种简单直观的排序算法,其基本思想是在待排序的元素中选出最小(或最大)的一个元素,与序列最左侧的元素交换位置,然后再从剩余未排序的元素中继续寻找最小(或最大)的元素,重复以上操作直到整个序列有序。

以下是选择排序的详细实现过程:

1.首先,我们找到数组中最小的元素。

2.其次,将最小元素和数组的第一个元素交换位置。

3.接着,在剩余的元素中找到最小元素,将其与数组的第二个元素交换位置。

4.重复以上步骤,一直到数组排序完成。

JavaScript实现代码如下:

function selectionSort(arr) {
  var len = arr.length;
  var minIndex, temp;
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) { // 找到更小的数,更新最小值的下标
        minIndex = j;
      }
    }
    temp = arr[i]; // 将最小值交换到当前位置
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

下面是一个使用选择排序的例子:

var arr = [64, 25, 12, 22, 11];
console.log(selectionSort(arr)); // [11,12,22,25,64]

选择排序是一种简单有效的排序算法,虽然它的时间复杂度为O(n^2),但是在小规模数据的排序中相对于其他高级排序算法具有一定的优势。

插入排序

插入排序是一种基本的排序算法,其基本思想是将待排序的元素插入到已经有序的数组中,以达到排序的目的。下面是 js 插入排序的详解。

  1. 算法步骤

插入排序的基本思路是,将待排序的元素插入到已经排好序的数组中,因此,插入排序的算法步骤如下:

  1. 将待排序的数组分为两个区间:已排序区间和待排序区间。

  2. 初始时,已排序区间只有一个元素,即数组的第一个元素。

  3. 将待排序区间的第一个元素插入到已排序区间的适当位置(如有必要,已排序区间需要将插入位置之后的元素后移)。

  4. 重复步骤 3,直到待排序区间中的所有元素都插入到已排序区间中。

  5. js 代码实现

以下是使用 js 实现插入排序的代码:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // 将当前元素插入到已排序区间的适当位置
    let j = i;
    while (j > 0 && arr[j] < arr[j - 1]) {
      [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      j--;
    }
  }
  return arr;
}

// 示例:
let arr = [3, 1, 5, 7, 2, 4, 9, 6];
console.log(insertionSort(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 9]
  1. 算法分析

插入排序算法的时间复杂度为 O(n^2)。虽然插入排序算法的时间复杂度不是最优的,但是它具有以下几个优点:

  1. 算法思路简单,易于理解和实现。
  2. 当待排序的元素数量比较少时(如少于 10 个),插入排序算法的效率比较高。
  3. 插入排序算法是稳定的,即排序前相同的元素,在排序后仍然保持相同的顺序。

希尔排序

希尔排序是一种改进的插入排序算法,也称缩小增量排序,它首先将数组分为若干子数组,然后对每个子数组进行插入排序,最后对整个数组进行一次插入排序。具体来说,希尔排序是通过将间隔 h 不断缩小进行插入排序的一种算法。

假设待排序的数组为 arr,希尔排序的实现过程如下:

  1. 确定初始步长 h,一般取数组长度的一半,然后将数组分为 h 个子数组。

  2. 分别对每个子数组进行插入排序,即将子数组中的元素按照从小到大的顺序进行排序。

  3. 将步长 h 缩小为原来的一半,重新分为 h/2 个子数组。

  4. 重复步骤 2 和 3,直到步长为 1,即整个数组变为一个子数组。

  5. 对整个数组进行一次插入排序,排序完成。

希尔排序的时间复杂度取决于步长序列的选择,一般情况下可以选择以下步长序列:

  1. Knuth 序列:h = 1, 4, 13, 40, …,其时间复杂度为 O(n^(3/2))。

  2. Hibbard 序列:h = 1, 3, 7, 15, …,其时间复杂度为 O(n^(3/2))。

  3. Sedgewick 序列:h = 1, 5, 19, 41, 109, …,其时间复杂度为 O(n^(4/3))。

希尔排序的优点是相较于冒泡排序、选择排序等简单排序算法更加高效,适用于大规模数据的排序。但是其实现过程比较复杂,需要对步长序列的选择进行优化,否则可能导致性能的下降。

归并排序

归并排序是一种基于分治思想的排序算法。它将问题分解成小问题,通过递归求解小问题,然后将小问题的解合并成大问题的解。具体实现过程如下:

  1. 将待排序数组分为两个子数组,分别对这两个子数组进行递归排序,直到子数组长度为 1 或 0。
  2. 合并两个已排好序的子数组。合并的过程中,将每个子数组的首元素进行比较,将较小的元素放入新的数组中,并将对应子数组的指针向后移动一位。当其中一个子数组的指针移动到末尾时,将另一个子数组的剩余元素直接拷贝到新的数组中。
  3. 返回合并后的数组作为结果。

JavaScript 代码实现:

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  while (i < left.length) {
    result.push(left[i++]);
  }
  while (j < right.length) {
    result.push(right[j++]);
  }
  return result;
}

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  left = mergeSort(left);
  right = mergeSort(right);
  return merge(left, right);
}

这里定义了两个函数,merge 函数用来合并两个已排好序的子数组,mergeSort 函数是递归函数,用来排序整个数组。函数的实现过程与上面提到的算法思想一致。

快速排序

快速排序是一种常见的排序算法,它采用了分治的思想,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再利用递归的方式将这两部分数据分别进行快速排序,最终达到整个序列有序的效果。在实现中,我们需要选取一个基准元素,一般选择第一个或最后一个元素作为基准,将序列中比基准元素小的放在左边,比基准元素大的放在右边,再递归地对左右两部分数据进行排序。

以下是 JavaScript 实现快速排序的代码:

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

代码解释:

  1. 对于长度不超过 1 的数组,直接返回。
  2. 选择数组的中间元素作为基准元素 pivot。
  3. 将除了 pivot 以外的元素分为左右两个数组,左边的元素小于 pivot,右边的元素大于等于 pivot。
  4. 将左右两部分数据分别递归进行快速排序,并将左右数组和 pivot 拼接起来返回。

使用示例:

const arr = [6, 5, 3, 1, 8, 7, 2, 4];
const sortedArr = quickSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6, 7, 8]

堆排序

堆排序(Heap Sort)是一种树形选择排序算法,它是把无序数组构建成二叉堆,利用堆的特性进行排序的一种算法。堆的结构分为大根堆和小根堆。在堆中,最大的元素总是位于根节点。

堆排序的基本思想是:利用堆结构的特点(即大/小根堆)依次将堆顶元素与堆底元素交换位置并调整堆结构,这样,最后得到的就是一个有序序列了。

具体步骤如下:

  1. 构建堆:将无序数组构建成二叉堆,具体实现过程是从最后一个非叶子节点开始,依次将子树调整为堆,直到根节点。

  2. 堆排序:依次将堆顶元素与堆底元素交换位置,并调整堆结构,使得剩余元素仍然构成堆。重复执行该步骤,直到所有元素都有序。

JavaScript 实现代码如下:

function heapSort(arr) {

  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  function heapify(arr, n, i) {
    let largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) {
      largest = l;
    }

    if (r < n && arr[r] > arr[largest]) {
      largest = r;
    }

    if (largest != i) {
      swap(arr, i, largest);
      heapify(arr, n, largest);
    }
  }

  function buildHeap(arr) {
    let n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }
  }

  buildHeap(arr);
  for (let i = arr.length - 1; i >= 0; i--) {
    swap(arr, 0, i);
    heapify(arr, i, 0);
  }

  return arr;
}

// Example
let arr = [5, 3, 8, 4, 2];
let sortedArr = heapSort(arr);
console.log(sortedArr); // [2, 3, 4, 5, 8]

计数排序

计数排序是一种非比较排序算法,它适用于待排序序列中元素范围较小的情况。计数排序的主要思想是,统计待排序序列中每个元素出现的次数,然后根据元素出现的次数,输出排序后的序列。

具体的实现步骤如下:

  1. 找出待排序序列中最大值和最小值,确定元素的取值范围。

  2. 根据取值范围创建一个计数数组count,count[i]表示待排序序列中i出现的次数。

  3. 遍历待排序序列,统计每个元素出现的次数,记录在count数组中。

  4. 根据count数组中的计数信息,对待排序序列进行排序。

  5. 输出排序后的序列。

下面是JavaScript实现代码:

function countSort(arr) {
  // 找出待排序序列中最大值和最小值,确定元素的取值范围
  const maxValue = Math.max(...arr);
  const minValue = Math.min(...arr);
  const len = maxValue - minValue + 1;

  // 根据取值范围创建一个计数数组count
  const count = new Array(len).fill(0);

  // 统计每个元素出现的次数,记录在count数组中
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - minValue]++;
  }

  // 根据统计信息,对待排序序列进行排序
  let sortedIndex = 0;
  for (let i = 0; i < len; i++) {
    while (count[i] > 0) {
      arr[sortedIndex++] = i + minValue;
      count[i]--;
    }
  }

  return arr;
}

// 测试
const arr = [3, 1, 6, 2, 7, 2, 8, 4];
console.log(countSort(arr)); // [1, 2, 2, 3, 4, 6, 7, 8]

上述代码中,我们先找出待排序序列中的最大值和最小值,然后创建一个计数数组count,其中数组的长度为最大值和最小值之差加一。接着,我们遍历待排序数组,统计每个元素出现的次数,并记录在count数组中。最后,我们根据count数组中的统计信息,对待排序序列进行排序。排序完毕后,返回排序后的序列。

桶排序

桶排序是一种排序算法,它的基本思想是将待排序的元素分配到有限数量的桶中,然后对桶中元素进行排序,最后按照顺序将各个桶中元素依次排列得到排序结果。

以下是 JavaScript 实现桶排序的代码:

function bucketSort(arr, bucketSize) {
  if (arr.length === 0) {
    return arr;
  }

  let i;
  let minValue = arr[0];
  let maxValue = arr[0];
  for (i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i];
    } else if (arr[i] > maxValue) {
      maxValue = arr[i];
    }
  }

  // 桶数量
  let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  let buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  // 将元素分配到桶中
  for (i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  }

  // 对每个桶中的元素进行排序
  arr.length = 0;
  for (i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]);
    for (let j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }

  return arr;
}

function insertionSort(arr) {
  let len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}

该实现中使用了插入排序算法对每个桶中的元素进行排序。这是因为桶排序的时间复杂度取决于对每个桶中元素的排序算法,插入排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2),但由于每个桶中的元素数量不超过 b u c k e t S i z e bucketSize bucketSize,所以插入排序是比较理想的选择。不过也可以使用其他的排序算法,比如快速排序或归并排序,以提高桶排序的效率。

基数排序

基数排序是一种非比较排序算法,适用于对整数进行排序。它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别进行排序。这个过程从低位到高位进行,也就是说,先排最低位,再排次低位,直到排完最高位。

以下是基数排序的 JavaScript 实现:

function radixSort(arr) {
  const maxNum = Math.max(...arr);
  let divisor = 1; // 除数,用于求每位的数字
  while (divisor <= maxNum) {
    const buckets = Array.from({ length: 10 }, () => []); // 10 个桶,用于存放每位数字相同的数字
    for (let i = 0; i < arr.length; i++) {
      const digit = Math.floor((arr[i] / divisor) % 10); // 求出当前数字的对应位数上的数字
      buckets[digit].push(arr[i]); // 将数字放入对应的桶中
    }
    arr = [].concat(...buckets); // 合并桶中的数字,组成新的 arr 数组
    divisor *= 10; // 将除数乘以 10,求下一位数字
  }
  return arr;
}

该实现中,我们先求出数组中的最大值,然后定义一个变量 divisor,初值为 1,每轮循环 divisor 都会乘以 10,这样可以依次求出数字的个位、十位、百位等等。在每轮循环中,我们创建 10 个桶,用于存放数字。我们将每个数字放入对应的桶中,最后将所有桶中的数字按顺序依次合并,组成新的数组。经过多轮的循环和桶的合并,我们就得到了有序的数组。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/66373.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【源码编译并安装RocketMQ Dashboard】

【源码编译并安装RocketMQ Dashboard】 一、环境说明二、源码编译并执行三、小结 一、环境说明 安装环境&#xff1a;虚拟机VMWare Centos7.6 Maven3.6.3 JDK1.8已经安装了RocketMQ-5.1.3 单Master集群&#xff0c;且使用Local模式部署&#xff0c;即Broker和Proxy同进程部署…

springcloud3 bus+springconfig 实现配置文件的动态刷新(了解)

一 springcloud Bus的作用 1.1 springcloud的作用 spring cloud bus是用来将分布式系统的节点与轻量级消息系统链接起来的框架。 它整合了java的事件处理机制和消息中间件的功能。其中目前支持RabbitMQ和kafka 简介&#xff1a; bus实现多个服务的配置文件动态刷新。 1.2 …

Pytorch Tutorial【Chapter 3. Simple Neural Network】

Pytorch Tutorial【Chapter 3. Simple Neural Network】 文章目录 Pytorch Tutorial【Chapter 3. Simple Neural Network】Chapter 3. Simple Neural Network3.1 Train Neural Network Procedure训练神经网络流程3.2 Build Neural Network Procedure 搭建神经网络3.3 Use Loss …

网络基本概念

目录 一、IP地址 1. 概念 2. 格式 3. 特殊IP 二、端口号 1.概念 2. 格式 3.注意事项 三、 协议 1. 概念 2. 作用 四、协议分层 1. 网络设备所在分层 五、封装与分用 六、客户端和服务器 1. 客户端与服务器通信的过程 一、IP地址 1. 概念 IP地址主要用于标识网络主机.其他网络…

linux系统虚拟主机开启支持Swoole Loader扩展

特别说明&#xff1a;只是安装支持Swoole扩展&#xff0c;主机并没有安装服务端。目前支持版本php5.4-php7.2。 1、登陆主机控制面板&#xff0c;找到【远程文件下载】这个功能。 2、远程下载文件填写http://download.myhostadmin.net/vps/SwooleLoader_linux.zip 下载保存的路…

跳表与Redis

跳表原理 跳表是Redis有序集合ZSet底层的数据结构 首先有一个头结点 这个头结点里面的数据是null 就是他就是这个链表的最小值 就算是Math.Min也比它大 然后我们新建一个节点的时候是怎么操作的呢 先根据参数(假如说是5)创建一个节点 然后把它放在对应位置 就是找到小于他的最…

web安全漏洞

1.什么是Web漏洞 WEB漏洞通常是指网站程序上的漏洞&#xff0c;可能是由于代码编写者在编写代码时考虑不周全等原因而造成的漏洞。如果网站存在WEB漏洞并被黑客攻击者利用&#xff0c;攻击者可以轻易控制整个网站&#xff0c;并可进一步提前获取网站服务器权限&#xff0c;控制…

【Winform学习笔记(五)】引用自定义控件库(dll文件)

引用自定义控件库dll文件 前言正文1、生成dll文件2、选择工具箱项3、选择需要导入的dll文件4、确定需要导入的控件5、导入及使用 前言 在本文中主要介绍 如何引用自定义控件库(dll文件)。 正文 1、生成dll文件 通过生成解决方案 或 重新生成解决方案 生成 dll 文件 生成的…

探索ES高可用:滴滴自研跨数据中心复制技术详解

Elasticsearch 是一个基于Lucene构建的开源、分布式、RESTful接口的全文搜索引擎&#xff0c;其每个字段均可被索引&#xff0c;且能够横向扩展至数以百计的服务器存储以及处理TB级的数据&#xff0c;其可以在极短的时间内存储、搜索和分析大量的数据。 滴滴ES发展至今&#xf…

element-ui 表格el-table的列内容溢出省略显示,鼠标移上显示全部和定制样式

1、在对应列加上省略显示show-overflow-tooltip属性&#xff0c;如果加上这属性&#xff0c;鼠标移上还是没效果&#xff0c;要考滤是不是层级的原因&#xff0c;被其他挡住了。 :deep(.el-tooltip){position: relative;z-index:9; } <el-table-column label"用款渠…

java静默打印PDF(可实现生产环境下服务器写入PDF模板,然后调用客户端打印机打印)

java静默打印PDF可实现生产环境下服务器写入PDF模板&#xff0c;然后调用客户端打印机打印 一、简需求实现步骤 二、代码实现0、打印模板1、服务器部分 &#xff08;端口&#xff1a;8090&#xff09;1.1、maven依赖1.2、实体1.2.1、接口返回类1.2.2、标签纸页面参数类1.2.3、P…

Spring集成Web

目录 1、简介 2、监听器 3、Spring提供的listener 3.1、xml 3.2、配置类 3.3、WebApplicationContextUtils 3.4、说明 4、自己复现的listener 4.1、ContextLoaderListener 4.2、WebApplicationContextUtils 4.3、Web调用 ⭐作者介绍&#xff1a;大二本科网络工程专业…

《Linux运维实战:Docker基础总结》

一、简介 1、docker的基本结构是什么&#xff0c;包含哪些组件&#xff1f; docker的基本机构是c/s模式&#xff0c;即客户端/服务端模式。 由docker客户端和docker守护进程组成。docker客户端通过命令行或其它工具使用docker sdk与docker守护进程通信&#xff0c;发送容器管理…

Add-in Express for Microsoft Office and Delphi Crack

Add-in Express for Microsoft Office and Delphi Crack 适用于Microsoft Office和Delphi VCL的Add-in Express使您能够在几次点击中为Microsoft Office开发专业插件。它生成基于COM的项目&#xff0c;这些项目包含Microsoft Office外接程序或智能标记的所有必要功能&#xff0…

React实现关键字高亮

先看效果&#xff1a; 实现很简单通过以下这个函数&#xff1a; highLight (text, keyword ) > {return text.split(keyword).flatMap(str > [<span style{{ color: red, fontWeight: bold }}>{keyword}</span>, str]).slice(1);}展示某段文本时调用该函数…

Matlab进阶绘图第25期—三维密度散点图

三维密度散点图本质上是一种特征渲染的三维散点图&#xff0c;其颜色表示某一点所在区域的密度信息。 除了作图&#xff0c;三维密度散点图绘制的关键还在于密度的计算。 当然&#xff0c;不管是作图还是密度的计算&#xff0c;这些在《Matlab论文插图绘制模板》和《Matlab点…

k8s资源管理方法详解(陈述式、声明式)

目录 一&#xff1a;陈述式资源管理方法 二&#xff1a; 基本信息查看 1、查看信息 2、创建 3、删除 4、service 的 type 类型 三&#xff1a;项目实例 1、创建 kubectl create命令 2、发布 kubectl expose命令 3、在 node 节点上操作&#xff0c;查看负载均衡端…

Celery嵌入工程的使用

文章目录 1.config 1.1 通过app.conf进行配置1.2 通过app.conf.update进行配置1.3 通过配置文件进行配置1.4 通过配置类的方式进行配置2.任务相关 2.1 任务基类(base)2.2 任务名称(name)2.3 任务请求(request)2.4 任务重试(retry) 2.4.1 指定最大重试次数2.4.2 设置重试间隔时间…

Mac终端利器:Homebrew + iTerm2 + Oh My Zsh 教程

引言 前段时间调整了一下 iTerm2 的环境&#xff0c;感觉比以前好看多了&#xff0c;并且更加高效&#xff0c;这里做一个记录&#xff0c;希望能给大家一些启发。 工具介绍 brew&#xff1a;Mac OS 下强大的包管理工具。iTerm2&#xff1a;iTerm2是 Mac OS 终端的替代品&am…

Detecting Everything in the Open World: Towards Universal Object Detection

1. 论文简介 论文题目《Detecting Everything in the Open World: Towards Universal Object Detection》发表情况&#xff0c;CVPR2023[论文地址][https://arxiv.org/pdf/2303.11749.pdf][代码地址][https://github.com/zhenyuw16/UniDetector] 2.背景与摘要 本文旨在解决通…
最新文章