Algoritma mendapatkan semula struktur data javascript dan kemahiran algorithm_javascript

Terdapat dua cara untuk mencari data, carian berjujukan dan carian binari. Carian berurutan berfungsi pada senarai dengan unsur yang disusun secara rawak. Carian binari berfungsi pada senarai elemen yang disusun. Carian binari adalah lebih cekap, tetapi ia mestilah satu set elemen senarai yang diisih.

1: Carian berurutan
Carian berurutan adalah untuk menilai elemen senarai satu demi satu bermula dari elemen pertama senarai sehingga hasil yang diingini ditemui, atau elemen yang dikehendaki tidak ditemui sehingga akhir senarai.

Kod adalah seperti berikut:

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return true;
    }
  }
  return false;
}

Kami juga boleh mengembalikan fungsi carian berjujukan yang sepadan dengan kedudukan elemen Kodnya adalah seperti berikut:

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return i;
    }
  }
  return -1;
}

Dua: Cari nilai minimum dan maksimum

Algoritma untuk mencari nilai minimum dalam tatasusunan adalah seperti berikut:

1. Berikan elemen pertama tatasusunan kepada pembolehubah dan gunakan pembolehubah ini sebagai nilai minimum.
2. Mula melintasi tatasusunan, bermula dari elemen kedua dan membandingkannya dengan nilai minimum semasa.
3. Jika nilai elemen semasa kurang daripada nilai minimum semasa, tetapkan elemen semasa kepada nilai minimum baharu.
4. Beralih ke elemen seterusnya dan ulangi langkah 3.
5. Apabila program tamat, apa yang disimpan dalam pembolehubah ini ialah nilai minimum.

Kod adalah seperti berikut:

function findMin(arr) {
  var min = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

Algoritma untuk mencari nilai maksimum adalah serupa dengan nilai minimum di atas Pertama, tetapkan elemen pertama dalam tatasusunan kepada nilai maksimum, dan kemudian gelung untuk membandingkan setiap elemen tatasusunan yang tinggal dengan nilai maksimum semasa nilai elemen semasa adalah lebih besar daripada nilai Maksimum semasa, kemudian tetapkan nilai elemen kepada nilai maksimum. Kodnya adalah seperti berikut:

function findMax(arr) {
  var max = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
 }

Tiga: Kaedah carian binari.

Jika data yang anda cari tersusun, algoritma carian binari adalah lebih cekap daripada algoritma carian berjujukan. Prinsip asas algoritma carian binari adalah seperti berikut:

1. Tetapkan kedudukan pertama tatasusunan kepada sempadan bawah (0).
2. Tetapkan kedudukan elemen terakhir tatasusunan ke sempadan atas (panjang tatasusunan tolak 1).
3. Jika sempadan bawah sama dengan atau lebih kecil daripada sempadan atas, lakukan perkara berikut:
A. Tetapkan titik tengah kepada (sempadan atas campur sempadan bawah) dibahagikan dengan 2.
B. Jika elemen pada titik tengah lebih kecil daripada nilai pertanyaan, tetapkan sempadan bawah kepada subskrip elemen titik tengah tambah 1.
C. Jika elemen pada titik tengah lebih besar daripada nilai pertanyaan, tetapkan sempadan atas kepada subskrip elemen titik tengah tolak 1.
D. Jika tidak, elemen titik tengah ialah data yang akan ditemui dan boleh dikembalikan.

Kod adalah seperti berikut:

// 二分查找算法
function binSearch(data,arr) {
var lowerBound = 0;
  var upperBound = arr.length - 1;
  while(lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound)/2);
    if(arr[mid] < data) {
      lowerBound = mid + 1;
    }else if(arr[mid] > data) {
      upperBound = mid - 1;
    }else {
      return mid;
    }
  }
  return -1;
}
 // 快速排序
function qSort(list) {
  if(list.length == 0) {
    return [];
  }
  // 存储小于基准值的值
  var left = [];
  // 存储大于基准值的值
  var right = [];
  var pivot = list[0];
  for(var i = 1; i < list.length; i++) {
    if(list[i] < pivot) {
      left.push(list[i]);
    }else {
      right.push(list[i])
    }
  }
  return qSort(left).concat(pivot,qSort(right));
}
 // 测试代码
var numbers = [0,9,1,8,7,6,2,3,5,4];
var list = qSort(numbers);
console.log(binSearch(6,list));

4: Kira bilangan ulangan;
Apabila fungsi binSearch() algoritma carian binari menemui nilai tertentu, jika terdapat nilai lain yang sama dalam set data, maka fungsi tersebut akan diletakkan berhampiran nilai yang serupa, dengan kata lain, nilai lain yang sama mungkin muncul. Bahagian kiri atau kanan nilai yang ditemui.

Kemudian penyelesaian kami yang paling mudah ialah menulis dua gelung, satu yang secara serentak merentasi set data ke bawah atau ke kiri, mengira bilangan ulangan; dan kemudian, melintasi ke atas atau ke kanan, mengira bilangan ulangan. Kodnya adalah seperti berikut:

// 计算重复次数
function count(data,arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data,arr);
  if(position > -1) {
    ++count;
    arrs.push({"index":count});
    for(var i = position -1; i > 0; --i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
    for(var i = position + 1; i < arr.length; ++i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
  }
  return arrs;
}
 // 测试重复次数的代码
var arr = [0,1,1,1,2,3,4,5,6,7,8,9];
var arrs = count(1,arr);
console.log(arrs);
console.log(arrs.length);

Seperti yang ditunjukkan di bawah: