前言
排序是數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容,并不限于語(yǔ)言主要在于思想;大學(xué)曾經(jīng)用C語(yǔ)言研究過(guò)一段時(shí)間的排序?qū)崿F(xiàn), 這段時(shí)間有空用JS再將排序知識(shí)點(diǎn)熟悉一遍。
下面話不多說(shuō)了,來(lái)一起看看詳細(xì)的介紹吧
一、代碼匯總(一)
1、冒泡排序
2、改進(jìn)版冒泡排序
3、選擇排序
4、直接插入排序
5、二分插入排序
/* * @Author: laifeipeng * @Date: 2019-02-20 10:00:36 * @Last Modified by: laifeipeng * @Last Modified time: 2019-02-21 11:57:58 */ /********* 1、冒泡排序 **********/ // 很常見(jiàn)很容易理解的排序算法, 排序思路:遍歷數(shù)組,每次遍歷就將最大(或最?。┲低浦磷钋啊T酵蟊闅v查詢次數(shù)越少 const bubbleSort = arr => { const list = arr.slice(); //保證函數(shù)為純函數(shù) const len = list.length; for (let i = 0; i < len; i++) { for (let j = len - 1; j > i; j--) { if (list[j] < list[j - 1]) { [list[j - 1], list[j]] = [list[j], list[j - 1]]; } } } return list; } /********* 2、改進(jìn)版冒泡排序 **********/ // 對(duì)上述冒泡排序的一種優(yōu)化, 優(yōu)化思路:當(dāng)一次遍歷前后數(shù)組不產(chǎn)生變化時(shí),說(shuō)明該數(shù)組已經(jīng)有序,結(jié)束排序。 const bubbleSort2 = arr => { const list = arr.slice(); //保證函數(shù)為純函數(shù) const len = list.length; for (let i = 0; i < len; i++) { let exchange = false; for (let j = len - 1; j > i; j--) { if (list[j] < list[j - 1]) { [list[j - 1], list[j]] = [list[j], list[j - 1]]; exchange = true; } } if (!exchange) return list } return list; } /********* 3、選擇排序 **********/ // 在無(wú)序區(qū)中選出最小的元素,然后將它和無(wú)序區(qū)的第一個(gè)元素交換位置。 const selectionSort = arr => { const list = arr.slice(); //保證函數(shù)為純函數(shù) const len = list.length; for (let i = 0; i < len; i++) { let k = i for (let j = len - 1; j > i; j--) { if (list[j] < list[k]) k = j; } if (k !== i) { [list[k], list[i]] = [list[i], list[k]]; } } return list; } /********* 4、直接插入排序 **********/ // 每次選擇無(wú)序區(qū)第一個(gè)元素插入到有序區(qū),并排序 const insertSort = arr => { const list = arr.slice(); //保證函數(shù)為純函數(shù) const len = list.length; for (let i = 1; i < len; i++) { const tmp = list[i]; let j = i - 1; while (j >= 0 && tmp < list[j]) { list[j + 1] = list[j]; j--; } list[j + 1] = tmp; } return list; } /********* 5、二分插入排序 **********/ // 插入排序的一種優(yōu)化實(shí)現(xiàn), 通過(guò)二分法減少遍歷時(shí)間(以前是從某邊開(kāi)始依次比較,現(xiàn)在從中間開(kāi)始比較,減少比較次數(shù)) // 注意,數(shù)組很大才能提現(xiàn)二分插入的優(yōu)勢(shì) const insertSort2 = arr => { const list = arr.slice(); //保證函數(shù)為純函數(shù) const len = list.length; for (let i = 1; i < len; i++) { const tmp = list[i]; let low = 0; let high = i - 1; let j = i - 1; while (low <= high) { const mid = ~~((low + high) / 2); if (tmp < list[mid]) { high = mid - 1; } else { low = mid + 1; } } while (j > high) { list[j + 1] = list[j]; j--; } list[j + 1] = tmp; } return list; }
2、代碼匯總(二)
6、快速排序
7、原地算法快速排序
8、希爾排序
堆排序、歸并排序(js實(shí)現(xiàn)無(wú)優(yōu)勢(shì),不作實(shí)現(xiàn))
/********* 6、快速排序 **********/ const quickSort1 = arr => { const list = arr.slice(); //為了保證這個(gè)函數(shù)是純函數(shù),拷貝一次數(shù)組 if (list.length <= 1) return list; const pivot = list.splice(0, 1)[0]; //選第一個(gè)作為基數(shù),并把基數(shù)從數(shù)組里面刪除 const left = []; const right = []; for (let i = 0, len = list.length; i < len; i++) { //從0開(kāi)始 if (list[i] < pivot) { left.push(list[i]); } else { right.push(list[i]); } } return [...quickSort(left), pivot, ...quickSort(right)]; } // 上面const pivot = list.splice(0, 1)[0]; 如果想直接改為list[0],那么后面循環(huán)的時(shí)候要從i=1開(kāi)始 const quickSort2 = arr => { const list = arr.slice(); //為了保證這個(gè)函數(shù)是純函數(shù),拷貝一次數(shù)組 if (list.length <= 1) return list; const pivot = list[0]; //選第一個(gè)作為基數(shù) const left = []; const right = []; for (let i = 1, len = list.length; i < len; i++) { //從1開(kāi)始 if (list[i] < pivot) { left.push(list[i]); } else { right.push(list[i]); } } return [...quickSort(left), pivot, ...quickSort(right)]; } /********* 7、原地算法快速排序 **********/ const quickSort = arr => { const list = arr.slice() // 為了保證這個(gè)函數(shù)是純函數(shù)拷貝一次數(shù)組 const sort = (arr, left = 0, right = arr.length - 1) => { if (left >= right) {//如果左邊的索引大于等于右邊的索引說(shuō)明整理完畢 return; } let i = left; let j = right; const baseVal = arr[j]; // 取無(wú)序數(shù)組最后一個(gè)數(shù)為基準(zhǔn)值 while (i < j) { //把所有比基準(zhǔn)值小的數(shù)放在左邊大的數(shù)放在右邊 while (i < j && arr[i] <= baseVal) { //找到一個(gè)比基準(zhǔn)值大的數(shù)交換 i++; } arr[j] = arr[i]; // 將較大的值放在右邊如果沒(méi)有比基準(zhǔn)值大的數(shù)就是將自己賦值給自己(i 等于 j) while (j > i && arr[j] >= baseVal) { //找到一個(gè)比基準(zhǔn)值小的數(shù)交換 j--; } arr[i] = arr[j]; // 將較小的值放在左邊如果沒(méi)有找到比基準(zhǔn)值小的數(shù)就是將自己賦值給自己(i 等于 j) } arr[j] = baseVal; // 將基準(zhǔn)值放至中央位置完成一次循環(huán)(這時(shí)候 j 等于 i ) sort(arr, left, j - 1); // 將左邊的無(wú)序數(shù)組重復(fù)上面的操作 sort(arr, j + 1, right); // 將右邊的無(wú)序數(shù)組重復(fù)上面的操作 } sort(list); return list; } /********* 8、希爾排序 **********/ // 排序思路:先將整個(gè)待排序記錄序列分割成若干個(gè)子序列,在序列內(nèi)分別進(jìn)行直接插入排序,待整個(gè)序列基本有序時(shí),再對(duì)全體記錄進(jìn)行一次直接插入排序。 const shellSort = arr => { const list = arr.slice(); //保證函數(shù)為純函數(shù) const len = list.length; let gap = ~~(len / 2); while (gap > 0) { for (let i = gap; i < len; i++) { const tmp = list[i]; let j = i - gap; while (j >= 0 && tmp < list[j]) { list[j + gap] = list[j]; j = j - gap; } list[j + gap] = tmp; } gap = ~~(gap / 2); } return list; }
3、效果圖
4、解答
1、如何在控制臺(tái)打印出上面圖片中的彩色效果,eg:
const logStep = (i, leftArr, rightArr) => console.log(`%c 第${i}趟排序:%c ${arrStr(leftArr)} %c${arrStr(rightArr)} `, 'color:green', 'color:red', 'color:blue');
2、交換數(shù)組2元素:
// 交換下標(biāo)為i,k的數(shù)組元素 [list[k], list[i]] = [list[i], list[k]];
3、所有源碼github地址:
https://github.com/laifeipeng/utils/blob/master/sort/sort.js
4、彩色打印效果的github地址:
https://github.com/laifeipeng/utils/blob/master/sort/test.js
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,如果有疑問(wèn)大家可以留言交流,謝謝大家對(duì)億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。