排序算法

冒泡排序

最经典和简单粗暴的排序算法

什么是冒泡排序

逐个的比较相邻的元素

1 .比较相邻的元素。如果第一个比第二个大，就交换他们两个。因此是小的在前面

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

为什么叫冒泡排序

如碳酸饮料中的二氧化碳，密度小的泡泡首先会浮到顶端，用泡泡来比喻元素，因此数据小的元素会在数列的顶端，大的数据在最后

故名“冒泡排序”

冒泡排序说明

再次说明一下，JS冒泡排序可能并不适用于你的实际工作中哦，它只是一个简单的工具帮助我们了解算法并且为进一步获取更多的知识打下基础。而我们用得最多的可能是内置的Array.prototype.sort() 原型方法，这是由于它具有更高效率。

例子1

js
//排序方法 (冒泡排序)  
Array.prototype.mySort = function (){
    for(var i = 0;i<this.length-1;i++){
        for(var j = 0;j<this.length -1-i;j++){
            // this[j]<this[j+1] 代表降序
            // this[j]>this[j+1] 代表升序
            if(this[j]>this[j+1]){
                var temp = this[j]
                this[j] = this[j+1]
                this[j+1] = temp
            }  
        }
    }
}
var arr1 = [1,77,3,44,55,66]
arr1.mySort()
console.log(arr1)

例子2

js
function bubbleSort(arr) {
  var len = arr.length;
  for (let outer = len; outer >= 2; outer--) {
    for (let inner = 0; inner <= outer - 1; inner++) {
      if (arr[inner] > arr[inner + 1]) {
        [arr[inner], arr[inner + 1]] = [arr[inner + 1], arr[inner]];
      }
    }
  }
  return arr;
}
console.log(bubbleSort(arr));

例子3

js
var arr = [3, 4, 1, 2];
function bubbleSort (arr) {
  var max = arr.length - 1;
  for (var j = 0; j < max; j++) {
    // 声明一个变量，作为标志位
    var done = true;
    for (var i = 0; i < max - j; i++) {
      if (arr[i] > arr[i + 1]) {
        var temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        done = false;
      }
    }
    if (done) {
      break;
    }
  }
  return arr;
}
bubbleSort(arr);

快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

首先设定一个分界值，通过该分界值将数组分成左右两部分

将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边

分别对较小元素的子序列和较大元素的子序列重复步骤1和2

js
function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  //递归出口
    }
    var left = [],
        right = [],
        current = arr.splice(0,1); //注意splice后，数组长度少了一个
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  //放在左边
        } else {
            right.push(arr[i]) //放在右边
        }
    }
    return  quickSort(left).concat(current,quickSort(right)); //递归
}

选择排序

选择排序是从数组的开头开始，将第一个元素和其他元素作比较，检查完所有的元素后，最小的放在第一个位置，接下来再开始从第二个元素开始，重复以上一直到最后

js
function selectSort(arr) {
    var len = arr.length;
    for(let i = 0 ;i < len - 1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

插入排序

插入排序逻辑和冒泡类似，只不过没采用挨个交换的逻辑，而是在一个已经排好序的数组里，插入一个元素，让它依然是有序的

默认 arr[0] 为已排序数组中的元素*，*从 arr[1] 开始逐渐往已排序数组中插入元素，从后往前一个个比较，如果待插入元素小于已排序元素，则已排序元素往后移动一位，直到待插入元素找到合适的位置并插入已排序数组。

将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。

插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。

例子1

js
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    //外循环从1开始，默认arr[0]是有序段
    for (let j = i; j > 0; j--) {
      //j = i,将arr[j]依次插入有序段中
       //为了找到合适的位置插入
      if (arr[j] < arr[j - 1]) {
         //arr[j]和arr[j-1]对应的值进行交换
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      } else {
        break;
      }
    }
  }
  return arr;
}

例子2

<1>.从第一个元素开始，该元素可以认为已经被排序； <2>.取出下一个元素，在已经排序的元素序列中从后向前扫描； <3>.如果该元素（已排序）大于新元素，将该元素移到下一位置； <4>.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置； <5>.将新元素插入到该位置后； <6>.重复步骤2~5。

js
function insertionSort(arr) {
  for (let i = 1; i <arr.length; i++) {
    const temp = arr[i];
    let preIndex = i - 1; //默认已排序的元素  默认arr[0]是有序段
  //在已排序好的队列中从后向前扫描  
    while (arr[preIndex] > temp) {
       //已排序的元素大于新元素，将该元素移到一下个位置
      arr[preIndex + 1] = arr[preIndex];
      preIndex -= 1;
    }
    arr[preIndex + 1] = temp;
  }

  return arr;
}

冒泡排序​

什么是冒泡排序​

为什么叫冒泡排序​

冒泡排序说明​

例子1​

例子2​

例子3​

快速排序​

选择排序​

插入排序​