ホームページ > 記事 > ウェブフロントエンド > JavaScript がクイックソートを実装する方法の詳細なコード説明
この記事の内容は、JavaScript でクイックソートを実装する方法を共有することです。必要な友人はそれを参照できます
偶然、Ruan Yifeng 先生のブログでクイックソートアルゴリズムをいくつか見ました。各ループでは 2 つの追加の配列が作成され、データ量が多い場合は余分なメモリが大量に消費されます。ただし、配列は参照型であり、元の配列自体を直接操作してメモリを節約できます。
クイックソート方法の鍵は、値を選択し、配列全体を左側の小さい部分と右側の大きい部分の 2 つの部分に分割することです。この関数の書き方は次のとおりです:
//该函数的主要目的是交换数组中两个元素的位置 function swap(arr, index1, index2) { let data = arr[index1]; arr[index1] = arr[index2]; arr[index2] = arr[index1]; //数组是引用类型,允许修改原数组。 } //选取随机值,将数组分为两部分 function partition(arr, start, end) { let keyIndex = end, key = arr[keyIndex]; //将随机值(以后称key值)定为最后一个数,也可以真的随机选取,见下一行 // let keyIndex = Math.floor(Math.random() * (end - start)) + start; let i = start, j = end, order = true; //当order为true时正向筛选,当order为false时逆向筛选 //先从正向开始,因为我们把key值保存到了数组的结尾处。 while(i != j) { if(order) { //正向筛选 if (arr[i]>key) { swap(arr, i, j); //将大于key的数字和key进行交换 order = false; } else { i++; } } else { //逆向筛选 if(arr[j]<key) { swap(arr, i, j); //将小于key的数字和key进行交换 order = true; } else { j--; } } } return i;//返回key值最终的位置 }
です。実際、グループ化アルゴリズムのパーティションを観察することで見つけるのは難しくありません。実際、i の位置には常にキー値が格納されており、それより大きい値または小さい値と交換されます。次に、それを一方向のグループ化メソッドとして記述することもできます:
function partition2(arr, start, end) { let keyIndex = end, key = arr[end]; let i = start -1, j = start; for (;j<end;j++) { if (arr[j]< key) { // i位置的值永远比key值小 i++; if (i != j) { swap(arr, i, j); } } } ++i; swap(arr, i, end); return i; //返回key值最终的位置 }
次に、グループ化関数を再帰的に呼び出して配列全体を並べ替えます:
function quickSort(arr, start, end) { if (start == end) return; let index = partition(arr, start, end); if (index > start){ quickSort(arr, start, index-1); } if (index<end) { quickSort(arr, index+1, end); } }
関連する推奨事項:
以上がJavaScript がクイックソートを実装する方法の詳細なコード説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。