基于js 各种排序方法和sort方法的区别(详解)

针对“基于js 各种排序方法和sort方法的区别(详解)”这个话题,我将从以下几个方面进行详细讲解。

一、基础排序算法

在介绍各种排序算法之前,我们先了解一下几个基础排序算法:冒泡排序、插入排序和选择排序。

1. 冒泡排序

冒泡排序的基本思路是比较相邻的元素,如果前面的元素比后面的大,则交换这两个元素。每完成一轮比较,就可以确定一个最大的元素,并且这个最大的元素已经排好序了。时间复杂度为O(n^2)。

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

function bubbleSort(array) {
  const len = array.length;
  for(let i = 0; i < len; i++) {
    for(let j = 0; j < len - i - 1; j++) {
      if(array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

2. 插入排序

插入排序的基本思路是将一个数组分成两个部分,一部分是已经排好序的,另一部分是待排序的。每次取出待排序部分的第一个元素,将它插入到已排序部分的正确位置。时间复杂度为O(n^2)。

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

function insertionSort(array) {
  const len = array.length;
  for(let i = 1; i < len; i++) {
    let j = i - 1;
    const tmp = array[i];
    while(j >= 0 && array[j] > tmp) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = tmp;
  }
  return array;
}

3. 选择排序

选择排序的基本思路是从待排序的数组中找到最小的元素,将它放到已排序数组的末尾。这样每次找到的最小元素都是未排序数组中最小的元素。时间复杂度为O(n^2)。

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

function selectionSort(array) {
  const len = array.length;
  for(let i = 0; i < len; i++) {
    let minIndex = i;
    for(let j = i + 1; j < len; j++) {
      if(array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

二、高级排序算法

高级排序算法包括快速排序、归并排序和堆排序。这些算法的时间复杂度都是O(nlogn)。

1. 快速排序

快速排序的基本思路是选择一个元素作为“基准元素”,然后将数组中的其他元素分别与这个基准元素进行比较,将较小的元素排在基准元素的左边,将较大的元素排在基准元素的右边。然后对基准元素左右的子数组分别进行递归后,再对其进行合并。快速排序的关键在于选取合适的基准元素。时间复杂度为O(nlogn)。

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

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

2. 归并排序

归并排序的基本思路是将数组分成两个部分,对这两个部分分别进行递归,直到每个部分只有一个元素。然后将这些只有一个元素的部分合并起来,并按照从小到大的顺序排列。时间复杂度为O(nlogn)。

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

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

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

3. 堆排序

堆排序的基本思路是利用堆这种数据结构进行排序。首先将数组转化为一个大根堆,然后将堆顶元素与数组末尾元素交换,接着再将前n-1个元素转化为大根堆,再交换堆顶元素与数组末尾元素。如此反复操作直到完成排序。时间复杂度为O(nlogn)。

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

function heapSort(array) {
  const len = array.length;
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(array, len, i);
  }
  for (let i = len - 1; i >= 0; i--) {
    [array[0], array[i]] = [array[i], array[0]];
    heapify(array, i, 0);
  }
  return array;
}

function heapify(array, len, k) {
  let maxIndex = k;
  let left = 2 * k + 1;
  let right = 2 * k + 2;
  if (left < len && array[left] > array[maxIndex]) {
    maxIndex = left;
  }
  if (right < len && array[right] > array[maxIndex]) {
    maxIndex = right;
  }
  if (maxIndex !== k) {
    [array[k], array[maxIndex]] = [array[maxIndex], array[k]];
    heapify(array, len, maxIndex);
  }
}

三、数组的Sort方法

JavaScript数组自带的sort方法可以进行升序排列和降序排列。如果没有指定比较函数,则按照字符串的unicode码进行排序。如果指定了比较函数,那么按照比较函数的规则进行排序。

以下是按照数字大小进行升序排列的JavaScript代码实现:

const array = [3, 1, 4, 2, 5];
array.sort(function(a, b) {
  return a - b;
});
console.log(array); // [1, 2, 3, 4, 5]

以下是按照数字大小进行降序排列的JavaScript代码实现:

const array = [3, 1, 4, 2, 5];
array.sort(function(a, b) {
  return b - a;
});
console.log(array); // [5, 4, 3, 2, 1]

四、各种排序方法和sort方法的区别

除了基础排序算法和高级排序算法之外,还有很多其他的排序算法,比如希尔排序、计数排序、桶排序和基数排序等。这些算法有各自的优缺点和适用场景。而JavaScript数组的sort方法则只能进行升序排列和降序排列。

总体来说,使用JavaScript数组的sort方法比手写排序函数更为简便,因为它已经很好地考虑了各种情况。但如果我们需要掌握各种排序算法的原理和实现方法,还是需要手写排序函数的。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:基于js 各种排序方法和sort方法的区别(详解) - Python技术站

(0)
上一篇 2023年6月11日
下一篇 2023年6月11日

相关文章

  • IE下通过a实现location.href 获取referer的值

    在IE浏览器下,通过a标签可以实现获取referer的值。具体实现步骤如下: 1. 通过a标签实现location.href方法获取referer 在a标签的href属性中添加需要跳转到的URL地址,并在该URL地址后添加“?referer=当前页面的URL地址”,如下所示: <a href="http://www.example.com?r…

    JavaScript 2023年6月11日
    00
  • js与C#进行时间戳转换

    当我们需要在前端应用中与后端应用进行通信时,常常需要用到时间戳。因为各种编程语言对时间的处理方式不同,所以在不同编程语言之间进行通信时需要进行一些数据格式的转换。下面我会提供一些将 JS 时间戳转换成 C# 时间戳的方法和示例。 JS 时间戳转 C# 时间戳格式 JS 中获取时间戳的方式很简单,可以使用 Date.now() 或 new Date().get…

    JavaScript 2023年5月27日
    00
  • javascript最基本的函数汇总

    本文将分享JavaScript最基本的函数汇总,包含函数的定义、调用和返回值等内容。 函数的定义 JavaScript中定义函数非常简单,使用function关键字,并指定函数名、参数列表和函数体。 示例代码: function sayHello(name) { console.log("Hello, " + name); } 上述代码定…

    JavaScript 2023年5月18日
    00
  • 基于原生JavaScript实现SPA单页应用

    基于原生JavaScript实现SPA单页应用攻略 简介 单页应用(Single Page Application,SPA)是一种基于Web浏览器的应用程序,整个应用程序只有一个HTML文件,页面切换时通过ajax与后端进行数据交互,然后动态更新Dom元素,从而实现页面的切换。 原生JavaScript是指不依赖第三方框架或库,只使用纯JavaScript进…

    JavaScript 2023年6月11日
    00
  • JavaScript中this详解

    JavaScript中this详解 介绍 this是JavaScript语言中的一个关键字,表示函数在调用时所在的对象。this的指向是在函数被调用时确定的,而不是在函数被创建时确定的。由于JavaScript中的函数可以在不同的对象上下文中被调用,因此this的指向具有动态性。 this的四种调用方式 1. 作为函数调用 当函数不作为对象的属性,或使用ca…

    JavaScript 2023年5月18日
    00
  • JavaScript编程的10个实用小技巧

    JavaScript编程的10个实用小技巧 JavaScript编程是现代Web开发中不可或缺的一部分。为了更好地利用JavaScript进行编程,我们需要学习许多小技巧,这些小技巧能够帮助我们更加轻松快捷地编写代码。本文将介绍JavaScript编程的10个实用小技巧。 1. 使用模板字面量 在JavaScript中,我们可以使用模板字面量来轻松创建格式化…

    JavaScript 2023年5月18日
    00
  • JS实现数组去重及数组内对象去重功能示例

    JS实现数组去重及数组内对象去重功能示例攻略 在JavaScript中,我们经常会用到数组。但是,数组中如果有重复的元素会影响我们的数据操作,因此我们需要进行数组去重操作。在这篇攻略中,我将向您展示如何使用JavaScript实现数组去重及数组内对象去重功能,希望能帮助您更好地理解和应用JS。 数组去重 方法一:使用Set 使用Set可以很方便地去除数组中的…

    JavaScript 2023年5月27日
    00
  • 50行代码实现贪吃蛇(具体思路及代码)

    下面是详细讲解: 1. 思路概述 本质上,贪吃蛇游戏可以看做经典的“贪心算法”的应用。游戏主要的难点在于掌握如何实现贪心策略,以及如何处理蛇的移动和碰撞。具体思路如下: 定义一个二维数组,建立游戏场地; 在场地上随机放置一个初始“食物”(贪心的目标); 定义蛇的数据结构和初始状态,并将蛇放置在场地上; 接收输入事件(如按键),并将其转换为蛇的运动方向; 按照…

    JavaScript 2023年6月11日
    00
合作推广
合作推广
分享本页
返回顶部