玩转经典排序算法

排序算法是非常常见的面试题, 有了这个, 再也不怕啦

1. 冒泡排序

相邻元素两两比较 大的数字往后排序

    function bubble(arr) {
      let flag = false; // 提交结束冒泡的标识
      if (arr.length < 2) return arr;
      for (let i = 0; i < arr.length; i++) {
        flag = false; // 循环内的标识
        for (let j = 0; j < arr.length - 1 - i; j++) {
          // 从0开始, 到length-1-i结束
          if (arr[j] > arr[j + 1]) {
            const temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag = true; // 表示进行了数据交换
          }
          if (!flag) break; // 如果没有进行数据交换, 表示已经排序完成, 跳出循环
        }
      }
      console.log("arr", arr);
      return arr;
    }
    // bubble([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]);

 

2. 插入排序

拿到一个元素, 和前面的所有元素对比, 只要比他大就交换位置

    function insert(arr) {
      let len = arr.length;
      if (len < 2) {
        return arr;
      }
      let cur, pre;
      for (var i = 1; i < len; i++) {
        // 从1开始, len结束
        cur = arr[i];
        pre = i - 1;
        while (pre >= 0 && cur < arr[pre]) {
          arr[pre + 1] = arr[pre];
          pre--;
        }
        arr[pre + 1] = cur;
      }
      console.log("arr", arr);

      return arr;
    }
    // insert([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]);
 

3.选择排序

最小的元素放在起始位置, 再从剩下的未排序的数组选最小值, 放在已经排序的后面

    function select(arr) {
      let len = arr.length;
      let minIndex, temp;
      for (let i = 0; i < arr.length - 1; i++) {
        minIndex = i; // 定义最小元素的索引
        for (let j = i + 1; j < arr.length; j++) {
          if (arr[minIndex] > arr[j]) {
            minIndex = j; // 找到剩余数组中的最小值的索引, 赋值给minIndex
          }
        }
        // 交换当前arr[i]和arr[minIndex]的位置
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
      }
      console.log(arr);
      return arr;
    }
    // select([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]);
 

4. 归并排序

• 分治算法 递归 先处理子问题 再合并
• 先把数组分成两部分 递归进行排序

    function mergeSort(arr) {
   // 具体排序逻辑
   function merge(left, right) {
     const result = [];
     let i = 0, // 初始化i,j 的值
       j = 0;
     // 如果i,j都分别小于对应的数组长度, result的值为两个数组中对应的i,j的最小值
     while (i < left.length && j < right.length) {
       if (left[i] < right[j]) {
         result.push(left[i++]);
       } else {
         result.push(right[j++]);
       }
     }
     while (i < left.length) {
       result.push(left[i++]);
     }
     while (j < right.length) {
       result.push(right[j++]);
     }
     return result;
   }
   // 根据中间数, 分割数组成两部分
   function sort(arr) {
     if (arr.length === 1) return arr;
     const middle = Math.floor(arr.length / 2);
     const left = arr.slice(0, middle);
     const right = arr.slice(middle, arr.length);
     // merge 函数递归
     return merge(mergeSort(left), mergeSort(right));
   }

   return sort(arr);
 }

 

5. 快速排序

根据一个基数, 分别排序左右两边的数组, 最后连起来变成整个数组

    function quickSort(arr) {
    // 具体逻辑
    function quick(arr) {
      if (arr.length <= 1) return arr;
      const baseIndex = Math.floor(arr.length >> 1); // 找到基准点的索引
      const base = arr.splice(baseIndex, 1)[0]; // 找到基准点, arr去掉这个数
      const left = [],
        right = [];
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] > base) {
          right.push(arr[i]);
        } else {
          left.push(arr[i]);
        }
      }
      return quick(left).concat([base], quick(right)); // 递归去找, 直到arr.length<=1 退出循环
    }
    let result = quick(arr);
    return result;
  }
  let result = quickSort([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]);
  console.log(result, "result");

 

6.堆排序

--- 未完待续

• 本人今天写排序写的太累了, 但也属实有趣 , 后续会补充此排序, 并加多注释...嘿嘿嘿