JS数据结构与算法_排序和搜索算法

写在前面

这是《学习JavaScript数据结构与算法》的最后一篇博客，也是在面试中常常会被问到的一部分内容：排序和搜索。在这篇博客之前，我每每看到排序头就是大的，心里想着类似“冒泡排序，两层遍历啪啪啪“就完事了，然后再也无心去深入研究排序相关的问题了。如果你也有类似的经历，希望下面的内容对你有一定帮助

一、准备

在进入正题之前，先准备几个基础的函数

（1）交换数组两个元素

function swap(arr, sourceIndex, targetIndex) {  
  let temp = arr[sourceIndex];  
  arr[sourceIndex] = arr[targetIndex];  
  arr[targetIndex] = temp;  
} 

（2）快速生成0~N的数组 可点击查看更多生成方法

function createArr(length) {  
  return Array.from({length}, (_, i) => i);  
} 

（3）洗牌函数

洗牌函数可快速打乱数组，常见的用法如切换音乐播放顺序

function shuffle(arr) {  
  for (let i = 0; i < arr.length; i += 1) {  
    const rand = Math.floor(Math.random() * (i + 1));  
    if (rand !== i) {  
      swap(arr, i, rand);  
    }  
  }  
  return arr;  
} 

二、排序

常见排序算法可以分为两大类：

•  比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序
•  非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

在本篇博客中，仅对比较类排序的几种排序方式进行学习介绍

2.1 冒泡排序

冒泡排序是所有排序算法中最简单的，通常也是我们学习排序的入门方法。但是，从运行时间的角度来看，冒泡排序是最差的一种排序方式。

核心：比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因而得名

注意：第一层遍历找出剩余元素的最大值，至指定位置【依次冒泡出最大值】

代码：

function bubbleSort(arr) {  
  const len = arr.length;  
  for (let i = 0; i < len; i += 1) {  
    for (let j = 0; j < len - 1 - i; j += 1) {  
      if (arr[j] > arr[j + 1]) { // 比较相邻元素  
        swap(arr, j, j + 1);  
      }  
    }  
  }  
  return arr;  
} 

2.2 选择排序

选择排序是一种原址比较排序算法。

核心：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

注意：第一层遍历找出剩余元素最小值的索引，然后交换当前位置和最小值索引值【依次找到最小值】

代码：

function selectionSort(arr) {  
  const len = arr.length;  
  let minIndex;  
  for (let i = 0; i < len - 1; i += 1) {  
    minIndex = i;  
    for (let j = i + 1; j < len; j += 1) {  
      if (arr[minIndex] > arr[j]) {  
        minIndex = j; // 寻找最小值对应的索引  
      }  
    }  
    if (minIndex === i) continue;  
    swap(arr, minIndex, i);  
  }  
  return arr;  
} 

2.3 插入排序

插入排序的比较顺序不同于冒泡排序和选择排序，插入排序的比较顺序是当前项向前比较。

（编辑：ASP站长网）