排序算法
冒泡排序
const bubbleSort = arr => {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j+1]) {
let temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}
}
选择排序
const selectionSort = arr => {
for (let i = arr.length - 1; i > 0; i--) {
let max = i
for (let j = 0; j <= i; j++) {
if (arr[j] > arr[max]) max = j
}
let temp = arr[i]
arr[i] = arr[max]
arr[max] = temp
}
}
插入排序
const insertionSort = arr => {
for (let i = 1; i < arr.length; i++) {
let temp = arr[i]
for (var j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j]
}
arr[j + 1] = temp
}
}
希尔排序
const shellSort = arr => {
for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
for (let i = gap; i < arr.length; i++) {
let temp = arr[i]
for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j]
}
arr[j + gap] = temp
}
}
}
归并排序
const mergeSort = arr => {
if (arr.length <= 1) return arr
let mid = arr.length >> 1
let left = arr.slice(0, mid)
let right = arr.slice(mid)
return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
let result = []
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return result.concat(left, right)
}
堆排序
const heapSort = arr => {
const swap = (i,j) => {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
const maxHeapify = (start,end) => {
let dad = start
let son = dad*2+1
if(son >= end) return
if(son+1<end && arr[son]<arr[son+1]) son++
if(arr[dad] <= arr[son]) {
swap(dad,son)
maxHeapify(son,end)
}
}
let len = arr.length
for(let i=(len>>1)-1;i>=0;i--) maxHeapify(i,len)// bottom parent node
for (let i =len-1;i>0;i--) {
swap(0, i);
maxHeapify(0, i);
}
return arr
}
快速排序
const quickSort = arr => {
const len = arr.length
if (len < 2) return arr
const pivot = arr[0],
left = [],
right = []
for (let i = 1; i < len; i++) {
const item = arr[i]
item >= pivot && right.push(item)
item < pivot && left.push(item)
}
return quickSort(left).concat(pivot, quickSort(right))
}
查找算法
二分查找
- 基本形态
一般来说，mid的溢出在js里还是挺难碰到的。如果有需要的场合的话，换成mid = low + Math.floor((high-low)/2)
function binarySearch (target, arr) {
let low = 0, high = arr.length - 1, mid
while (low <= high) {
mid = Math.floor((high+low)/2)
if (arr[mid] === target) {
return mid
} else if (arr[mid] < target) {
low = mid + 1
} else {
high = mid - 1
}
}
return false
}
- 查找目标值区域左边界
function binarySearch (target, arr) {
let low = 0, high = arr.length - 1, mid
while (low <= high) {
mid = Math.floor((high+low)/2)
if (arr[mid] >= target) {
high = mid - 1
} else {
low = mid + 1
}
}
if(low < A.length && A[low] == target)
return low;
else
return false;
}
