這短時(shí)間學(xué)習(xí)了各種基本排序算法军熏。我們來捋一捋這些算法度硝。
選擇和冒泡排序：
大多數(shù)人最先接觸的排序凌简，因?yàn)楹美斫馍涎祝谔幚頂?shù)據(jù)量不大的情況也能很好的應(yīng)對(duì)。
插入排序：
插入排序和選擇排序的區(qū)別就是插入排序可以提前結(jié)束雏搂。
執(zhí)行時(shí) 插入排序比選擇排序慢 因?yàn)椴煌５慕粨Q位置比較耗時(shí)藕施，可以優(yōu)化。
但是對(duì)于一個(gè)近乎有序的數(shù)組進(jìn)行排序凸郑，插入排序性能要遠(yuǎn)遠(yuǎn)優(yōu)于選擇排序
所以插入排序是很有實(shí)際意義的裳食。（例如我們?cè)诓槿罩镜臅r(shí)候，要按時(shí)間排序芙沥，因?yàn)榕紶柕膯栴}導(dǎo)致個(gè)別不是按時(shí)間的 這個(gè)時(shí)候插入排序的優(yōu)勢(shì)就能完全發(fā)揮出來了）
歸并和快速排序：
歸并算法和快速排序的算法都采用了分治算法的思想：
顧名思義诲祸。分而治之浊吏，就是將原有問題分割成同等結(jié)構(gòu)的子問題。之后將子問題逐一解決后救氯，原問題也就解決找田。
快排學(xué)習(xí)了之后我們能解決那些問題呢？
例如我們要知道一個(gè)值在數(shù)組排好序之后的位置径密。
我們只需要稍微改一下快速排序就可以很快的實(shí)現(xiàn)：
/**
* 查詢數(shù)組中排在第m位的值
* @param {*查詢的數(shù)組} arr
* @param {* 數(shù)組長(zhǎng)度} n
* @param {* 查詢的下標(biāo)+1} m //查詢數(shù)組的第多少位
*/
this.selectionOne = (arr, n, m) => {
var _this = this
__quickSort(arr, 0, n - 1, m)
function __quickSort(arr, l, r, m) {
if (l >= r) {
return
}
//基本上所有的高級(jí)排序在底層都可以采用插入排序進(jìn)行優(yōu)化
// if (r - l <= 10) {
// _this.insertionSort2(arr, l, r)
// return
// }
let p = __partition(arr, l, r)
if (p > m) {
__quickSort(arr, l, p - 1, m)
} else if (p < m) {
__quickSort(arr, p + 1, r, m)
} else {
log(arr[p])
}
}
//對(duì)arr進(jìn)行partition操作返回一個(gè)索引下標(biāo) p
//滿足 arr[l,p1]里面所有的值都小于 arr[p] , arr[p+1,r]里面所有的值都大于 arr[p]
function __partition(arr, l, r) {
let n = Math.floor(Math.random() * (r - l + 1) + l, 10)
swap(arr, l, n)
let v = arr[l]
let i = l + 1, p = r
while (true) {
while (i <= r && arr[i] < v) {
i++
}
while (p >= l + 1 && arr[p] > v) {
p--
}
if (i > p) {
break
}
swap(arr, i, p)
i++
p--
}
swap(arr, l, p)
return p
}
}
下面我們說一下數(shù)組打亂：
方法一：
[12,4,16,3].sort(function() {
return .5 - Math.random();
});
該方法打亂數(shù)組不是完全的午阵，根據(jù)網(wǎng)上資料：
chrome v8引擎 在處理 sort 方法時(shí)，使用了插入排序和快排兩種方案享扔。
當(dāng)目標(biāo)數(shù)組長(zhǎng)度小于10時(shí)底桂，使用插入排序；反之惧眠，使用快排
Math.random 的隨機(jī)數(shù)生成器和 java 一樣以當(dāng)前時(shí)間為隨機(jī)數(shù)種子
這樣在測(cè)試數(shù)據(jù)很大的時(shí)候會(huì)導(dǎo)致打亂的不是很均勻籽懦。
方法二：
稱之為洗牌算法：
this.shuffle = (arr, n) => {
for (let i = 1; i < arr.length; i++) {
const random = Math.floor(Math.random() * (i + 1));
[arr[i], arr[random]] = [arr[random], arr[i]];
}
return arr;
};
順序拿到數(shù)組中的一位，和數(shù)組中隨機(jī)一位進(jìn)行換位氛魁，保證每個(gè)位置都被打亂過暮顺。
以上都是個(gè)人理解如有不對(duì)之處還望指正交流！
