排序算法的Javascript实现

fredshare 发布于2019-08-22 18:29 / 2688人阅读

摘要：排序加了的插入排序。分别以索引数为的元素为起点，将其看做不同的组，，，为一组，，为一组依次分组，按照组为单位进行插入排序。各组都已经插入排序一轮过后，将除以向下取整，再进行分组并将各组分别进行插入排序，直到为。

1.冒泡排序：

比较相邻的两个数，如果前一个数大于后一个数，就将这两个数换位置。每一次遍历都会将本次遍历最大的数冒泡到最后。为了将n个数排好序，需要n-1次遍历。如果某次遍历中，没有调整任何两个相邻的数的位置关系，说明此时数组已排好序，可以结束程序。

Array.prototype.bubbleSort = function () {
  let i, j;
  for (i = 1; i < this.length; i++) {  //表示本次是第i次遍历
    let changed = false;
    for (j = 0; j < this.length - i; j++) {   //访问序列为arr[0:length-i]
      if(this[j] > this[j + 1]){  //发现前一个数大于后一个时，互换位置
        [this[j],this[j+1]] = [this[j+1],this[j]];
        changed = true;
      }
    }
    if(!changed) {      //如果本轮遍历没有发现位置调整，结束排序函数
      break;
    }
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.bubbleSort();
console.log(arr);

2.选择排序

第i轮遍历arr[0:n-i]选出最大的数，与arr[n-i]互换。

Array.prototype.selectSort = function () {
  let i, j;
  for (i = 1; i < this.length; i++) {     //表示本次是第i次遍历
    let maxIndex = 0;
    for (j = 0; j <= this.length - i; j++) {  //访问子序列为arr[0:this.length-i]
      if (this[j] > this[maxIndex]) {   //当前值大于当前最大值时，记录索引
        maxIndex = j;
      }
    }
    //将子数组最大值索引的值，与子数组末尾的值互换
    [this[this.length - i], this[maxIndex]] = [this[maxIndex], this[this.length - i]]
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.selectSort();
console.log(arr);

3.插入排序数组的前面部分已经排好序，要把当前数字插入到前面已排好序的数组的相应位置。可能有人会有疑问为什么默认数组前面部分已排好序？是怎么排好序的？是因为当排序开始时，从第2个数字开始进行向前插入，此时当前数字索引为1，当前数字前面仅有一个数字，因此可以认为前面部分已经排好序，将这个数字插入到相应位置之后数组仍然是有序的。每次都将当前数字插入到对应的位置，因此每次插入之后前面的数组仍是排好序的。

Array.prototype.insertSort = function () {
  let i, j;
  for (i = 1; i < this.length; i++) {   //i表示当前要向前插入的数字的索引，从1(即第2个数)开始前插
    let val = this[i];   //记录当前要前插的数的大小
    /*
    * 用指针j来遍历第i个数字前面的，已经排好序的子数组。当j没有指到头，并且j的数字大于要插入的数字时，说明
    * j还要向前遍历，直到发现一个比要插入数字小的位置pos，然后将这个数字插到pos+1处。如果j已经指到头了，
    * 到了-1了还没有找到比当前数字小的位置，就把当前数字放在索引0处。
    * */
    for (j = i - 1; j >= 0 && this[j] > val; j--) {  
      this[j + 1] = this[j];
    }
    this[j + 1] = val;
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.insertSort();
console.log(arr);

4.shell排序加了step的插入排序。分别以索引数为0,1,......step-1的元素为起点，将其看做不同的组，0、0+step,0+2step，......，0+nstep为一组，1,1+step,1+2step，.....,1+nstep为一组依次分组，按照组为单位进行插入排序。各组都已经插入排序一轮过后，将step除以2向下取整，再进行分组并将各组分别进行插入排序，直到step为0。 step的取值与性能直接相关，需要思考后取值。并且这里的分组仅仅是逻辑上分组，并没有开辟新的地址空间将其进行物理上的分组。

const {floor} = Math;
//这个和插入排序相同，只不过加了step
Array.prototype.shellInsertSort = function (startIndex, step) {
  let i, j;
  for (i = startIndex + step; i < this.length; i += step) {
    let val = this[i];
    for (j = i - step; j >= 0 && this[j] > val; j -= step) {
      this[j + step] = this[j];
    }
    this[j + step] = val;
  }
};
Array.prototype.shellSort = function () {
  let i, step;
  for (step = floor(this.length / 2); step > 0; step = floor(step / 2)) {
    for (i = 0; i < step; i++) {
      this.shellInsertSort(i, step);
    }
  }
};
let arr = [43, 21, 10, 5, 9, 15, 32, 57, 35];
arr.shellSort(true);
console.log(arr);

5.合并排序

举个例子：有 43 12 32 29 66 78 31这个数组要用合并排序。先将相邻两数分为一组进行合并 43|12 32|29 66|78 31 结果为12 43 29 32 66 78 31

再将组的大小乘以二 (12 43|29 32) (66 78|31) 本次合并后结果为 12 29 32 43 31 66 78

再将组的大小乘以二 12 43 29 32 | 66 78 31 合并结果：12 29 31 32 43 66 78

合并的过程中要开辟新的数组arr，建立两个指针i,j分别指向arr1与arr2，此时arr1与arr2都是排好序的，然后每次都将arr1[i]与arr2[j]较小的数加到arr中并将指针后移。最后哪个数组有剩余的数在追加到arr后面。

云服务器 GPU云服务器字母的排序算法最好的排序算法选择排序的算法过程最好的快速排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95913.html

深入浅出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 评论0 收藏0
常用排序算法之JavaScript实现

摘要：代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序，排序的速度快于任何比较排序算法。赞助我以写出更好的文章，give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1）算法简介插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它...

jerry 2019-08-21 12:27 评论0 收藏0
优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...

cheukyin 2019-08-26 10:17 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

GeekQiaQia 2019-08-21 11:41 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

cgspine 2019-08-16 10:33 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上，通常采用排序即只需用到的额外空间的排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segm...

lufficc 2019-07-31 10:56 评论0 收藏0