Javascriptの実装とソートアルゴリズムの解説（99jsメモ）_JavaScriptスキル

バブルソート

バブリングの原理は、最大の要素または最小の要素を「浮かせる」ことです

挿入ソート、選択ソート、クイックソート、バブルソートはすべて比較ソートです

感想

小数点を前に、大きい数を後ろに置いて、2 つの隣接する数値を順番に比較します。

ステップ 1: 最初と 2 番目の数値を比較し、小数点以下を前に、大きい数値を後ろに置きます。 2 番目の数値と 3 番目の数値を比較するには、小数を前に、大きい数値を後ろに置きます。最後の 2 つの数値を比較するまでこの手順を続け、小数を前に、大きい数値を後ろに置きます。
ステップ 2: 2 番目のパスでも、最初の数値のペアから比較を開始します (2 番目の数値と 3 番目の数値の交換により、最初の数値が 2 番目の数値より小さくなくなっている可能性があるため)、 10 進数が最初に配置され、最後から 2 番目の数値まで比較が継続されます (2 回目のパスの終了時に、2 番目から最後までの位置で新しい最大数値が取得されます)。最後の位置 (実際、シーケンス全体で 2 番目に大きい番号です)。
このようにして、最終的に並べ替えが完了するまで上記のプロセスを繰り返します。
仕分けの際、常に小さい数字が前方に、大きな数字が後方に配置されることになり、泡が上がっていくのと同じことになるため、バブルソートと呼ばれています。
バブルソートアニメーション効果

実装: このコードは比較的単純で、アルゴリズムの中で最も基本的かつ基本的なコードです。 。 。
3つの注意点

1. クラスを交換する方法は、JavaScript の a=[b,b=a][0] を使用することで解決できます。これは非常に賢い方法です。

を置き換えます

コードをコピーします コードは次のとおりです:

var,a,b,temp
温度 = a;
a=b;
b = 温度

今回の交換方法
2. ここで Array.length
がキャッシュされることに注意してください。 3. 最初の数値から最後から n 番目の数値までを比較する埋め込みループに注目してください。n は比較のステップ数です

function bubbleSort(array) {
var l=array.length;
for (var i = 0; i < l; i++) {//比较的step数为数组的长度
for (var j = 0; j < l-i; j++) {//内嵌交换的次数是从第一个数比较到倒数第总长-n个数，n则为比较的step数
if (array[j] < array[j - 1]) {
array[j] = [array[j - 1], array[j - 1] = array[j]][0]//在这里交换元素
}
}
for (var k = 0; k < l; k++) {
console.log(array[k] + ",");
}
console.log('这是第'+(i+1)+'次排序')
}
}
var a = [6,54,6,22,5,7,8,2,34];
bubbleSort(a);

アニメーション効果

並べ替えの挿入
カードを引いて挿入するだけなのでとても簡単です！
アイデア:

1 まず、カードを引くとします。現在手札にあるすべてのカードが empty = [] に設定され、push(arr[0]) を引くとします
2 次のカードを取り出して a に設定し、空の (ソート済み) カードをすべて後ろから前にスキャンします
3. 手札の empty[empty.length-n] (ソート済み) カードが新しい要素より大きい場合、カードを次の位置に移動します (スペースを空けます) empty[empty.length-n]= empty[empty.長さ - n 1]
4 並べ替えたカード empty[empty.length-n] が a
以下になるまで手順 3 を繰り返します。 5空の位置に a を挿入します[empty.length-n]=a
6手順2を繰り返します
ただし、JavaScript コードを実装するのはまだ少し難しいです。コードは次のとおりです:

function insert(arr) {
var l = arr.length;
var empty = [];//空数组，表示我们的手
empty.push(arr[0]);//我们先摸起来一张
for (var i = 1; i < l; i++) {//注意这里起点是1，因为我们已经摸了一张了！
if (arr[i] > empty[empty.length - 1]) {
empty[empty.length] = arr[i]
} //如果比有序数组empty还大，直接放到末尾
for (var j = empty.length; j > 0 && arr[i] < empty[j - 1]; j--) { //从最大值跟arr进行比较，为了给arr腾空。当arr<有序数组的某一位时，就不用移动了。
empty[j] = empty[j - 1]; //向右移动
empty[j - 1] = arr[i]; //把值放到空出来的位置上
}
//console.log(empty)
}
return empty
}

ここでより重要な知識ポイントは、「および」を意味する && 記号です。つまり、式が true になるには両側の条件が満たされる必要があります。
&& 記号は if(a){fun()} が a&&b
に等しい場合に置き換えることもできます。 もう一つの非常に重要なポイント
配列が arr であると仮定すると、その「最後の項目」は arr[arr.length-1] になります。

ソートアニメーション

選択並べ替え
これは単純な並べ替えアルゴリズムでもあります。

もの:

最小の要素を見つけて配列に投入し、次に最小の要素を見つけて配列に投入、というように繰り返します。
まず、ソートされていない配列内の最小の要素を見つけます。この検索方法は、連続的な判断と代入を通じて行うことができます。つまり、配列の最初の要素である array[0] が最小の要素であると仮定し、次にそのシリアル番号を求めます。配列内の「最小の要素」は 0
次に、配列を走査し、配列の 2 番目の要素がそれより小さい場合、2 番目の要素が最小の要素であることを意味し、「0」を「1」に更新します。
走査が完了すると、この系列の最小要素添字が「n」であることがわかり、それを直接取り出して、ソートされたシーケンス (array[n]) の開始位置に格納します
。 次に、ソートされていない残りの要素から最小の要素を探し続け、それをソートされたシーケンスの最後に置きます。このとき調べられる添字は 1 から始まることに注意してください。すでに最小限の要素を選択しているからです。
すべての要素がソートされるまで続きます。

function selectSort(array) {
var min;
var l = array.length;//缓存长度
for (var i = 0; i < l; i++) {//开始进行循环，一共循环l次，就可以找出l个元素了
min = i;//假设第一个为最小元素
for (var j = i + 1; j < l; j++) {//从第一个开始循环，遍历
if (array[min] > array[j])//判断之后的是否比前面的小
min = j;//更新“最小”的下标
}
if (min != i) {//这里因为是在同一个数组内进行操作，所以直接交换元素即可。比如数组第一项是i，那么我找出了最小元素为array[min],那么我就需要把这个min跟i交换。以此类推。
array[i]= [array[min],array[min]=array[i]][0];//交换元素
}
}
return array;
}

这里仍然注意的是交换的写法 array[i]= [array[min],array[min]=array[i]][0]
可以方便的把array[i]与array[min]交换~

排序动画

快速排序
 
快速排序是目前最强大的排序算法，算法利用了递归的思想。
 
思路

从数组中挑出一个元素，称为 “基准”，这个可以直接利用length/2挑出来
遍历数组，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。通俗来讲：男的站左边，女的站右边。。
之后我们得到了一个这样的数组 array= 比基准小的部分组成的数组lArray+基准+比基准大的部分组成的数组rArray。
那么我们之后只需要再把lArray,rArray进行“同样的”处理即可~
这就需要用到 递归 的写法了。处理之后，lArray又分成了 lArray的基准，比lArray基准还小的，比lArray基准还大的。。
那么我们不断的进行操作，男的站左边，女的站右边。。
直到我们发现，lArray的长度变成1了，不足以再分下去了，我们认为排序结束。

function quickSort(arr) {
var l = arr.length;//缓存数组长度
if(arr.length <= 1){return arr}; //如果我们拿到的lArray,rArray长度比1都小，那就不用排了~
var num = Math.floor(arr.length / 2);//取数组中间的那个数。注意length/2不一定是整数，用Math.floor取整
var numValue = arr.splice(num, 1)[0];//利用splice方法，取一个元素出来，注意语法
var left = [];//创建左边基准容器
var right = [];//创建右边基准容器
for (var i = 0; i < l; i += 1) {//开始遍历数组
arr[i] < numValue &#63; left.push(arr[i]) : right.push(arr[i]);//男的站左边，女的站右边。。
}
return quickSort(left).concat([numValue], quickSort(right))//递归，继续对左右数组进行操作。
}

动画效果：

这里注意 arr.splice(num,1)虽然只抽了一个数，但splice的结果也是数组，需要[0],要不然结果就会很奇葩的出现一堆array(1)的数组了。。。
splice的参考：http://www.jb51.net/w3school/js/jsref_splice.htm
Math.floor即Math对象的参考http://www.jb51.net/w3school/js/js_obj_math.htm
递归是什么：http://baike.baidu.com/view/96473.htm

以上四个算法除了快速排序，都是简单排序算法，而这四个算法在面试中考的都非常频繁~
在这里仍然要强调一点，以上的算法大量使用了循环及数组的相关知识，一定要背熟！