基础排序算法原理

冒泡排序

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个【原地排序】算法。冒泡排序中，只有大小不同才做交换，相等不交换位置，所以是【稳定排序】。

// 对以下数据，从小到大排序
let sortData = [4,5,6,3,2,1];

function bubbleSort(){
    for (var i = 0; i < sortData.length-1; i++) {
      let flag = false;//是否有数据交换
      for (var j = i+1; j < sortData.length; j++) {
        // swap
        if(sortData[i]>sortData[j]){
          [sortData[i],sortData[j]] = [sortData[j],sortData[i]]
          flag = true;
        }
      }
      if(!flag){
        break;
      }
    }
    
    console.log('after bubbleSort sortData ',sortData)
}

插入排序

插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间（内层循环）只有一个元素，即数组第一个元素。在未排序区间（外层循环）取出一个元素，在已经排序的元素序列中从后向前扫描，插入到已排序区间的合适位置。直到未排序区间为空，结束。

// 对以下数据，从小到大排序
let sortData = [4,5,6,3,2,1];

function insertionSort() {
    // 默认从第二个元素到数组结束为“未排序区间”
    for (var i = 1; i < sortData.length; i++) {
      // 从“未排序区间”取出一个值，和“已排序区间”的值遍历对比大小
      let value = sortData[i];
    
      // 极客时间-处理手法
      // let j = i-1;
      // for(; j>=0; j--){
      //   if(sortData[j] > value){
      //     sortData[j+1] = sortData[j];
      //   }else{
      //     break;
      //   }
      // }
      // sortData[j+1] = value;//为何是j+1（看了评论说j可以到达-1）
    
      // 我的-处理手法
      // 已排序区间，从后往前遍历
      for(var j=i-1; j>=0; j--){
        if(sortData[j] > value){
          sortData[j+1] = sortData[j];
          sortData[j] = value;
        }else{
          break;
        }
      }
    }
    
    console.log('after insertionSort sortData ',sortData)
}

insertionSort()

快速排序（‼️重要）

取数组基准位置midIndex和基准位置的值midValue，设置左left右right数组遍历数组，小于midValue的放在left，大于midValue的放在right数组返回拼接left，midValue，right，递归上述步骤。当数组长度小于等于1，结束。

具体实现方式如下：

• 选取数组中的一个元素作为“基准”（pivot）。
• 将数组中小于基准的元素移到基准的左边，将大于基准的元素移到基准的右边。
• 递归地对基准左边和右边的子数组进行排序，直到子数组的长度为 0 或 1。
• 在实现快速排序时，为了提高算法的效率，可以对数组进行优化，例如使用三数取中法选择基准元素，以减少最坏情况的发生。

let sortData = [4,5,6,3,2,1];

function quickSort(arr) {
    if(arr.length<=1){
      return arr;
    }
    
    let midIndex = Math.floor(arr.length/2);
    let midValue = arr.splice(midIndex,1)[0];//splice返回数组形式，[0]取出来
    let left = [];
    let right = [];
    
    for (var i = 0; i < arr.length; i++) {
      if(arr[i]<midValue){
        left.push(arr[i])
      }else{
        right.push(arr[i])
      }
    }
    
    return quickSort(left).concat(midValue,quickSort(right))
}

quickSort(sortData)

选择排序

大致思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

let sortData = [4,5,6,3,2,1];

function selectionSort(arr) {
    for (var i = 0; i < arr.length; i++) {
      let minIndex = i;
      for (var j = i+1; j < arr.length; j++) {
        minIndex = arr[j] < arr[minIndex] ? j : minIndex;//寻找最小值
    
        if(arr[i] > arr[minIndex]){
          [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];//交换
        }
      }
    }
    console.log('after selectionSort sortData ', arr)
}

selectionSort(sortData);

二分查找法

将有序数组一分为二，并取中间的值与target对比。

• 若 相等，则返回中间位；
• 若 比target大，则在中间位左边查找
• 否则在右边查找

var sortedarr = [1, 2, 3, 4, 5, 6];

function binarySearch(arr,target,low=null,high=null){
    low = low===null?0:low;
    high = high===null?arr.length-1:high;
    // 结束条件
    if(low>high){
      return -1;
    }
    let mid = parseInt((low+high)/2);
    let current = arr[mid];
    if (target == current) {
      return mid;
    }else if(target < current){
      high = mid - 1;
      return binarySearch(arr, target, low, high)
    }else{
      low = mid + 1;
      return binarySearch(arr, target, low, high)
    }
}

binarySearch(sortedarr,6); //5

sort方法的实现原理

avaScript 中的 sort 方法采用的是快速排序（quick sort）算法实现的，但具体实现方式因浏览器厂商而异，因为 JavaScript 引擎可以根据具体情况选择最优的算法实现。

快速排序算法的基本思想是将一个数组分成两个子数组，其中一个子数组的元素都比另一个子数组的元素小，然后递归地对这两个子数组进行排序。具体实现方式如下：

• 选取数组中的一个元素作为“基准”（pivot）。
• 将数组中小于基准的元素移到基准的左边，将大于基准的元素移到基准的右边。
• 递归地对基准左边和右边的子数组进行排序，直到子数组的长度为 0 或 1。
• 在实现快速排序时，为了提高算法的效率，可以对数组进行优化，例如使用三数取中法选择基准元素，以减少最坏情况的发生。

需要注意的是，JavaScript 的 sort 方法还有一个可选的参数，即排序函数。这个函数用于比较两个元素的大小，如果返回值小于 0，则表示第一个元素排在第二个元素前面；如果返回值大于 0，则表示第一个元素排在第二个元素后面；如果返回值等于 0，则表示两个元素相等，不需要改变它们的相对位置。如果没有提供排序函数，则 sort 方法将按照 Unicode 编码进行排序。

其它问题

  // 判断回文 1:顺读，反读都一样；2：从左到右，与对应的从右到左的每一个字符都相等
  function ispalindrome(str) {
    return str == str.split('').reverse().join('')
  }

  // 数组去重
  function noSame(arr) {
    let set = new Set(arr)
    return [...set]
  }

  // 阶乘
  // 未优化
  function factorial (n) {
      if (n === 1) return 1;
      return n*factorial(n-1);
  }
  factorial(10);//3628800

  // 优化
  function tailFactorial(n,total=1){
    if(n==1) return total;
    return tailFactorial(n-1,n*total);
  }
  tailFactorial(10);//3628800


  // 斐波那契数列-递归
  //在数据较大的时候会 超时
  // 未优化
  function fib(n){
    if(n<2) return 1
    return fib(n-1)+fib(n-2)
  }
  fib(8);// 34

  // 优化
  function fib(n,acc1=1,acc2=1){
    if(n<2) return acc1
    return fib(n-1,acc1+acc2,acc1)
  }
  fib(8);// 34


  // 星级评价
  function getRate(rate){
    return "★★★★★☆☆☆☆☆".slice(5 - rate, 10 - rate);
  }
  getRate(3);//★★★☆☆



  // 给定一个数组,有正数,负数和零,排列给定的数组,使负数在左边,0在中间,正数在右边
  var ar = [-1, 8, 0, -5, 0, 2, -4];

  function swap(a, b) {
    console.log('交换 %s:%s和%s:%s',a,ar[a],b,ar[b])
    if(a==b){
      return;
    }
    let c;
    c = ar[a];
    ar[a] = ar[b];
    ar[b] = c;
    console.log('ar:',ar)
  }

  function sortNumbers(len) {
    let low = 0, mid = 0, high = len - 1;
    while (mid <= high) {
      let midVal = ar[mid]
      console.log('low %s,mid %s,high %s,ar[mid] %s ',low,mid,high,midVal)
      if (midVal > 0) {
        swap(low++, mid++);
      } else if (midVal == 0) {
        mid++;
      } else
        swap(mid, high--);
    }
  }
  console.log(ar)
  console.log(sortNumbers(ar.length))


  // 不考虑0，负数放右边，0和正书放左边
  function basicSortNumber(arr) {
    let start = 0;
    let end = arr.length - 1;

    function mySwap(i,j) {
      [arr[i],arr[j]] = [arr[j],arr[i]];
    }

    while(start <= end){
      let num = arr[start];
      if(num>=0){
        start++;
      }else{
        mySwap(start, end);
        end--;
      }
    }

    console.log('arr:',arr)
  }

  basicSortNumber([-1, 8, 0, -5, 0, 2, -4])