Javascript_javascriptスキルでクイックソートを実装するためのアルゴリズムの詳細な説明-jsチュートリアル-php.cn

Javascript_javascriptスキルでクイックソートを実装するためのアルゴリズムの詳細な説明

WBOY

リリース： 2016-05-16 15:40:43

オリジナル

1049 人が閲覧しました

現在、最も一般的な並べ替えアルゴリズムは 7 ～ 8 つありますが、その中で「クイックソート」が最も広く使用されており、高速です。 1960 年にチューリング賞受賞者の C. A. R. ホア (1934--) によって提案されました。

「クイックソート」のアイデアは非常にシンプルです。ソートプロセス全体に必要なステップは 3 つだけです:

。

(1) データセットで、「ピボット」として要素を選択します。

(2) "base" より小さいすべての要素は "base" の左側に移動され、"base" より大きいすべての要素は "base" の右側に移動されます。

(3) 「ベースライン」の左右の 2 つのサブセットに対して、すべてのサブセットに要素が 1 つだけ残るまで、1 番目と 2 番目の手順を繰り返します。

たとえば、{85, 24, 63, 45, 17, 31, 96, 50} というデータセットがあります。これをソートするにはどうすればよいでしょうか?

最初のステップは、中央の要素 45 を「ベースライン」として選択することです。 (基準値は任意に選べますが、真ん中の値を選んだ方が分かりやすいです。)

2 番目のステップは、各要素を「ベースライン」と比較して、2 つのサブセット (1 つは「45 未満」、もう 1 つは「45 以上」) を形成することです。

3 番目のステップでは、すべてのサブセットに 1 つの要素だけが残るまで、2 つのサブセットに対して最初と 2 番目のステップを繰り返します。

以下はインターネット上の情報を参照し、JavaScript言語を使用して上記のアルゴリズムを実装しています。

まず、パラメータが配列である QuickSort 関数を定義します。

var quickSort = function(arr) {
};

ログイン後にコピー

次に、配列の要素数を確認し、1以下であればそれを返します。

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
};

ログイン後にコピー

次に、「ピボット」を選択して元の配列から分離し、左側と右側の 2 つのサブセットを格納する 2 つの空の配列を定義します。

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
};

ログイン後にコピー

次に、配列の走査を開始し、「ベースライン」より小さい要素を左側のサブセットに配置し、「ベースライン」より大きい要素を右側のサブセットに配置します。

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
};

ログイン後にコピー

最後に、再帰を使用してこのプロセスを繰り返し、ソートされた配列を取得します。

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1);
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat(pivot, quickSort(right));
};
 
var dataArray = [85,24,63,45,17,31,96,50];
console.log(dataArray.join(","));
console.log(quickSort(dataArray).join(","));

ログイン後にコピー

この記事が皆様の JavaScript プログラミング設計に役立つことを願っています。