请选择 进入手机版 | 继续访问电脑版

前端算法-基本排序算法比较

[复制链接]
Mr.ZhouHeng 发表于 2019-10-10 09:36:56
本帖最后由 Mr.ZhouHeng 于 2020-4-25 15:02 编辑

在网上看到比较全的排序,分享一下:这个感觉可以节省很多时间;最主要的是可以装逼
基本排序算法
  这里主要介绍的基本排序算法主要包括: 冒泡排序,选择排序,插入排序,基本排序算法的核心思想是对一组数据按照一定的顺序重新排列. 重新排列主要就是嵌套的for循环. 外循环会遍历数组每一项,内循环进行元素的比较.

注: 文中都以实现升序排序为例:

1.冒泡排序
  冒泡排序是最慢的排序算法之一, 也是最容易实现的排序算法.使用这种算法进行排序时,数据值会像气泡一样从数组的一端漂浮到另一端,所以称之为冒泡排序.假设要对数组按照升序排列,较大的值会浮动到数组的右侧,较小值会浮到左侧.
原理:
  从开始第一对相邻元素开始,对每一对相邻元素进行比较,如果第一个比第二个大,就交换它们两个, 这样直到最后一对元素比较结束,最后的元素就是最大的数,重复这个过程,就可以完成排序.
示意图:
代码:
   
  1. function bubbleSort(arr) {
  2.         for (let i = 0; i < arr.length; i++) {
  3.           for (let j = 0; j < arr.length - i - 1; j++) {
  4.             if (arr[j] > arr[j + 1]) {
  5.               let temp = arr[j];
  6.               arr[j] = arr[j + 1];
  7.               arr[j + 1] = temp;
  8.             }
  9.           }
  10.         }
  11.         return arr;
  12.       }
复制代码


2.选择排序原理:
  首先找出当前元素中最小的元素,并放到排序序列的起始位置,然后再从剩余的元素中寻找最小的元素,然后放到已排序序列的末尾。以此类推,直到排序完成。
示意图:
代码:
     
  1. function selectionSort(arr) {
  2.         var len = arr.length;
  3.         var minIndex, temp;
  4.         for (var i = 0; i < len - 1; i++) {
  5.           minIndex = i;
  6.           for (var j = i + 1; j < len; j++) {
  7.             if (arr[j] < arr[minIndex]) {
  8.               minIndex = j;
  9.             }
  10.           }
  11.           temp = arr[i];
  12.           arr[i] = arr[minIndex];
  13.           arr[minIndex] = temp;
  14.         }
  15.         return arr;
  16.       }
复制代码


3.插入排序原理:
  从第二个元素开始(假定第一个元素已经排序了),取出这个元素,在已经排序的元素中从后向前进行比较,如果该元素大于这个元素,就将该元素移动到下一个位置,然后继续向前进行比较,直到找到小于或者等于该元素的位置,将该元素插入到这个位置后.重复这个步骤直到排序完成.
示意图:
代码:
     
  1. function insertionSort(arr) {
  2.         var len = arr.length;
  3.         var preIndex, current;
  4.         for (var i = 1; i < len; i++) {
  5.           preIndex = i - 1;
  6.           current = arr[i];
  7.           while (preIndex >= 0 && arr[preIndex] > current) {
  8.             arr[preIndex + 1] = arr[preIndex];
  9.             preIndex--;
  10.           }
  11.           arr[preIndex + 1] = current;
  12.         }
  13.         return arr;
  14.       }
复制代码

4.基本排序算法的性能比较
  使用console.time进行时间计算,在需要测试的开始位置写上console.time,并且括号内传一个字符串。在结束的位置使用console.timeEnd方法,并再次把字符串传入,即可在控制台查看执行时间.
首先创建一个n位随机数组用来测试.

  1. function createRandomArr(n) {
  2.         let arr = [];
  3.         for (let i = 0; i < n; i++) {
  4.           arr.push(Math.floor((Math.random() * 100)));
  5.         }
  6.         return arr;
  7.       }
复制代码


分别记录3种算法所用时间:
  1. var testArr = createRandomArr(1000);
  2.   //  记录冒泡排序所用时间
  3.   console.time('bubbleSort');
  4.   bubbleSort(testArr);
  5.   console.timeEnd('bubbleSort');
  6.   var testArr = createRandomArr(1000);
  7.   //  记录选择排序所用时间
  8.   console.time('selectionSort');
  9.   selectionSort(testArr);
  10.   console.timeEnd('selectionSort');
  11.   var testArr = createRandomArr(1000);
  12.   //  记录插入排序所用时间
  13.   console.time('insertionSort');
  14.   insertionSort(testArr);
  15.   console.timeEnd('insertionSort');
复制代码


在Chrome执行代码,在控制台看看他们的执行时间对比, Duang Duang Duang!
当然, 要进行多次运行, 得到的结果才能被视为有效的结论. 很显然, 插入排序比其他两种排序方法快.



本帖子中包含更多资源,您需要 登录 才可以下载或查看,没有帐号?立即注册

X

3条回复

handsix 版主 12634Y币
豪气布拉格 业余车手 497Y币
优秀,顶
飞翔的翔 职业车手 9471Y币
很久不见啊
您需要登录后才可以回帖 登录

本版积分规则