ホームページ > 記事 > ウェブフロントエンド > クイックソートアルゴリズムのJavaScript実装のコードグラフィック解析
クイックソートアルゴリズムのJavaScript実装のコードグラフィック解析
- 黄舟オリジナル
- 2017-04-15 09:31:271528ブラウズ
この記事では、主に JavaScript に基づくクイック ソート アルゴリズムを紹介し、クイック ソートの原理を分析し、JavaScript クイック ソートの操作手順と関連実装テクニックを例の形で提供します。必要な友達はこの記事を参照してください。
この例では、JavaScript に基づいたクイック並べ替えアルゴリズムについて説明します。詳細は以下の通りです: まず、バブルソートのプロセスは非常に簡単ですまず、最初のレコードのキーワードを結合します。 2 番目のレコードのキーワードとの比較が行われ、順序が逆の場合は 2 つのキーが交換され、最後の比較が完了するまで 2 番目と 3 番目のキーが比較されます。これが最初のバブリングであり、その結果、最大のキーワードを持つレコードが最後の位置に配置されます。次に、シーケンスの最初の n-1 個の要素を 2 度目にバブルし、最後から 2 番目の要素を選択します。すべてが選択されて泡立ちが終わるまで、同様に続きます。 分析により、バブルソートの時間計算量はO(n2)
であると結論付けることができます。クイックソートはバブルソートを改良したもので、大規模なデータセット
を処理するための最も高速なソート方法の1つであり、異なるサブシーケンスの再帰を通じてデータを順番に小さな要素と大きな要素に分割します。すべてのデータが整うまでこのプロセスが繰り返されます。 このアルゴリズムは、まずベースライン値を選択し、ベースライン値を中心に処理を進める必要があります。 例は次のとおりです。
アルゴリズムのアイデアは次のとおりです:
リストを並べ替えて、すべての要素をベンチマーク要素を前に置き、大きい方を後ろに置きます
小さい要素のサブシーケンスと大きい要素のサブシーケンスに対してそれぞれ上記の 2 つの手順を繰り返します。
次のように
jsを通じてコードを実装します:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>JavaScript快速排序</title>
</head>
<body>
<script type="text/javascript">
function qSort(nums) {//快速排序
if(nums.length==0){
return [];
}
var lesser=[];
var greater=[];
var pivot=nums[0];//选择基准元素
for(var i=1;i<nums.length;i++){
if(nums[i]<pivot){//分成两个之序列
lesser.push(nums[i]);
}else{
greater.push(nums[i]);
}
}
return qSort(lesser).concat(pivot,qSort(greater));//递归
}
function show(nums){//显示数组
for(var i=0;i<nums.length;i++){
document.write(nums[i]+' ');
}
document.write('<br>');
}
var nums=[68,80,12,80,95,70,79,27,88,93];
show(nums);//newNums
var newNums=qSort(nums);//希尔排序
show(newNums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html> 平均時間の観点からは、クイック ソートが現在最良の内部ソート方法であると考えられています。クイック ソートは大規模なデータ セットに非常に適していますが、小さなデータ セットを処理する場合はパフォーマンスが低下します。その時間計算量は O(nlog2n)
以上がクイックソートアルゴリズムのJavaScript実装のコードグラフィック解析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。