数据结构(九)-排序和搜索算法

排序算法

排序算法动画图示网站:
https://visualgo.net/zh/sorting

冒泡排序

冒泡排序会比较所有两个相邻的项，如果第一个比第二个大，则交换他们。元素向上移动到正确顺序，就好像气泡升至表面。
优点:简单
缺点:运行时间长
复杂度O(n*n)

function defaultCompare (a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
function swap(array, a, b) {
  [array[a], array[b]] = [array[b], array[a]]
}
// 冒泡排序-效率低时间慢，复杂度O(n的平方)
function bubbleSort(arr, compareFn = defaultCompare) {
  for(let i = 0; i < arr.length; i++) { // 一共循环5轮
    // for (let j = 0; j < arr.length - 1; j++) { // 每次里层循环都要从第一个开始遍历一遍，这里会比较相邻的两项
    //   if (defaultCompare(arr[j],arr[j+1]) === Compare.BIGGER_THAN) {
    //     swap(arr,j,j+1)
    //   }
    // }
    // 优化版本，因为每次排序之后，已经跑过的圈数后面的顺序是正确的，就没必要再比较，这里减去一个i
    for (let j = 0; j < arr.length - 1 - i; j++) { // 每次里层循环都要从第一个开始遍历一遍，这里会比较相邻的两项
      if (defaultCompare(arr[j],arr[j+1]) === Compare.BIGGER_THAN) {
        swap(arr,j,j+1)
      }
    }
  }
  return arr
}

图示第一个算法过程

改进之后的算法过程

选择排序

性能较差
复杂度O(n*n)

function defaultCompare (a, b) {
    if (a === b) {
      return Compare.EQUALS;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
  }
  function swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
  }
  // 选择排序
  function selectionSort(array, compareFn = defaultCompare) {
    let indexMin;
    for (let i = 0; i < arr.length-1; i++) {
      indexMin = i;
      for (let j = 0; j < array.length; j++ ) {
        // 寻找是否有值比当前的indexMin小，有的话交换这两个值，较小的设置为indexMin
        if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {
         indexMin = j
        }
      }
    }
    // 交换i和indexMin
    if (i !== indexMin) {
      swap(array,i,indexMin)
    }
    return arr
  }

插入排序

插入排序在小型数组效率比冒泡和选择排序性能好

// 插入排序，插入排序就是第二个值开始，不断向前比较，看前面一个是否比自己大，大的话，就交换
 function insertionSection(array, compareFn = defaultCompare) {
   let temp;
   for (let i = 0; i < array.length; i++) {
     let j = i; //  临时记录最终要交换的是哪一个
     let temp = array[j]
     while(j > 0 && compareFn(array[j-1], temp === Compare.BIGGER_THAN)){
       array[j] = array[j-1]
       j--
     }
     array[j] = temp
   }
   return array

 }
 <!--另外的版本-->
   function insertionSection(arr) {
   var len = arr.length;
   var preIndex, current;
   for (var i = 1; i < len; i++) {
       preIndex = i - 1;
       current = arr[i];
       while (preIndex >= 0 && arr[preIndex] > current) {
           arr[preIndex + 1] = arr[preIndex];
           preIndex--;
       };
       arr[preIndex + 1] = current;
   };
   return arr;

 }

归并排序

参考:https://www.cnblogs.com/chengxiao/p/6194356.html
插入排序,冒泡排序，选择排序性能并不好，归并排序性能不错，复杂度为O(nlog(n)。

归并排序是一种分而治之的算法。其思想是将原始数组切分为娇小的数组，直到每一个小数组只有一个位置，接着将小数组归并为较大的数组，直到最后只有一个排序完毕的大数组。
分而治之:将问题分解为较小的子问题递归求解，直到它们变得足够简单以至可以直接解决为止。

// 归并排序
  function mergeSort(arr) {
    if(arr.length <=1) return arr;
   let middle = Math.floor(arr.length / 2);
   let left = mergeSort(arr.slice(0, middle))
   let right = mergeSort(arr.slice(middle))
    // merge(left,right)
    console.log(left, right) 
   return merge(left, right)
  }
  // 测试
  // mergeSort([8,7,6,5,4,3,2,1]) // [8][7]   [6][5]   [4][3]   [2][1]
  function merge(left, right) {
    const result = []
    while(left.length > 0 && right.length > 0) {
      if (left[0] > right[0]) { // 将两个数组的第一个进行比较，哪一个小就截出来放到新数组里面，知道有一个被截取完成
        result.push(right.shift())
      } else {
        result.push(left.shift())
      }
    }
    // 将截取完成添加到新数组的result和剩下的合并起来返回
    return result.concat(left, right)
  }

快速排序

最常用的排序算法。
复杂度为O(nlog(n))，同样使用分而治之思想。
https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html

console.log(quickSort([3,4,9,8,2,1]))
 // 快速排序算法
 function quickSort(array, compareFn = defaultCompare) {
   return quick(array,0,array.length-1,compareFn)
 }
 
 function quick(array, left, right, compareFn) {
   let index;
   if (array.length <= 1) return arr;
   // index是
   index = partition(array, left, right, compareFn)
   if (left < index -1) {
     quick(array, left, index-1, compareFn)
   }
   if (index < right) {
     quick(array,index,right,compareFn)
   }
   return array
 }
 function partition(array, left, right, compareFn) {
   // 选择一个基准值,可以是任意一个，但是如果假设数组已经是有序的。最好选择中间的数
   let pivot = array[Math.floor((left+right)/2)] // 拿到中间的那个数
   let i = left; // 声明两个指针，i从左向右移动
   let j = right; // 声明两个指针，j从右向左移动
   while(i <= j) {
     while(array[i] < pivot) { //先移动left指针，找到一个比基准值大的数
     // 走到这里证明array[i]比基准值小，继续移动i指针到下一个
       i++
     }
     while(array[j] > pivot) { // 在移动right指针，找到一个比基准值小的值
     // 走到这里证明 array[j]比基准值大，继续移动j指针到下一个
       j--
     }
     if (i <= j) { // 左右指针没有重叠，这里的意思的
       // 执行到这里，证明当前左指针比比基准值大，右指针比基准值小，并且i和j没有重叠，左边的值大于右边
       swap(array, i, j) //交换这两个值
       i++; // 继续遍历
       j--; // 继续遍历
     }
   }
   // 此时i和j已经重叠
   console.log(i, j,'12312')
   return i;
 }

Array.prototype.sort的实现原理

在JS中，有一个sort方法可以用来给数组排序，原理就是利用归并排序和快速排序。
在火狐浏览器中使用的是归并排序。
在V8中使用的是快速排序的变体

计数排序

计数排序是一种分布式排序算法，主要是计算元数组中每个出现的次数加入到新数组，然后遍历新数组还原。

时间复杂度O(n+k),k是临时计数数组的大小，缺点是需要更多的内存来存放临时数组。

// 计数排序
function findMaxValue(array) {
  let max = array[0];
  array.forEach((v) => {
    if (v > max) {
      max = v;
    }
  });
  return max;
}

function countingSort(array) {
  if (array.length < 2) {
    return array;
  }
  const maxValue = findMaxValue(array);
  let counts = new Array(maxValue + 1);
  array.forEach((element) => {
    if (!counts[element]) {
      counts[element] = 0;
    }
    counts[element]++;
  });
  console.log(counts, 'counts');
  let sortedIndex = 0; // 用来辅助排序，记录当前索引
  debugger;
  counts.forEach((count, i) => {
    // 这里的count是出现的次数，这里的i就是array中的元素
    while (count > 0) {
      array[sortedIndex++] = i;
      count--; // 至少出现一次，多次的话就继续while循环
    }
  });
  return array;
}
/**
这是计数排序下来的顺序
*/
// [empty, 1, 1, 2, 1, empty, empty, empty, 1] 'counts'  //上面方法中的counts中的i就是元数组中的元素
//         1  2  3  4                       8  //这里是对应的原数组
countingSort([8, 4, 3, 2, 3, 1]);

桶排序

基数排序

搜索算法

顺序搜索(线性搜索)

将每一个数据结构中的元素和我们要找的元素做比较，是一种最低效的搜索算法。

const DOES_NOT_EXIST = -1
function sequentialSearch(array, value, equalsFn = defaultEquals){
    for (let i = 0; i < array.length; i++){
        if (equalsFn(value, array[i])) {
            return i
        }
    }
    return DOES_NOT_EXIST
}

二分搜索

要求数组是一个升序的有序数组。
算法步骤:

• 选择数组中间的值
• 如果选中值是待搜索值，算法执行完毕
• 如果待搜索值比选中值要小，返回步骤一并在左边子数组中寻找(较小)
• 如果待搜索值比选中值要大，返回步骤一并在右边子数组中寻找(较大)

  const DOES_NOT_EXIST = -1
  function lesserOrEquals(a, b, compareFn) {
    const comp = compareFn(a, b)
    return comp === Compare.LESS_THAN || comp === Compare.EQUALS
  }
  function binarySearch(array, value, compareFn = defaultCompare) {
    // 二分搜索的数组需要是一个升序的数组，先排序
    const sortedArray = quickSort(array)
    let low = 0;
    let high = sortedArray.length - 1
    while(lesserOrEquals(low, high, compareFn)){ // 如果low不比high大
      const mid = Math.floor((low + high) / 2) // 获取到中间的下标
      const element = sortedArray[mid] // 获取到中间的值
      if (compareFn(element, value) === Compare.LESS_THAN) { // 中间值比待搜索值比较小，从右边开始搜索
        low = mid + 1
      } else if (compareFn(element, value) === Compare.BIGGER_THAN) { // 中间值比待搜索值比较大，从左边开始搜索
        high = mid - 1
      } else {
        return mid
      }
    }
    return DOES_NOT_EXIST
  }