JavaScript でクイックソートを実装するためのアルゴリズムのアイデア

この記事では、主に JavaScript のクイック ソートを実装するためのアルゴリズムのアイデアを紹介します。これを必要とする友人に参考にしてもらいます。現在、最も一般的なソート アルゴリズムは 7 つまたは 8 つあります。 , その中でも「クイックソート」が最も広く使用されており、高速です。 1960 年にチューリング賞受賞者のトニー ホール (C. A. R. ホア) によって提案されました。

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

(1) データセットで、要素を「ピボット」(ピボット) として選択します。 ) "pivot" より小さいすべての要素 "base" より大きい要素は "base" の左側に移動します。 "base" より大きいすべての要素は "base" の右側に移動します (3) を繰り返します。 「base」の左右の 2 つのサブセットに対する最初のステップ。すべてのサブセットに 1 つの要素だけが残るまでステップ 1 とステップ 2 を実行します

たとえば、データセット {85, 24, 63, 45 があります。 , 17, 31, 96, 50}、どうやって並べ替えるのですか？

最初のステップは、中央の要素 45 を「ベース」として選択することです (ベース値は任意に選択できますが、中央の値を選択するのは理解しやすいです。)

2番目のステップは、各要素を順番に選択して、要素を「ベースライン」と比較して、2つのサブセット、1つは「45未満」、もう1つは「45以上」を形成することです。 3 番目のステップは、2 つのサブセットに対して最初と 2 番目のステップを繰り返すことです。すべてのサブセットに要素が 1 つだけ残るまで

前のステップに従って、quickSort 関数を定義します:

var quickSort = function(arr) { //参数是一个数组
　　if (arr.length <= 1) { return arr; } //检查数组的元素个数，如果小于等于1，就返回。
　　var pivotIndex = Math.floor(arr.length / 2); //选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。
　　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]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

上記のアニメーションを実装します。

アルゴリズムのアイデア:

要素は「ピボット」と呼ばれ、ピボット値よりも小さいすべての要素が前に配置されるようにシーケンスを並べ替えます。ピボット、およびピボット値より大きいすべての要素がピボットの後ろに配置されます (同じ数値がどちらの側にも配置されます)。これは、パーティション操作と呼ばれます。

基準値より小さい要素と基準値より大きい要素の部分配列を再帰的に合計します。

実装コード:

function quickSort(arr, left, right) { 
　　var len = arr.length,
　　partitionIndex,
　　left = typeof left != 'number' ? 0 : left,
　　right = typeof right != 'number' ? len - 1 : right;
 
 
　　if (left < right) {
　　partitionIndex = partition(arr, left, right);
　　quickSort(arr, left, partitionIndex-1);
　　quickSort(arr, partitionIndex+1, right);
　　}
　　return arr;
}
function partition(arr, left ,right) { // 分区操作
　　var pivot = left,                // 设定基准值（pivot）
　　　　index = pivot + 1;
　　for (var i = index; i <= right; i++) {
　　　　if (arr[i] < arr[pivot]) {
　　　　　　swap(arr, i, index);
　　　　　　index++;
　　　　}
　　}
　　swap(arr, pivot, index - 1);
　　 return index-1;
}
 
function swap(arr, i, j) {
　　var temp = arr[i];
　　arr[i] = arr[j];
　　arr[j] = temp;
}
function partition2(arr, low, high) {
　　let pivot = arr[low];
　　while (low < high) {
　　　　while (low < high && arr[high] > pivot) {
　　　　--high;
　　　　}
　　　　arr[low] = arr[high];
　　　　while (low < high && arr[low] <= pivot) {
　　　　++low;
　　　　}
　　　　arr[high] = arr[low];
　　}
　　arr[low] = pivot;
　　return low;
}
 
function quickSort2(arr, low, high) {
　　if (low < high) {
　　let pivot = partition2(arr, low, high);
　　quickSort2(arr, low, pivot - 1);
　　quickSort2(arr, pivot + 1, high);
　　}
　　return arr;
}

以上がこの記事の内容になります。他の関連コンテンツについては、PHP 中国語 Web サイトに注目してください

1. 関連する推奨事項:

js 配列をランダムに並べ替える方法
3. js は、任意の要素を指定された位置に移動します

以上がJavaScript でクイックソートを実装するためのアルゴリズムのアイデアの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。