美文网首页
五种排序

五种排序

作者: fejavu | 来源:发表于2019-12-02 00:18 被阅读0次

    排序可以分为比较排序和非比较排序。比较排序是指在排序过程中,会将所有元素的值进行比较,将小的或者是大的按照一个规律进行“运动”,最终形成一个有序的数组;非比较排序是利用自然数本身递增的特点,记录待排序数组中的元素以及个数,按照自然数进行从小到大输出(该数组存在该自然数一次以上)。

    冒泡排序

    冒泡排序是比较排序的一种。在两个相邻元素之间进行两两比较,使得比较大的数不断上升到右边,就像是气泡,越往上冒越大,经过每个数字至少冒泡一次的比较,可以使得右边的数从大到小排列。


    Bubble-Sort-3.png
    Array.prototype.bubbleSort = function() {
      let len = this.length;
      let count = 0;
      
      if(len<2 || !this) {
        return this;
      }
      
      while(count < len-1) { 
        let swapFlag = false;
        for(var j=0;j<len-1;j++) {
          if(this[j] > this[j+1]) {
            var temp = this[j];
            this[j] = this[j+1];
            this[j+1] = temp;
            swapFlag = true;
          }
        }
        if(!swapFlag) break;
      }
      
      return this;
    }
    

    选择排序

    选择排序也是比较排序的一种。从数组第一个元素位置开始,每次将剩余最小的元素放到当前的位置上,这样经过数组长度次数的比较与元素选择,就可以将数组从小到大进行排序。

    selection sort.png
    Array.prototype.selectSort = function() {
      let count = 0;
      
      while(count < this.length) {
        let minNum = this[count];
        let index = count;
        for(let i=count+1; i<this.length;i++) {
          if(this[i] <= minNum) {
            minNum = this[i];
            index = i;
          }
        }
    
        this[index] = this[count]; 
        this[count] = minNum;   
        count++;
      }
      
      return this;
    }
    

    插入排序

    插入排序也是比较排序的一种。它的原理和平时生活里起扑克牌一样,每次拿到一张牌,将它插入后面比它大,前面比它小的位置上,每张牌都是如此,当牌拿完后,得到的就是一副从小到大的牌。

    insertion-sort-algorithm.jpg
    Array.prototype.insertSort = function() {  
      for(let count = 1;count < this.length; count++) {
        let minNum = this[count];
        let temp = count -1;
    
        while(temp > 0 && this[temp] > minNum) {
          this[temp+1] = this[temp];
          temp--;
        }
    
        this[temp+1] = minNum;
      }
      
      return this;
    }
    

    快速排序

    快速排序是比较排序的一种。它运用了分治的思想。每次选取数组的第一个作为数字基准,比基准小的排到基准左边,比基准大的,排到基准的右边,这样一来,基准的位置是唯一确定的。然后运用递归,将左边再次作为一个数组进行排序,选取基准,左右分开,不断递归。

    javascript-quicksort.jpg
    Array.prototype.quickSort = function() {
      const len = this.length;
      if(len < 2) return this;
      let basic = this[0], left = [], right = [];
      
      for(let i =1;i<len; i++) {
        if(this[i] <= basic) {
         left.push(this[i]);
        }else {
          right.push(this[i]);
        }
      }
      return left.quickSort().concat(basic, right.quickSort());
    }
    

    计数排序

    计数排序是非比较排序,它是将所有的数组元素都记录,用数组元素值作为键,元素出现的次数作为值,存储在一个类似于键值对的map类型中,当遍历完后,存储数组中有该值,则将该值从小到大按照次数输出,这样就形成了一个有序的数组。

    counting_sort_algorithm.png
    Array.prototype.countSort = function() {
      const countArr = [];
      for(let i=0;i<this.length;i++) {
        if(countArr[this[i]]) {
          countArr[this[i]]++;
        }else {
          countArr[this[i]] = 1;
        }
      }
    
      const resultArr = [];
      for(let j =0;j<countArr.length;j++) {
        while(countArr[j]>0) {
          resultArr.push(j);
          countArr[j]--;
        }
      }
      return resultArr;
    }
    

    相关文章

      网友评论

          本文标题:五种排序

          本文链接:https://www.haomeiwen.com/subject/pncuwctx.html