JS版本排序和搜索算法

# 排序算法

## 算法中用到的公共函数

``````type ICompareFunction = (a: T, b: T) => number;

type IEqualsFunction = (a: T, b: T) => boolean;

type IDiffFunction = (a: T, b: T) => number;

const DOES_NOT_EXIST = -1;

enum Compare {
LESS_THAN = -1,
BIGGER_THAN = 1,
EQUALS = 0
}

function lesserEquals(a: T, b: T, compareFn: ICompareFunction) {
const comp = compareFn(a, b);
return comp === Compare.LESS_THAN || comp === Compare.EQUALS;
}

function biggerEquals(a: T, b: T, compareFn: ICompareFunction) {
const comp = compareFn(a, b);
return comp === Compare.BIGGER_THAN || comp === Compare.EQUALS;
}

function defaultCompare(a: T, b: T): number {
if (a === b) {
return Compare.EQUALS;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

function defaultEquals(a: T, b: T): boolean {
return a === b;
}

function defaultToString(item: any): string {
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: any[], a: number, b: number) {
[array[a], array[b]] = [array[b], array[a]];
}

function reverseCompare(compareFn: ICompareFunction): ICompareFunction {
return (a, b) => compareFn(b, a);
}

function defaultDiff(a: T, b: T): number {
return Number(a) - Number(b);
}
``````

## 冒泡排序

``````function bubbleSort(array: T[], compareFn = defaultCompare) {
const { length } = array;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - 1; j++) {
if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
swap(array, j, j + 1);
}
}
}
return array;
}``````

## 改进的冒泡排序

``````function modifiedBubbleSort(array: T[], compareFn = defaultCompare) {
const { length } = array;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - 1 - i; j++) {
if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
swap(array, j, j + 1);
}
}
}
return array;
}``````

## 选择排序

``````function selectionSort(array: any[], compareFn = defaultCompare) {
const { length } = array;
let indexMin;

for (let i = 0; i < length - 1; i++) {
indexMin = i;
for (let j = i; j < length; j++) {
if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {
indexMin = j;
}
}
if (i !== indexMin) {
swap(array, i, indexMin);
}
}
return array;
};``````

## 插入排序

``````function insertionSort(array: any[], compareFn = defaultCompare) {
const { length } = array;
let temp;
for (let i = 1; i < length; i++) {
let j = i;
temp = array[i];
while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
return array;
};``````

## 归并排序

``````function merge(left: T[], right: T[], compareFn: ICompareFunction) {
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: T[], compareFn = defaultCompare): T[] {
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: any[], left: number, right: number, compareFn: ICompareFunction) {
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: any[],
left: number,
right: number,
compareFn: ICompareFunction
) {
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: any[], compareFn = defaultCompare) {
return quick(array, 0, array.length - 1, compareFn);
};``````

## 计数排序

``````function findMaxValue(array: T[], 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 countingSort(array: number[]) {
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]++;
});
counts.forEach((element, i) => {
while (element > 0) {
array[sortedIndex++] = i;
element--;
}
});
return array;
}``````

## 桶排序

``````// 引入插入排序
import { insertionSort } from './insertion-sort';

function createBuckets(array: number[], bucketSize: number): number[][] {
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: number[][]) {
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: number[], bucketSize = 5) {
if (array.length < 2) {
return array;
}
const buckets = createBuckets(array, bucketSize);
return sortBuckets(buckets);
}``````

## 基数排序

``````function findMaxValue(array: T[], 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: T[], 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;
}
array: number[],
significantDigit: number,
minValue: any
) => {
let bucketsIndex;
const buckets: number[] = [];
const aux: number[] = [];
for (let i = 0; i < radixBase; i++) {
buckets[i] = 0;
}
for (let i = 0; i < array.length; i++) {
bucketsIndex = Math.floor(((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 = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
aux[--buckets[bucketsIndex]] = array[i];
}
for (let i = 0; i < array.length; i++) {
array[i] = aux[i];
}
return array;
};
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) {
}
return array;
}``````

## 堆排序

``````function heapify(array: any[], index: number, heapSize: number, compareFn: ICompareFunction) {
let largest = index;
const left = (2 * index) + 1;
const right = (2 * index) + 2;
if (left < heapSize && compareFn(array[left], array[index]) > 0) {
largest = left;
}
if (right < heapSize && compareFn(array[right], array[largest]) > 0) {
largest = right;
}
if (largest !== index) {
swap(array, index, largest);
heapify(array, largest, heapSize, compareFn);
}
}
function buildMaxHeap(array: any[], compareFn: ICompareFunction) {
for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
heapify(array, i, array.length, compareFn);
}
return array;
}
function heapSort(array: any[], compareFn = defaultCompare) {
let heapSize = array.length;
buildMaxHeap(array, compareFn);
while (heapSize > 1) {
swap(array, 0, --heapSize);
heapify(array, 0, heapSize, compareFn);
}
return array;
}``````

## 希尔排序

``````function shellSort(array: T[], compareFn = defaultCompare) {
let increment = array.length / 2;
while (increment > 0) {
for (let i = increment; i < array.length; i++) {
let j = i;
const temp = array[i];
while (j >= increment && compareFn(array[j - increment], temp) === Compare.BIGGER_THAN) {
array[j] = array[j - increment];
j = j - increment;
}
array[j] = temp;
}
if (increment === 2) {
increment = 1;
} else {
increment = Math.floor(increment * 5 / 11);
}
}
return array;
}``````

# 搜索算法

## 顺序搜索

``````function sequentialSearch(array: T[], value: T, equalsFn: IEqualsFunction = 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: T[], value: T, 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];
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;
}``````

## 二分搜索——递归实现

``````// 引入快速排序
import { quickSort } from 'quicksort';

function binarySearchRecursive(
array: T[],
value: T,
low: number,
high: number,
compareFn = defaultCompare
): number {
if (low <= high) {
const mid = Math.floor((low + high) / 2);
const element = array[mid];

if (compareFn(element, value) === Compare.LESS_THAN) {
return binarySearchRecursive(array, value, mid + 1, high, compareFn);
} else if (compareFn(element, value) === Compare.BIGGER_THAN) {
return binarySearchRecursive(array, value, low, mid - 1, compareFn);
} else {
return mid;
}
}
return DOES_NOT_EXIST;
}
function binarySearch(array: T[], value: T, compareFn = defaultCompare) {
const sortedArray = quickSort(array);
const low = 0;
const high = sortedArray.length - 1;
return binarySearchRecursive(array, value, low, high, compareFn);
}``````

## 内插搜索

``````// 引入前面工具函数
import {
biggerEquals,
Compare,
defaultCompare,
defaultEquals,
defaultDiff,
DOES_NOT_EXIST,
lesserEquals
} from '../../util';

function interpolationSearch(
array: T[],
value: T,
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: T[]) {
for (let i = array.length - 1; i > 0; i--) {
const randomIndex = Math.floor(Math.random() * (i + 1));
swap(array, i, randomIndex);
}
return array;
}``````