前端学算法之搜索算法
本文将详细介绍搜索算法的实现
顺序搜索
顺序或线性搜索是最基本的搜索算法。它的机制是,将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法
以下是其实现:
this.sequentialSearch = function(item){ for (var i=0; i<array.length; i++){ //{1} if (item === array[i]) //{2} return i; //{3} } } return -1; //{4} };
顺序搜索迭代整个数组(行{1}),并将每个数组元素和搜索项作比较(行{2})。如果搜索到了,算法将用返回值来标示搜索成功。返回值可以是该搜索项本身,或是true,又或是搜索项的索引(行{3})。如果没有找到该项,则返回-1(行{4}),表示该索引不存在;也可以考虑返回false或者null
假定有数组[5, 4, 3, 2, 1]和待搜索值3,下图展示了顺序搜索的示意图:
二分搜索
二分搜索算法的原理和猜数字游戏类似,就是那个有人说“我正想着一个1到100的数字”的游戏。我们每回应一个数字,那个人就会说这个数字是高了、低了还是对了
这个算法要求被搜索的数据结构已排序。以下是该算法遵循的步骤。
1、选择数组的中间值
2、如果选中值是待搜索值,那么算法执行完毕(值找到了)
3、如果待搜索值比选中值要小,则返回步骤1并在选中值左边的子数组中寻找
4、如果待搜索值比选中值要大,则返回步骤1并在选种值右边的子数组中寻找
以下是其实现:
this.binarySearch = function(item){ this.quickSort(); var low = 0, high = array.length - 1, mid, element; while (low <= high){ mid = Math.floor((low + high) / 2); element = array[mid]; console.log('mid element is ' + element); if (element < item) { low = mid + 1; console.log('low is ' + low); } else if (element > item) { high = mid - 1; console.log('high is ' + high); } else { console.log('found it'); return mid; } } return -1; }; var partition = function(array, left, right) { var pivot = array[Math.floor((right + left) / 2)], i = left, j = right; console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right); while (i <= j) { while (array[i] < pivot) { i++; console.log('i = ' + i); } while (array[j] > pivot) { j--; console.log('j = ' + j); } if (i <= j) { console.log('swap ' + array[i] + ' with ' + array[j]); swap(array, i, j); i++; j--; } } return i; }; var quick = function(array, left, right){ var index; if (array.length > 1) { index = partition(array, left, right); if (left < index - 1) { quick(array, left, index - 1); } if (index < right) { quick(array, index, right); } } return array; }; this.quickSort = function(){ quick(array, 0, array.length - 1); };
开始前需要先将数组排序,可以选择任何一个排序算法。这里我们选择了快速排序。在数组排序之后,我们设置low(行{2})和high(行{3})指针(它们是边界)
当low比high小时(行{4}),我们计算得到中间项索引并取得中间项的值,此处如果low比high大,则意思是该待搜索值不存在并返回-1(行{12})。接着,我们比较选中项的值和搜索值(行{7})。如果小了,则选择数组低半边并重新开始。如果选中项的值比搜索值大了,则选择数组高半边并重新开始。若两者都是不是,则意味着选中项的值和搜索值相等,因此,直接返回该索引(行{11})
给定下图所示数组,让我们试试看搜索2。这些是算法将会执行的步骤:
【完整代码】
下面是排序和搜索算法的完整代码
function ArrayList(){ var array = []; this.insert = function(item){ array.push(item); }; var swap = function(array, index1, index2){ var aux = array[index1]; array[index1] = array[index2]; array[index2] = aux; //ES2015 swap - Firefox only, for other browser, uncomment code above and coment line below //[array[index1], array[index2]] = [array[index2], array[index1]]; }; this.toString= function(){ return array.join(); }; this.array= function(){ return array; }; this.bubbleSort = function(){ var length = array.length; for (var i=0; i<length; i++){ console.log('--- '); for (var j=0; j<length-1; j++ ){ console.log('compare ' + array[j] + ' with ' + array[j+1]); if (array[j] > array[j+1]){ console.log('swap ' + array[j] + ' with ' + array[j+1]); swap(array, j, j+1); } } } }; this.modifiedBubbleSort = function(){ var length = array.length; for (var i=0; i<length; i++){ console.log('--- '); for (var j=0; j<length-1-i; j++ ){ console.log('compare ' + array[j] + ' with ' + array[j+1]); if (array[j] > array[j+1]){ console.log('swap ' + array[j] + ' with ' + array[j+1]); swap(j, j+1); } } } }; this.selectionSort = function(){ var length = array.length, indexMin; for (var i=0; i<length-1; i++){ indexMin = i; console.log('index ' + array[i]); for (var j=i; j<length; j++){ if(array[indexMin]>array[j]){ console.log('new index min ' + array[j]); indexMin = j; } } if (i !== indexMin){ console.log('swap ' + array[i] + ' with ' + array[indexMin]); swap(i, indexMin); } } }; this.insertionSort = function(){ var length = array.length, j, temp; for (var i=1; i<length; i++){ j = i; temp = array[i]; console.log('to be inserted ' + temp); while (j>0 && array[j-1] > temp){ console.log('shift ' + array[j-1]); array[j] = array[j-1]; j--; } console.log('insert ' + temp); array[j] = temp; } }; var insertionSort_ = function(array){ var length = array.length, j, temp; for (var i=1; i<length; i++){ j = i; temp = array[i]; while (j>0 && array[j-1] > temp){ array[j] = array[j-1]; j--; } array[j] = temp; } }; this.mergeSort = function(){ array = mergeSortRec(array); }; var mergeSortRec = function(array){ var length = array.length; if(length === 1) { console.log(array); return array; } var mid = Math.floor(length / 2), left = array.slice(0, mid), right = array.slice(mid, length); return merge(mergeSortRec(left), mergeSortRec(right)); }; var merge = function(left, right){ var result = [], il = 0, ir = 0; while(il < left.length && ir < right.length) { if(left[il] < right[ir]) { result.push(left[il++]); } else{ result.push(right[ir++]); } } while (il < left.length){ result.push(left[il++]); } while (ir < right.length){ result.push(right[ir++]); } console.log(result); return result; }; this.quickSort = function(){ quick(array, 0, array.length - 1); }; var partition = function(array, left, right) { var pivot = array[Math.floor((right + left) / 2)], i = left, j = right; console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right); while (i <= j) { while (array[i] < pivot) { i++; console.log('i = ' + i); } while (array[j] > pivot) { j--; console.log('j = ' + j); } if (i <= j) { console.log('swap ' + array[i] + ' with ' + array[j]); swap(array, i, j); i++; j--; } } return i; }; var quick = function(array, left, right){ var index; if (array.length > 1) { index = partition(array, left, right); if (left < index - 1) { quick(array, left, index - 1); } if (index < right) { quick(array, index, right); } } return array; }; this.heapSort = function(){ var heapSize = array.length; buildHeap(array); while (heapSize > 1) { heapSize--; console.log('swap (' + + array[0] + ',' + array[heapSize] + ')'); swap(array, 0, heapSize); console.log('heapify ' + array.join()); heapify(array, heapSize, 0); } }; var buildHeap = function(array){ console.log('building heap'); var heapSize = array.length; for (var i = Math.floor(array.length / 2); i >= 0; i--) { heapify(array, heapSize, i); } console.log('heap created: ' + array.join()); }; var heapify = function(array, heapSize, i){ var left = i * 2 + 1, right = i * 2 + 2, largest = i; if (left < heapSize && array[left] > array[largest]) { largest = left; } if (right < heapSize && array[right] > array[largest]) { largest = right; } console.log('Heapify Index = '+ i + ' and Heap Size = ' + heapSize); if (largest !== i) { console.log('swap index ' + i + ' with ' + largest + ' (' + + array[i] + ',' + array[largest] + ')'); swap(array, i, largest); console.log('heapify ' + array.join()); heapify(array, heapSize, largest); } }; this.countingSort = function(){ var i, maxValue = this.findMaxValue(), sortedIndex = 0, counts = new Array(maxValue + 1); for (i = 0; i < array.length; i++) { if (!counts[array[i]]) { counts[array[i]] = 0; } counts[array[i]]++; } console.log('Frequencies: ' + counts.join()); for (i = 0; i < counts.length; i++) { while (counts[i] > 0) { array[sortedIndex++] = i; counts[i]--; } } }; this.bucketSort = function(bucketSize){ var i, minValue = this.findMinValue(), maxValue = this.findMaxValue(), BUCKET_SIZE = 5; console.log('minValue ' + minValue); console.log('maxValue ' + maxValue); bucketSize = bucketSize || BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets = new Array(bucketCount); console.log('bucketSize = ' + bucketCount); for (i = 0; i < buckets.length; i++) { buckets[i] = []; } for (i = 0; i < array.length; i++) { buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]); console.log('pushing item ' + array[i] + ' to bucket index ' + Math.floor((array[i] - minValue) / bucketSize)); } array = []; for (i = 0; i < buckets.length; i++) { insertionSort_(buckets[i]); console.log('bucket sorted ' + i + ': ' + buckets[i].join()); for (var j = 0; j < buckets[i].length; j++) { array.push(buckets[i][j]); } } }; this.radixSort = function(radixBase){ var i, minValue = this.findMinValue(), maxValue = this.findMaxValue(), radixBase = radixBase || 10; // Perform counting sort for each significant digit), starting at 1 var significantDigit = 1; while (((maxValue - minValue) / significantDigit) >= 1) { console.log('radix sort for digit ' + significantDigit); array = countingSortForRadix(array, radixBase, significantDigit, minValue); console.log(array.join()); significantDigit *= radixBase; } }; var countingSortForRadix = function(array, radixBase, significantDigit, minValue){ var i, countsIndex, counts = new Array(radixBase), aux = new Array(radixBase); for (i = 0; i < radixBase; i++) { counts[i] = 0; } for (i = 0; i < array.length; i++) { countsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase); counts[countsIndex]++; } for (i = 1; i < radixBase; i++) { counts[i] += counts[i - 1]; } for (i = array.length - 1; i >= 0; i--) { countsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase); aux[--counts[countsIndex]] = array[i]; } for (i = 0; i < array.length; i++) { array[i] = aux[i]; } return array; }; this.sequentialSearch = function(item){ for (var i=0; i<array.length; i++){ if (item === array[i]){ return i; } } return -1; }; this.findMaxValue = function(){ var max = array[0]; for (var i=1; i<array.length; i++){ if (max < array[i]){ max = array[i]; } } return max; }; this.findMinValue = function(){ var min = array[0]; for (var i=1; i<array.length; i++){ if (min > array[i]){ min = array[i]; } } return min; }; this.binarySearch = function(item){ this.quickSort(); var low = 0, high = array.length - 1, mid, element; while (low <= high){ mid = Math.floor((low + high) / 2); element = array[mid]; console.log('mid element is ' + element); if (element < item) { low = mid + 1; console.log('low is ' + low); } else if (element > item) { high = mid - 1; console.log('high is ' + high); } else { console.log('found it'); return mid; } } return -1; }; }