欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

前端学算法之搜索算法

程序员文章站 2023-12-29 23:37:46
前面的话 本文将详细介绍搜索算法的实现 顺序搜索 顺序或线性搜索是最基本的搜索算法。它的机制是,将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法 以下是其实现: 顺序搜索迭代整个数组(行{1}),并将每个数组元素和搜索项作比较(行{2})。如果搜索到了,算法将用返回值来 ......
前面的话

  本文将详细介绍搜索算法的实现

 

顺序搜索

  顺序或线性搜索是最基本的搜索算法。它的机制是,将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法

  以下是其实现:

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;
    };

}

 

 

上一篇:

下一篇: