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 插入排序

插入排序的较量次序差异于冒泡排序和选择排序，插入排序的较量次序是当前项向前较量。

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!