JavaScriptデータ構造とアルゴリズムの総括5——並べ替えと検索(発泡体の並べ替え選択の並べ替えの並べ替えの迅速な並べ替えの順序を挿入して、二分ルックアップの補間検索を検索する)
52309 ワード
並べ替え
泡の並べ替え
泡の並べ替えは、隣接するすべての2つの項目を比較し、最初が2番目より大きい場合、それらを交換します.元素の項を正しい順序に上に移動すると、泡が表面に上がるように泡が並べられます.
並べ替えアルゴリズムを選択することは、元のアドレス比較並べ替えアルゴリズムです.並べ替えの大まかな考え方は、データ構造の最小値を見つけて第一位に置くことであり、次に第二小の値を見つけて、第二位に置くことである.
データ要素の位置を決定するたびに、データ要素が下付きになる前に順序付けされたサブシーケンスの正しい位置に挿入されます.は、選択された要素の前のサブシーケンスから、現在の要素が挿入すべき位置 を検索する.は、選択された位置の要素を後に移動し、挿入される要素をこの位置 にコピーします.
クイックソート
高速の並べ替えは最もよく使われている並べ替えアルゴリズムかもしれません.その複雑さはO(nlog(n))であり、性能は一般的に他の複雑さよりO(nlog(n))の順序付けアルゴリズムが良い.は、最初に、行列から1つの値をプライマリ要素(pivot)として選択し、プライマリ要素は任意に選択することができる. は、2つのポインタ(参照)を作成し、左の1つは配列の最初の値を指し、右の1つは配列の最後の値を指す.左のポインタを移動して、メインより大きな値を見つけます.次に、メインより小さい値を見つけたら、左のポインタが右のポインタを超えるまで、それらを交換します.このプロセスは、主要素より小さい値を主要素の前に並べ、主要素より大きい値を主要素の後に並べます.このステップを分割操作といいます. は、次いで、アルゴリズム対分割された小さい配列(主要素より小さい値からなるサブアレイ、および主要素より大きい値からなるサブアレイ)に対して、行列が完全に順序付けされるまでの2つのステップを反復する. は、ソースデータとして最大のヒープを配列で作成する. は、最大ヒープを作成すると、一番大きな値がヒープの最初の位置に格納されます.私たちはこれを山の最後の値に置き換えて、山の大きさを1つ減らします. 最後に、スタックのルートノードを下に移動し、スタックのサイズが1になるまで、ステップ2を繰り返します. 最大スタックを用いて昇順配列の配列(最小から最大まで)を求めた.この配列を降順に並べたいなら、一番小さい山で代えることができます.
順序
順序または線形検索は最も基本的な検索アルゴリズムである.そのメカニズムは、各データ構造の元素と私たちが探している元素を比較することです.逐次検索は最も効率が悪い検索アルゴリズムである.
二分検索はまた、半分割検索とも言われ、秩序ある順序表にのみ適用されます.
補間検索:検索キーワードに基づいて検索テーブルの最大最小レコードキーワードと比較した検索方法.補間ルックアップは、二分ルックアップに基づいて、検索点の選択を適応選択に改善し、検索効率を向上させる.二分割検索のポイントを
泡の並べ替え
泡の並べ替えは、隣接するすべての2つの項目を比較し、最初が2番目より大きい場合、それらを交換します.元素の項を正しい順序に上に移動すると、泡が表面に上がるように泡が並べられます.
// ,
let testArray = [77, 41, 31, 43, 11, 33, 21];
for (let i = 0; i < testArray.length - 1; i++) {
for (let j = 0; j < testArray.length - 1; j++) {
if (testArray[j] > testArray[j + 1]) {
// ，
let t = testArray[i];
testArray[i] = testArray[i + 1];
testArray[i + 1] = t;
}
}
}
document.write(testArray);
// ,
let testArray = [77, 41, 31, 43, 11, 33, 21];
for (let i = 0; i < testArray.length - 1; i++) {
for (let j = 0; j < testArray.length - 1 - i; j++) {
if (testArray[j] > testArray[j + 1]) {
let t = testArray[i];
testArray[i] = testArray[i + 1];
testArray[i + 1] = t;
}
}
}
document.write(testArray);
並べ替えアルゴリズムを選択することは、元のアドレス比較並べ替えアルゴリズムです.並べ替えの大まかな考え方は、データ構造の最小値を見つけて第一位に置くことであり、次に第二小の値を見つけて、第二位に置くことである.
// ,
let testArray = [77, 41, 31, 43, 11, 33, 21];
let indexMin;
//
function swap(array,i,j){
let t = array[i];
array[i]=array[j];
array[j]=t;
}
for (let i = 0; i < testArray.length - 1; i++) {
indexMin = i;
//
for (let j = i; j < testArray.length; j++) {
if (testArray[i] > testArray[j])
indexMin = j;
}
if (i !== indexMin) {
swap(testArray, i, indexMin);
}
}
document.write(testArray);
データ要素の位置を決定するたびに、データ要素が下付きになる前に順序付けされたサブシーケンスの正しい位置に挿入されます.
// ，
let testArray = [77, 41, 31, 43, 11, 33, 21];
let temp,i,j;
for (i = 1; i < testArray.length; i++) {
// ， ， ，
if(testArray[i]<testArray[i-1]){
temp=testArray[i];
//
for(j=i-1;temp<testArray[j];--j){
testArray[j+1]=testArray[j];
}
testArray[j+1]=temp;
}
}
document.write(testArray);
クイックソート
高速の並べ替えは最もよく使われている並べ替えアルゴリズムかもしれません.その複雑さはO(nlog(n))であり、性能は一般的に他の複雑さよりO(nlog(n))の順序付けアルゴリズムが良い.
// ，
var testArray = [77, 41, 31, 43, 11, 33, 21];
//
function quickSort(arr, left, right) {
if (left < right) {
var pivotpos = partition(arr, left, right);
quickSort(arr, left, pivotpos - 1);
quickSort(arr, pivotpos + 1, right);
}
return arr;
}
//
function partition(arr, left, right) {
let pivot = left,index = pivot;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index;
}
//
function swap(array, i, j) {
let t = array[i];
array[i] = array[j];
array[j] = t;
}
// ，
testArray = quickSort(testArray, 0, testArray.length - 1);
document.write(testArray);
let testArray = [77, 41, 31, 43, 11, 33, 21];
function heapSort(array) {
let heapSize = array.length;
buildMaxHeap(array); // 1
while (heapSize > 1) {
swap(array, 0, --heapSize); // 2
heapify(array, 0, heapSize); // 3
}
return array;
}
function buildMaxHeap(array) {
for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) {
heapify(array, i, array.length);
//document.write(testArray);
}
return array;
}
function heapify(arr, index, length) {
var left = 2 * index + 1,
right = 2 * index + 2,
largest = index;
if (left < length && arr[left] > arr[largest]) {
largest = left;
}
if (right < length && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== index) {
swap(arr, index, largest);
heapify(arr, largest, length, );
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
testArray = heapSort(testArray);
document.write(testArray);
順序
順序または線形検索は最も基本的な検索アルゴリズムである.そのメカニズムは、各データ構造の元素と私たちが探している元素を比較することです.逐次検索は最も効率が悪い検索アルゴリズムである.
//
var testArray = [77, 41, 31, 43, 11, 33, 21];
var key = 31;//
function seqSearch(arr,e){
for(let i=0;i<arr.length;i++){
if(arr[i]===e){
return i+1;
}
}
return 0;
}
var index = seqSearch(testArray,key);
if(index){
document.write(key," ",index," ");
}else{
document.write(" ");
}
二分検索はまた、半分割検索とも言われ、秩序ある順序表にのみ適用されます.
//
var testArray = [77, 41, 31, 43, 11, 33, 21];
let key = 31;
function compare(a, b) {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
function binarySearch(arr, e) {
var left = 0, right = arr.length - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] === e) {
return mid + 1;
} else if (arr[mid] > e) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return 0;
}
//sort ， , 。
//
testArray.sort(compare);
document.write(testArray,"
");
var index = binarySearch(testArray, key);
if (index) {
document.write(key, " ", index, " ");
} else {
document.write(" ");
}
補間検索:検索キーワードに基づいて検索テーブルの最大最小レコードキーワードと比較した検索方法.補間ルックアップは、二分ルックアップに基づいて、検索点の選択を適応選択に改善し、検索効率を向上させる.二分割検索のポイントを
mid = left+(e-arr[left])/(arr[right]-arr[left])*(right-left);時間の複雑度に改善します.O(log_;n)アプリケーション:テーブル長が大きいのに対して、キーワード分布が均一なルックアップテーブルでは、補間ルックアップアルゴリズムの平均性能は、折半ルックアップよりもずっと良いです. //
var testArray = [77, 41, 31, 43, 11, 33, 21];
let key = 43;
function compare(a, b) {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
}
function insertSearch(arr,e){
var left = 0, right = arr.length - 1;
while (left <= right) {
var mid = left+(e-arr[left])/(arr[right]-arr[left])*(right-left);
mid = Math.round(mid);
if (arr[mid] === e) {
return mid + 1;
} else if (arr[mid] > e) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return 0;
}
testArray.sort(compare);
document.write(testArray, "
");
var index = insertSearch(testArray, key);
if (index) {
document.write(key, " ", index, " ");
} else {
document.write(" ");
}