# 前言
很多同學(xué)在前端面試中剩晴,手寫代碼已經(jīng)是家常便飯萤晴。要求寫一些常見的排序算法也是常常遇到互艾,接下來(lái)將把幾種常見的算法用 JavaScript
的方法實(shí)現(xiàn)载碌。
# 快速排序
分治法的思想猜嘱,尋找中間點(diǎn),并對(duì)其左右的序列遞歸進(jìn)行排序嫁艇,直到左右都排序完成朗伶。
function quickSort(arr){
if(arr.length == 0) return arr;
let pirotIndex = Math.floor(arr.length/2),
pirot = arr.splice(pirotIndex, 1)[0],
left= [], right = [];
for(let i = 0; i < arr.length; i++){
arr[i] > pirot ? right.push(arr[i]) : left.push(arr[i]);
}
return quickSort(left).concat(pirot, quickSort(right))
}
# 插入排序
將數(shù)組分為 無(wú)序區(qū) 和 有序區(qū) 兩個(gè)區(qū),然后不斷 將無(wú)序區(qū) 的第一個(gè)元素按大小順序插入到 有序區(qū) 中去步咪,最終將所有 無(wú)序區(qū) 元素都移動(dòng)到 有序區(qū)完 成排序
function insertionSort(arr) {
var preIndex, current;
for (let i = 1; i < arr.length; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
# 冒泡排序
比較相鄰的元素论皆。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)猾漫。對(duì)每一對(duì)相鄰元素做同樣的工作点晴,從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)悯周,最后的元素應(yīng)該會(huì)是最大的數(shù)粒督。
function bubbleSort(arr){
if(arr.length==0) return arr
for(let i = 0; i < arr.length; i++){
for(let j = 0; j < arr.length-1; j++){
if(arr[j] > arr[j+1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]] //ES6解構(gòu)
}
}
}
return arr
}
# 選擇排序
第一次從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素禽翼,存放在序列的起始位置屠橄,然后再?gòu)氖S嗟奈磁判蛟刂袑ふ业阶钚族跛。ù螅┰兀缓蠓诺揭雅判虻男蛄械哪┪踩袂健R源祟愅平负澹钡饺看判虻臄?shù)據(jù)元素的個(gè)數(shù)為零。
function selectionSort(arr) {
if (arr.length == 0) return arr
let minIndex;
for (let i = 0; i < arr.length; i++) {
minIndex = i;
for (let j = i; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
}
return arr
}
# 歸并排序
把數(shù)組分半溪北,不斷遞歸排序桐绒,最后進(jìn)行已排序的數(shù)字進(jìn)行合并。
function mergeSort(arr) {
if (arr.length < 2) return arr
let middle = Math.floor(arr.length / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = []
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
while (left.length) {
result.push(left.shift())
}
while (right.length) {
result.push(right.shift())
}
return result
}