Pelaksanaan Javascript dan penjelasan algoritma pengisihan (nota 99js)

Isih gelembung

Prinsip menggelegak adalah untuk "mengapungkan" unsur terbesar atau unsur terkecil

Isih sisipan, isihan pilihan, isihan pantas, isihan gelembung adalah semua jenis perbandingan

Pemikiran

Bandingkan dua nombor bersebelahan dalam urutan, meletakkan perpuluhan di hadapan dan nombor besar di belakang.

langkah1: Bandingkan nombor pertama dan kedua, letakkan perpuluhan di hadapan dan nombor besar di belakang. Untuk membandingkan nombor kedua dan nombor ketiga, letakkan perpuluhan di hadapan dan nombor besar di belakang, dan teruskan seperti ini sehingga membandingkan dua nombor terakhir, letakkan perpuluhan di hadapan dan nombor besar di belakang.
step2: Dalam laluan kedua: masih memulakan perbandingan dari pasangan nombor pertama (kerana mungkin disebabkan pertukaran nombor kedua dan nombor ketiga bahawa nombor pertama tidak lagi lebih kecil daripada nombor kedua), letakkan perpuluhan dahulu, Selepas nombor besar diletakkan, perbandingan diteruskan sehingga nombor kedua-ke-terakhir (kedudukan pertama-ke-terakhir sudah menjadi yang terbesar Pada penghujung hantaran kedua, nombor maksimum baharu diperolehi). pada kedudukan kedua hingga terakhir (sebenarnya, dalam keseluruhan urutan adalah nombor kedua terbesar).
Teruskan seperti ini dan ulangi proses di atas sehingga pengisihan akhirnya selesai.
Oleh kerana dalam proses pengisihan, nombor kecil sentiasa diletakkan ke hadapan dan nombor besar diletakkan ke belakang, yang bersamaan dengan buih yang meningkat, maka ia dipanggil pengisihan gelembung.
Kesan animasi isihan buih

Pelaksanaan: Kod ini agak mudah dan merupakan kod paling asas dan asas dalam algoritma. . .
Tiga perkara yang perlu diperhatikan

1. Kaedah pertukaran kelas boleh diselesaikan dengan menggunakan a=[b,b=a][0] dalam JavaScript, yang merupakan kaedah yang sangat bijak,
Gantikan

Salin kod Kod adalah seperti berikut:

var,a,b,temp

suhu = a;

a=b;

b = suhu

Kaedah pertukaran ini
2. Perhatikan cache pembolehubah gelung Array.length
dicache di sini. 3. Beri perhatian kepada gelung terbenam, yang membandingkan daripada nombor pertama kepada nombor ke-n daripada yang terakhir, dan n ialah bilangan langkah untuk perbandingan

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);

Salin selepas log masuk

Kesan animasi

Isih Sisipan
Ia sangat mudah, hanya langkah untuk kami melukis dan memasukkan kad!
Idea:

1 Mula-mula, katakan kita melukis kad, dan semua kad yang ada di tangan kita ditetapkan kepada kosong = [] dan lukis tolak(arr[0])
2 Keluarkan kad seterusnya, tetapkannya kepada a dan imbas semua kad kami kosong (sudah diisih) dari belakang ke hadapan
3. Jika kad kosong[empty.length-n] (diisih) di tangan anda lebih besar daripada elemen baharu, alihkan kad ke kedudukan seterusnya (buat ruang) kosong[empty.length-n]= kosong[kosong. panjang- n 1]
4 Ulang langkah 3 sehingga anda mendapati kad diisih kosong[empty.length-n] kurang daripada atau sama dengan a
5 Masukkan a ke dalam kedudukan kosong[empty.length-n]=a
6Ulang langkah 2
Walau bagaimanapun, ia masih agak sukar untuk melaksanakan kod javascript Kod adalah seperti berikut:

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
}

Salin selepas log masuk

Titik pengetahuan yang lebih penting di sini ialah simbol &&, yang bermaksud "dan", iaitu syarat di kedua-dua belah pihak mesti dipenuhi agar ungkapan itu benar.
Simbol && juga boleh menggantikan jika, contohnya jika(a){fun()} sama dengan a&&b
Satu lagi perkara yang sangat penting
Andaikan tatasusunan ialah arr, maka "item terakhir"nya ialah arr[arr.length-1].

Isih animasi

Isih pilihan
Ia juga merupakan algoritma pengisihan yang mudah.

Perkara:

Cari elemen terkecil - buang ke dalam tatasusunan - kemudian cari elemen terkecil seterusnya - buang ke dalam tatasusunan, dan seterusnya.
Mula-mula, cari elemen terkecil dalam tatasusunan yang tidak diisih Kaedah mencari boleh melalui pertimbangan dan penugasan berterusan, iaitu: dengan mengandaikan elemen pertama tatasusunan, tatasusunan[0], ialah elemen terkecil, kemudian nombor siri bagi. "elemen terkecil" dalam tatasusunan ialah 0
Kemudian melintasi tatasusunan Jika elemen kedua tatasusunan lebih kecil daripadanya, ini bermakna elemen kedua ialah elemen terkecil, dan kemas kini "0" kepada "1".
Selepas traversal selesai, kita tahu bahawa subskrip elemen minimum siri ini ialah "n" terus keluarkan dan simpannya pada kedudukan permulaan urutan yang diisih (array[n])
Kemudian, teruskan mencari elemen terkecil daripada baki elemen yang tidak diisih, dan kemudian meletakkannya di penghujung urutan yang diisih. Ambil perhatian bahawa subskrip yang dilalui pada masa ini bermula dari 1. Kerana kami telah memilih elemen minimum.
Dan seterusnya sehingga semua elemen disusun.

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;
}

Salin selepas log masuk

这里仍然注意的是交换的写法 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))//递归，继续对左右数组进行操作。
}

Salin selepas log masuk

动画效果：

这里注意 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

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