JavaScript实现排序算法

╰半橙微兮° 2021-09-20 00:56 341阅读 0赞

#### 前言 ####

排序算法是笔试中经常出现的，提起排序算法就一定要提下算法复杂度和大O表示法，可参考文章 [算法复杂度和大O表示法][O]

#### 冒泡排序 ####

冒泡排序的空间复杂度是 0(n²) 。从运行时间来看，冒泡排序是排序算法中效率最差的一个。冒泡排序是比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

function bubbleSort(arr) { 
          for (let i = 0; i < arr.length - 1; i++) { 
            for (let j = 0; j < arr.length - 1 - i; j++) { 
              if (arr[j] > arr[j + 1]) { 
                swap(arr, j, j + 1)
              }Ï
            }
          }
        }

#### 选择排序 ####

选择排序的复杂度为 O(n²)。选择排序和冒泡排序一样，它包含镶嵌的两个循环，导致了二次方的复杂度。  
选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放到第二位，以此类推。

function swap(arr, a, b) { 
          let temp = arr[a];
          arr[a] = arr[b];
          arr[b] = temp;
          return arr
        }
    
        function selectSort(arr) { 
          for (let i = 0; i < arr.length - 1; i++) { 
            let min = arr[i];
            let minIndex = i;
            for (let j = i; j < arr.length; j++) { 
              if (min > arr[j]) { 
                min = arr[j];
                minIndex = j;
              }
            }
            swap(arr, i, minIndex)
          }
        }

#### 插入排序 ####

插入排序的算法复杂度为 O(n²) 。插入排序每次排一个数组项，以此方式构建最后的排序数组。插入排序的核心思想是局部有变。排序小型数组时，此算法比选择排序和冒泡排序性能好。

function insertSort(arr) {
                var len = arr.length;
                var j, temp;
                for (var i = 1; i < len; i++) {
                    j = i;
                    temp = arr[i];
                    while (i > 0 && arr[j - 1] > temp) {
                        arr[j] = arr[j - 1];
                        j--;
                    }
                    arr[j] = temp
                }
                return arr;
            }

#### 快速排序 ####

快速排序的时间复杂度为O(nlog^n),且性能更好。快速排序采用分治的方法，将原始数组分为较小的数组。

function quickArr(arr) {
        if (arr.length <= 1) {
            return arr;
        }
        var left = [],
            right = [];
        var pIndex = Math.floor(arr.length / 2);
        var p = arr.splice(pIndex, 1)[0];
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] <= p) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        // 递归
        return quickArr(left).concat([p], quickArr(right));
    }

#### 希尔排序 ####

希尔排序是插入排序的一种高效改进版。

以上为比较重要和面试中比较常见的几种排序算法

--------------------

#### 归并排序 ####

#### 堆排序 ####

#### 计数排序 ####

#### 桶排序 ####

#### 基数排序（分布式排序） ####

[O]: https://blog.csdn.net/weixin_42755677/article/details/93631473

发表评论取消回复

表情：

评论列表（有 0 条评论，341人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法的JavaScript实现

冒泡排序 let compare = (n1, n2) => n1 - n2; let bubbleSort = (arr, cmp = compa

刺骨的言语ヽ痛彻心扉/ 2022年08月05日 13:10/ 0 赞/ 153 阅读

相关 JavaScript实现的两种排序算法

想学一点原生的js，闲来无事写的冒泡排序和快速排序，欢迎指正，不喜勿喷。 // 冒泡 function PP(arr){ for( var i =

墨蓝/ 2022年07月13日 03:40/ 0 赞/ 170 阅读

相关 JavaScript 实现3种排序算法

本文讲述了冒泡，插入，快速三大排序算法，个人感觉写的比较清晰，欢迎留言讨论。 / Created by Administrator on 2017/5/26

淡淡的烟草味﹌/ 2022年05月30日 02:37/ 0 赞/ 173 阅读

相关 JavaScript实现选择排序算法对数组进行排序

原理：从数组中找到最大（最小）的数放在数组的开头，在剩下的数中继续找到最大（最小）的数放在已经排序好的序列后面，这样反复寻找，直到数组排序完成。代码： var

柔情只为你懂/ 2022年05月23日 09:45/ 0 赞/ 189 阅读

相关 JavaScript实现插入排序算法

一、插入排序算法原理插入排序是先将数组中的一部分数进行排序，再将数组中的还未排序的数与已排序的数逐一进行比较，每一次比较都判断二者的大小关系，大的数右移，为小的数腾出位

古城微笑少年丶/ 2022年03月02日 15:22/ 0 赞/ 262 阅读

相关 JavaScript实现选择排序算法

一、选择排序原理选择排序是从数组的第一个数开始，和其他元素逐一进行比较，并将最小数放到数组的第一个位置，第一轮比结束。然后从重新排序的数组中的第二个数开始（此时第一个数

小鱼儿/ 2022年03月02日 13:30/ 0 赞/ 298 阅读

相关 JavaScript实现冒泡排序算法

一、冒泡排序冒泡排序是一种非常基础的排序方法，其原理就是从把一个数组中的每一个数从前往后依次进行比较，然后根据大小交换位置，每一轮的比较都确定出一个当轮比较的最大值，最

た入场券/ 2022年03月02日 11:24/ 0 赞/ 235 阅读

相关 javascript实现希尔排序算法

希尔排序是一种高级的排序算法，接下来我们将使用JS对希尔排序进行实现。 1、准备10000个取值在0~10000之间的随机整数集 var arr = [];

落日映苍穹つ/ 2022年03月01日 06:28/ 0 赞/ 207 阅读

相关 JavaScript实现排序算法

前言排序算法是笔试中经常出现的，提起排序算法就一定要提下算法复杂度和大O表示法，可参考文章 [算法复杂度和大O表示法][O] 冒泡排序冒泡排序的空间复杂度是

╰半橙微兮°/ 2021年09月20日 00:56/ 0 赞/ 342 阅读

相关 javascript-排序算法

插入排序 ![da44baba996d9c4e8ddeb43a01c2139d][] 算法描述： 1. 从第一个元素开始，该元素可以认为已经被排序 2. 取

分手后的思念是犯贱/ 2021年09月14日 01:36/ 0 赞/ 282 阅读