常见的算法

[huangchucai]

人生就像一列开往坟墓的列车，路途上会有很多站，很难有人至始至终陪你走完全程，当陪你的人要下车时，即便不舍，也要心存感激，然后挥手告别。---sunnyhuang

---

常见的算法

1. 冒泡排序：效率低，生产环境中很少使用

   • 依次比较相邻的两个数，如果不符合排序规矩，则调换两个数的位置。这样一遍下来，可以保证最大（或者最小）的数排在最后一位。
   • 再对除了最后一位的数进行上一步动作的排序，直到全部完成。

   function swap(myArray,p1,p2){
   	var temp=myArray[p1];
     	myArray[p1]=myArray[p2];
       myArray[p2]=temp;
   }
   //传递需要排序的数组
   function bubbleSort(myArray){
   	var len=myArray.length;
       var i,j;
     	//假如已经排好了i个数字
     	for(i=0;i<len;i++){
       //对已经排好了的数字的剩下数字比较
         //这里的len-i-1,是选择了减去已经选择好了的元素和被选中的元素
         for(j=0;j<len-i-1;j++){
           if(myArray[j]>myArray[j+1]){
             swap(myArray,j,j+1)
           }
         }
     	}
     return myArray;
   }
   bubbleSort([1,2,3,656,767,4,353,7])  //[1, 2, 3, 4, 7, 353, 656, 767]

2. 选择算法

   • 依次比较相邻的2个数，记录出已经比较的最小值（最大值）
   • 等一轮结束后把得到的相应的值，放到开头（结尾）
   • 依次寻找，直到全部找到

   //定义一个交换函数
   function swap(myArray, p1, p2) {
       var temp = myArray[p1];
       myArray[p1] = myArray[p2];
       myArray[p2] = temp;
   }
   function selectionSort(myArray) {
       var len = myArray.length;
       var i,j,min;
       for (i = 0; i < len; i++) {
         	//将当前位置设为最小值
           min = i;
         	//检查数组的其余部分是否更小
           for(j=i+1;j<len;j++){
             if (myArray[min] > myArray[j]) {
               min=j;
              }
           }
         	//如果当前位置不是最小值，就将其换为最小值
           if(i != min){
               swap(myArray,i,min)
           }
       }
       return myArray
   }
   selectionSort([1,3,534,5,64,234,6])  //[1, 3, 5, 6, 64, 234, 534]

3. 插入排序

   • 首先把数组分成2个部分，已排序和未排序
   • 假定第一个元素是已经排序了的（所有这里除了第一个元素后，其余的都是未排序的）
   • 将已经排序了的在未排序中的后一个元素，放入已经排序的队列中，所有已经排序的队列增加一个，未排序的队列减少一个
   • 对刚刚放进已经排序的元素和已经在排序好了的队列中的元素比较，将其放入相应的位置。

   //定义一个交换函数
   function insertSort(myArray) {
       var len = myArray.length;
       var i, j, value;
       for (i = 0; i < len; i++) {
           //记录当前的值得大小
           value = myArray[i]  //当前序号是 i,前面有i-1个已经排好序列的元素
           //把当前值得大小和已经排好序列的元素进行比较
           //当已排序部分的当前元素大于value，
           //就将当前元素向后移一位，再将前一位与value比较
           for (j = i - 1; j > -1 && value < myArray[j]; j--) {
               myArray[j + 1] = myArray[j];
           }
           myArray[j + 1] = value;
       }
       return myArray;
   }

4. 快速排序

   • 在数据集中，选择一个元素作为“基数”（pivot），一般取中间值
   • 在数据中，小于“基数”的元素，都移到“j基数”的左边，大于“基数”的，都移动到“基数”的右边
   • 对“基数”的左右2个子集，不断的重复第一步和第二步，直到所有子集只剩下一个元素为止。

function quickSort(myArray) {
if (myArray.length <= 1) { return myArray; }
var baseIndex = Math.floor(myArray.length / 2);
var base = myArray.splice(baseIndex, 1)[0];
var right = [];
var left = [];
for (var i = 0; i < myArray.length; i++) {
if (myArray[i] < base) {
left.push(myArray[i])
}
else {
right.push(myArray[i])
}
}
return quickSort(left).concat([base], quickSort(right))
}

#### [参考链接](https://javascript.ruanyifeng.com/library/sorting.html)

#### [动效展示](https://visualgo.net/sorting)
​

​