共计 7737 个字符,预计需要花费 20 分钟才能阅读完成。
Typescript 版本的排序和搜索算法
排序算法
算法中用到的公共函数
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
EQUALS: 0
};
const DOES_NOT_EXIST = -1;
function lesserEquals(a, b, compareFn) {const comp = compareFn(a, b);
return comp === Compare.LESS_THAN || comp === Compare.EQUALS;
}
function biggerEquals(a, b, compareFn) {const comp = compareFn(a, b);
return comp === Compare.BIGGER_THAN || comp === Compare.EQUALS;
}
function defaultCompare(a, b) {if (a === b) {return Compare.EQUALS;}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
function defaultEquals(a, b) {return a === b;}
function defaultToString(item) {if (item === null) {return 'NULL';} else if (item === undefined) {return 'UNDEFINED';} else if (typeof item === 'string' || item instanceof String) {return `${item}`;
}
return item.toString();}
function swap(array, a, b) {[array[a], array[b]] = [array[b], array[a]];
}
function reverseCompare(compareFn) {return (a, b) => compareFn(b, a);
}
function defaultDiff(a, b) {return Number(a) - Number(b);
}
冒泡排序
function bubbleSort(array, compareFn = defaultCompare) {const { length} = array;
for (let i = 0; i < length; i++) {// console.log('---');
for (let j = 0; j < length - 1; j++) {// console.log('compare' + array[j] + 'with' + array[j + 1]);
if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {// console.log('swap' + array[j] + 'with' + array[j + 1]);
swap(array, j, j + 1);
}
}
}
return array;
}
改进的冒泡排序 (减少中间比较)
function modifiedBubbleSort(array, compareFn = defaultCompare) {const { length} = array;
for (let i = 0; i < length; i++) {// console.log('---');
for (let j = 0; j < length - 1 - i; j++) {// console.log('compare' + array[j] + 'with' + array[j + 1]);
if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {// console.log('swap' + array[j] + 'with' + array[j + 1]);
swap(array, j, j + 1);
}
}
}
return array;
}
选择排序
function selectionSort (array, compareFn = defaultCompare) => {const { length} = array;
let indexMin;
for (let i = 0; i < length - 1; i++) {
indexMin = i;
// console.log('index' + array[i]);
for (let j = i; j < length; j++) {if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {// console.log('new index min' + array[j]);
indexMin = j;
}
}
if (i !== indexMin) {// console.log('swap' + array[i] + 'with' + array[indexMin]);
swap(array, i, indexMin);
}
}
return array;
};
插入排序
function insertionSort (array, compareFn = defaultCompare) => {const { length} = array;
let temp;
for (let i = 1; i < length; i++) {
let j = i;
temp = array[i];
// console.log('to be inserted' + temp);
while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {// console.log('shift' + array[j - 1]);
array[j] = array[j - 1];
j--;
}
// console.log('insert' + temp);
array[j] = temp;
}
return array;
};
归并排序
function merge(left, right, compareFn) {
let i = 0;
let j = 0;
const result = [];
while (i < left.length && j < right.length) {result.push(compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
}
return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
function mergeSort(array, compareFn = defaultCompare) {if (array.length > 1) {const { length} = array;
const middle = Math.floor(length / 2);
const left = mergeSort(array.slice(0, middle), compareFn);
const right = mergeSort(array.slice(middle, length), compareFn);
array = merge(left, right, compareFn);
}
return array;
}
快速排序
// 划分过程
function partition(array, left, right, compareFn) {const pivot = array[Math.floor((right + left) / 2)];
let i = left;
let j = right;
while (i <= j) {while (compareFn(array[i], pivot) === Compare.LESS_THAN) {i++;}
while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {j--;}
if (i <= j) {swap(array, i, j);
i++;
j--;
}
}
return i;
}
function quick(array, left, right, compareFn) {
let index;
if (array.length > 1) {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 quickSort(array, compareFn = defaultCompare) {return quick(array, 0, array.length - 1, compareFn);
}
计数排序
function countingSort(array) {if (array.length < 2) {return array;}
const maxValue = findMaxValue(array);
let sortedIndex = 0;
const counts = new Array(maxValue + 1);
array.forEach(element => {if (!counts[element]) {counts[element] = 0;
}
counts[element]++;
});
// console.log('Frequencies:' + counts.join());
counts.forEach((element, i) => {while (element > 0) {array[sortedIndex++] = i;
element--;
}
});
return array;
}
桶排序
// 引入前面的插入排序
import {insertionSort} from './insertion-sort';
function createBuckets(array, bucketSize) {let minValue = array[0];
let maxValue = array[0];
for (let i = 1; i < array.length; i++) {if (array[i] < minValue) {minValue = array[i];
} else if (array[i] > maxValue) {maxValue = array[i];
}
}
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
const buckets = [];
for (let i = 0; i < bucketCount; i++) {buckets[i] = [];}
for (let i = 0; i < array.length; i++) {buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
}
return buckets;
}
function sortBuckets(buckets) {const sortedArray = [];
for (let i = 0; i < buckets.length; i++) {if (buckets[i] != null) {insertionSort(buckets[i]);
sortedArray.push(...buckets[i]);
}
}
return sortedArray;
}
function bucketSort(array, bucketSize = 5) {if (array.length < 2) {return array;}
const buckets = createBuckets(array, bucketSize);
return sortBuckets(buckets);
}
基数排序
function findMaxValue(array, compareFn = defaultCompare) {if (array && array.length > 0) {let max = array[0];
for (let i = 1; i < array.length; i++) {if (compareFn(max, array[i]) === Compare.LESS_THAN) {max = array[i];
}
}
return max;
}
return undefined;
}
function findMinValue(array, compareFn = defaultCompare) {if (array && array.length > 0) {let min = array[0];
for (let i = 1; i < array.length; i++) {if (compareFn(min, array[i]) === Compare.BIGGER_THAN) {min = array[i];
}
}
return min;
}
return undefined;
}
const getBucketIndex = (value, minValue, significantDigit, radixBase) =>
Math.floor(((value - minValue) / significantDigit) % radixBase);
const countingSortForRadix = (array, radixBase, significantDigit, minValue) => {
let bucketsIndex;
const buckets = [];
const aux = [];
for (let i = 0; i < radixBase; i++) {buckets[i] = 0;
}
for (let i = 0; i < array.length; i++) {bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase);
buckets[bucketsIndex]++;
}
for (let i = 1; i < radixBase; i++) {buckets[i] += buckets[i - 1];
}
for (let i = array.length - 1; i >= 0; i--) {bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase);
aux[--buckets[bucketsIndex]] = array[i];
}
for (let i = 0; i < array.length; i++) {array[i] = aux[i];
}
return array;
};
function radixSort(array, radixBase = 10) {if (array.length < 2) {return array;}
const minValue = findMinValue(array);
const maxValue = findMaxValue(array);
// Perform counting sort for each significant digit, starting at 1
let significantDigit = 1;
while ((maxValue - minValue) / significantDigit >= 1) {array = countingSortForRadix(array, radixBase, significantDigit, minValue);
significantDigit *= radixBase;
}
return array;
}
搜索算法
顺序搜索
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;
}
二分搜索
// 引入文章前面的快速排序方法
import {quickSort} from 'quicksort';
function binarySearch(array, value, compareFn = defaultCompare) {const sortedArray = quickSort(array);
let low = 0;
let high = sortedArray.length - 1;
while (low <= high) {const mid = Math.floor((low + high) / 2);
const element = sortedArray[mid];
// console.log('mid element is' + element);
if (compareFn(element, value) === Compare.LESS_THAN) {
low = mid + 1;
// console.log('low is' + low);
} else if (compareFn(element, value) === Compare.BIGGER_THAN) {
high = mid - 1;
// console.log('high is' + high);
} else {// console.log('found it');
return mid;
}
}
return DOES_NOT_EXIST;
}
内插搜索
// 引入前面的工具函数和相关变量
import {
biggerEquals,
Compare,
defaultCompare,
defaultEquals,
defaultDiff,
DOES_NOT_EXIST,
lesserEquals
} from '../../util';
function interpolationSearch(
array,
value,
compareFn = defaultCompare,
equalsFn = defaultEquals,
diffFn = defaultDiff
) {const { length} = array;
let low = 0;
let high = length - 1;
let position = -1;
let delta = -1;
while (
low <= high &&
biggerEquals(value, array[low], compareFn) &&
lesserEquals(value, array[high], compareFn)
) {delta = diffFn(value, array[low]) / diffFn(array[high], array[low]);
position = low + Math.floor((high - low) * delta);
if (equalsFn(array[position], value)) {return position;}
if (compareFn(array[position], value) === Compare.LESS_THAN) {low = position + 1;} else {high = position - 1;}
}
return DOES_NOT_EXIST;
}
随机算法 Fisher—Yates(洗扑克牌)
function shuffle(array) {for(let i=array.length;i>0;i--) {const randomIndex = Math.floor(Math.random()*(i+1));
swap(array, i, randomIndex);
}
return array;
}
正文完
发表至: javascript
2019-11-18