冒泡排序
先說(shuō)冒泡，這個(gè)原理最簡(jiǎn)單锁蠕，其實(shí)一趟冒泡要做的事情就是“把最重的泡泡沉到底下去”夷野，也就是一趟排序要找出最大的數(shù)，那怎么實(shí)現(xiàn)呢荣倾？用當(dāng)前數(shù)字和下一個(gè)數(shù)字做比較悯搔，如果當(dāng)前>下一個(gè)，進(jìn)行值交換舌仍，自然就可以通過(guò)一次循環(huán)找到最大的數(shù)妒貌。
那么我們需要控制的就是循環(huán)次數(shù)，這個(gè)當(dāng)然是用數(shù)組長(zhǎng)度來(lái)控制铸豁，一趟冒泡后灌曙，循環(huán)次數(shù)減一，看下面一段代碼：
function bubbleSort(arr) {
const end = arr.length - 1;
for (let i = end; i >= 0; i--) {
let temp = 0;
for (let k = 0; k < i; k++) {
if (arr[k] > arr[k + 1]) {
arr[k] = arr[k] + arr[k + 1] - (arr[k + 1] = arr[k]);
temp = 1;
}
}
if (temp == 0) {
break;
}
}
return arr;
}
我們可以看到节芥，上面代碼片段中設(shè)置了temp在刺，它是用來(lái)做什么的呢？用于標(biāo)記一次循環(huán)時(shí)是否發(fā)生了交換头镊。也就是說(shuō)蚣驼，如果在一趟循環(huán)結(jié)束后，沒(méi)有發(fā)生任何交換拧晕，也就是說(shuō)現(xiàn)在已經(jīng)是升序了隙姿，不需要再排了，可以結(jié)束了厂捞，這樣就有效的降低了時(shí)間復(fù)雜度输玷。
快速排序
快排的思想想必大家也都知道队丝，在一次排序后，數(shù)字a的左邊都是比它小的欲鹏，右邊都是比它大的机久。然后對(duì)左邊和右邊的數(shù)字做同樣的操作。比如我們先選擇第一個(gè)數(shù)a赔嚎，然后對(duì)數(shù)組進(jìn)行循環(huán)膘盖，遇到比a大的就不管，遇到比a小的就和上一個(gè)比a大的數(shù)進(jìn)行交換尤误，數(shù)組循環(huán)完畢后侠畔，將a與當(dāng)前正在比對(duì)的值進(jìn)行交換，就可以實(shí)現(xiàn)“左邊<a<右邊”损晤，然后對(duì)左邊右邊的數(shù)據(jù)遞歸排序软棺，具體代碼如下：
function quickSort(arr, start, end) {
let m = start;
if (start >= end) {
return;
}
for (let i = start + 1; i <= end; i++) {
if (arr[i] < arr[start]) {
m++;
arr[i] = arr[i] + arr[m] - (arr[m] = arr[i]);
}
}
arr[start] = arr[start] + arr[m] - (arr[m] = arr[start]);
quickSort(arr, start, m - 1);
quickSort(arr, m + 1, end);
return arr;
}
