JavaScript：十大排序的算法思路和代碼實現

文內容包括：(雙向)冒泡排序、選擇排序、插入排序、快速排序(填坑和交換)、歸并排序、桶排序、基數排序、計數排序(優化)、堆排序、希爾排序。

先推薦一個數據結構和算法動態可視化工具，可以查看各種算法的動畫演示。下面開始正文。

冒泡排序

通過相鄰元素的比較和交換，使得每一趟循環都能找到未有序數組的最大值或最小值。

最好： O(n)，只需要冒泡一次數組就有序了。
最壞： O(n2)
平均： O(n2)

單向冒泡

function bubbleSort(nums) { for(let i=0, len=nums.length; i<len-1; i++) { // 如果一輪比較中沒有需要交換的數據，則說明數組已經有序。主要是對[5,1,2,3,4]之類的數組進行優化 let mark=true; for(let j=0; j<len-i-1; j++) { if(nums[j] > nums[j+1]) { [nums[j], nums[j+1]]=[nums[j+1], nums[j]]; mark=false; } } if(mark) return; }}

雙向冒泡

普通的冒泡排序在一趟循環中只能找出一個最大值或最小值，雙向冒泡則是多一輪循環既找出最大值也找出最小值。

function bubbleSort_twoWays(nums) { let low=0; let high=nums.length - 1; while(low < high) { let mark=true; // 找到最大值放到右邊 for(let i=low; i<high; i++) { if(nums[i] > nums[i+1]) { [nums[i], nums[i+1]]=[nums[i+1], nums[i]]; mark=false; } } high--; // 找到最小值放到左邊 for(let j=high; j>low; j--) { if(nums[j] < nums[j-1]) { [nums[j], nums[j-1]]=[nums[j-1], nums[j]]; mark=false; } } low++; if(mark) return; }}

選擇排序

和冒泡排序相似，區別在于選擇排序是將每一個元素和它后面的元素進行比較和交換。

最好： O(n2)
最壞： O(n2)
平均： O(n2)

function selectSort(nums) { for(let i=0, len=nums.length; i<len; i++) { for(let j=i+1; j<len; j++) { if(nums[i] > nums[j]) { [nums[i], nums[j]]=[nums[j], nums[i]]; } } }}

插入排序

以第一個元素作為有序數組，其后的元素通過在這個已有序的數組中找到合適的位置并插入。

最好： O(n)，原數組已經是升序的。
最壞： O(n2)
平均： O(n2)

function insertSort(nums) { for(let i=1, len=nums.length; i<len; i++) { let temp=nums[i]; let j=i; while(j >=0 && temp < nums[j-1]) { nums[j]=nums[j-1]; j--; } nums[j]=temp; }}

快速排序

選擇一個元素作為基數（通常是第一個元素），把比基數小的元素放到它左邊，比基數大的元素放到它右邊（相當于二分），再不斷遞歸基數左右兩邊的序列。

最好： O(n * logn)，所有數均勻分布在基數的兩邊，此時的遞歸就是不斷地二分左右序列。
最壞： O(n2)，所有數都分布在基數的一邊，此時劃分左右序列就相當于是插入排序。
平均： O(n * logn)

參考學習鏈接：
算法 3：最常用的排序——快速排序
三種快速排序以及快速排序的優化

快速排序之填坑

從右邊向中間推進的時候，遇到小于基數的數就賦給左邊（一開始是基數的位置），右邊保留原先的值等之后被左邊的值填上。

function quickSort(nums) { // 遞歸排序基數左右兩邊的序列 function recursive(arr, left, right) { if(left >=right) return; let index=partition(arr, left, right); recursive(arr, left, index - 1); recursive(arr, index + 1, right); return arr; } // 將小于基數的數放到基數左邊，大于基數的數放到基數右邊，并返回基數的位置 function partition(arr, left, right) { // 取第一個數為基數 let temp=arr[left]; while(left < right) { while(left < right && arr[right] >=temp) right--; arr[left]=arr[right]; while(left < right && arr[left] < temp) left++; arr[right]=arr[left]; } // 修改基數的位置 arr[left]=temp; return left; } recursive(nums, 0, nums.length-1);}

快速排序之交換

從左右兩邊向中間推進的時候，遇到不符合的數就兩邊交換值。

function quickSort1(nums) { function recursive(arr, left, right) { if(left >=right) return; let index=partition(arr, left, right); recursive(arr, left, index - 1); recursive(arr, index + 1, right); return arr; } function partition(arr, left, right) { let temp=arr[left]; let p=left + 1; let q=right; while(p <=q) { while(p <=q && arr[p] < temp) p++; while(p <=q && arr[q] > temp) q--; if(p <=q) { [arr[p], arr[q]]=[arr[q], arr[p]]; // 交換值后兩邊各向中間推進一位 p++; q--; } } // 修改基數的位置 [arr[left], arr[q]]=[arr[q], arr[left]]; return q; } recursive(nums, 0, nums.length-1);}

歸并排序

遞歸將數組分為兩個序列，有序合并這兩個序列。

最好： O(n * logn)
最壞： O(n * logn)
平均： O(n * logn)

參考學習鏈接：
圖解排序算法(四)之歸并排序

function mergeSort(nums) { // 有序合并兩個數組 function merge(l1, r1, l2, r2) { let arr=[]; let index=0; let i=l1, j=l2; while(i <=r1 && j <=r2) { arr[index++]=nums[i] < nums[j] ? nums[i++] : nums[j++]; } while(i <=r1) arr[index++]=nums[i++]; while(j <=r2) arr[index++]=nums[j++]; // 將有序合并后的數組修改回原數組 for(let t=0; t<index; t++) { nums[l1 + t]=arr[t]; } } // 遞歸將數組分為兩個序列 function recursive(left, right) { if(left >=right) return; // 比起(left+right)/2，更推薦下面這種寫法，可以避免數溢出 let mid=parseInt((right - left) / 2) + left; recursive(left, mid); recursive(mid+1, right); merge(left, mid, mid+1, right); return nums; } recursive(0, nums.length-1);}

桶排序

取 n 個桶，根據數組的最大值和最小值確認每個桶存放的數的區間，將數組元素插入到相應的桶里，最后再合并各個桶。

最好： O(n)，每個數都在分布在一個桶里，這樣就不用將數插入排序到桶里了(類似于計數排序以空間換時間)。
最壞： O(n2)，所有的數都分布在一個桶里。
平均： O(n + k)，k表示桶的個數。

參考學習鏈接：
拜托，面試別再問我桶排序了！！！

function bucketSort(nums) { // 桶的個數，只要是正數即可 let num=5; let max=Math.max(...nums); let min=Math.min(...nums); // 計算每個桶存放的數值范圍，至少為1， let range=Math.ceil((max - min) / num) || 1; // 創建二維數組，第一維表示第幾個桶，第二維表示該桶里存放的數 let arr=Array.from(Array(num)).map(()=> Array().fill(0)); nums.forEach(val=> { // 計算元素應該分布在哪個桶 let index=parseInt((val - min) / range); // 防止index越界，例如當[5,1,1,2,0,0]時index會出現5 index=index >=num ? num - 1 : index; let temp=arr[index]; // 插入排序，將元素有序插入到桶中 let j=temp.length - 1; while(j >=0 && val < temp[j]) { temp[j+1]=temp[j]; j--; } temp[j+1]=val; }) // 修改回原數組 let res=[].concat.apply([], arr); nums.forEach((val, i)=> { nums[i]=res[i]; })}

基數排序

使用十個桶 0-9，把每個數從低位到高位根據位數放到相應的桶里，以此循環最大值的位數次。但只能排列正整數，因為遇到負號和小數點無法進行比較。

最好： O(n * k)，k表示最大值的位數。
最壞： O(n * k)
平均： O(n * k)

參考學習鏈接：
算法總結系列之五: 基數排序(Radix Sort)

function radixSort(nums) { // 計算位數 function getDigits(n) { let sum=0; while(n) { sum++; n=parseInt(n / 10); } return sum; } // 第一維表示位數即0-9，第二維表示里面存放的值 let arr=Array.from(Array(10)).map(()=> Array()); let max=Math.max(...nums); let maxDigits=getDigits(max); for(let i=0, len=nums.length; i<len; i++) { // 用0把每一個數都填充成相同的位數 nums[i]=(nums[i] + '').padStart(maxDigits, 0); // 先根據個位數把每一個數放到相應的桶里 let temp=nums[i][nums[i].length-1]; arr[temp].push(nums[i]); } // 循環判斷每個位數 for(let i=maxDigits-2; i>=0; i--) { // 循環每一個桶 for(let j=0; j<=9; j++) { let temp=arr[j] let len=temp.length; // 根據當前的位數i把桶里的數放到相應的桶里 while(len--) { let str=temp[0]; temp.shift(); arr[str[i]].push(str); } } } // 修改回原數組 let res=[].concat.apply([], arr); nums.forEach((val, index)=> { nums[index]=+res[index]; }) }

計數排序

以數組元素值為鍵，出現次數為值存進一個臨時數組，最后再遍歷這個臨時數組還原回原數組。因為 JavaScript 的數組下標是以字符串形式存儲的，所以計數排序可以用來排列負數，但不可以排列小數。

最好： O(n + k)，k是最大值和最小值的差。
最壞： O(n + k)
平均： O(n + k)

function countingSort(nums) { let arr=[]; let max=Math.max(...nums); let min=Math.min(...nums); // 裝桶 for(let i=0, len=nums.length; i<len; i++) { let temp=nums[i]; arr[temp]=arr[temp] + 1 || 1; } let index=0; // 還原原數組 for(let i=min; i<=max; i++) { while(arr[i] > 0) { nums[index++]=i; arr[i]--; } }}

計數排序優化

把每一個數組元素都加上 min 的相反數，來避免特殊情況下的空間浪費，通過這種優化可以把所開的空間大小從 max+1 降低為 max-min+1， max 和 min 分別為數組中的最大值和最小值。

比如數組 [103, 102, 101, 100]，普通的計數排序需要開一個長度為 104 的數組，而且前面 100 個值都是 undefined，使用該優化方法后可以只開一個長度為 4 的數組。

function countingSort(nums) { let arr=[]; let max=Math.max(...nums); let min=Math.min(...nums); // 加上最小值的相反數來縮小數組范圍 let add=-min; for(let i=0, len=nums.length; i<len; i++) { let temp=nums[i]; temp +=add; arr[temp]=arr[temp] + 1 || 1; } let index=0; for(let i=min; i<=max; i++) { let temp=arr[i+add]; while(temp > 0) { nums[index++]=i; temp--; } }}

堆排序

根據數組建立一個堆（類似完全二叉樹），每個結點的值都大于左右結點（最大堆，通常用于升序），或小于左右結點（最小堆，通常用于降序）。對于升序排序，先構建最大堆后，交換堆頂元素（表示最大值）和堆底元素，每一次交換都能得到未有序序列的最大值。重新調整最大堆，再交換堆頂元素和堆底元素，重復 n-1 次后就能得到一個升序的數組。

最好： O(n * logn)，logn是調整最大堆所花的時間。
最壞： O(n * logn)
平均： O(n * logn)

參考學習鏈接：
常見排序算法 - 堆排序 (Heap Sort)
圖解排序算法(三)之堆排序

function heapSort(nums) { // 調整最大堆，使index的值大于左右節點 function adjustHeap(nums, index, size) { // 交換后可能會破壞堆結構，需要循環使得每一個父節點都大于左右結點 while(true) { let max=index; let left=index * 2 + 1; // 左節點 let right=index * 2 + 2; // 右節點 if(left < size && nums[max] < nums[left]) max=left; if(right < size && nums[max] < nums[right]) max=right; // 如果左右結點大于當前的結點則交換，并再循環一遍判斷交換后的左右結點位置是否破壞了堆結構（比左右結點小了） if(index !==max) { [nums[index], nums[max]]=[nums[max], nums[index]]; index=max; } else { break; } } } // 建立最大堆 function buildHeap(nums) { // 注意這里的頭節點是從0開始的，所以最后一個非葉子結點是 parseInt(nums.length/2)-1 let start=parseInt(nums.length / 2) - 1; let size=nums.length; // 從最后一個非葉子結點開始調整，直至堆頂。 for(let i=start; i>=0; i--) { adjustHeap(nums, i, size); } }
 buildHeap(nums); // 循環n-1次，每次循環后交換堆頂元素和堆底元素并重新調整堆結構 for(let i=nums.length-1; i>0; i--) { [nums[i], nums[0]]=[nums[0], nums[i]]; adjustHeap(nums, 0, i); }}

希爾排序

通過某個增量 gap，將整個序列分給若干組，從后往前進行組內成員的比較和交換，隨后逐步縮小增量至 1。希爾排序類似于插入排序，只是一開始向前移動的步數從 1 變成了 gap。

最好： O(n * logn)，步長不斷二分。
最壞： O(n * logn)
平均： O(n * logn)

參考學習鏈接：
圖解排序算法(二)之希爾排序

function shellSort(nums) { let len=nums.length; // 初始步數 let gap=parseInt(len / 2); // 逐漸縮小步數 while(gap) { // 從第gap個元素開始遍歷 for(let i=gap; i<len; i++) { // 逐步其和前面其他的組成員進行比較和交換 for(let j=i-gap; j>=0; j-=gap) { if(nums[j] > nums[j+gap]) { [nums[j], nums[j+gap]]=[nums[j+gap], nums[j]]; } else { break; } } } gap=parseInt(gap / 2); }}

擊上方“Web前端進階指南”關注我呦

跟程序員小強一起學前端

這一篇呢，我們來說說CSS3一些高級有趣的屬性，幫助我們更好的，更高效的去開發我們的頁面，不僅在效率上提高很多，而且頁面效果上更炫酷，下面一起來看看吧。

CSS3多列屬性

CSS3多列屬性有很多，我們一一來介紹一下，包括以下幾個屬性：

column-count
column-gap
column-rule-style
column-rule-width
column-rule-color
column-rule
column-span
column-width

1、CSS3創建多列

column-count屬性指定了需要分割的列數，就是說你想要讓你的文本顯示多少列，我們不需要寫很多個div，然后去限制字數，分別在每個div里調用多少字，還需要讓div浮動，麻煩滴很啊，這是用CSS3多列我們自己就可以達到這樣的需求。如圖所示：

效果如下：

這樣一來，我們就可以將文本分成3列顯示，超出的文本自動隱藏，我們在寫響應式頁面的時候就可以用到它哦！

2、CSS3 多列中列與列間的間隙

調整多列中列與列間的間隙的時候我們就可以用column-gap，它就指定了列與列間的間隙，我們再也不需要專門給div設定浮動，還要設置它們之間的margin，有了它就可以像Swiper那樣一個屬性，輕輕松松設置間距，效果如上圖那樣，分成三列，并設置間距。代碼如下：

3、CSS3 列邊框

還有更好玩的多列屬性。上面我們設置完了列與列的間距，這呢我們用column-rule-style屬性來設置列與列之間的邊框樣式，我們不再用圖片或者更多的CSS去寫，它就可以了，例如：

這樣我們就可以將文本分成3列，間距40px，列邊框的樣式為虛線，此外，我們還設定邊框的寬度（column-rule-width），顏色（column-rule-color），并且像CSS中那樣去用（column-rule）簡寫我們的多列邊框，例如：

達到的效果如下：

順便給大家說一下CSS有哪些邊框樣式，直接上圖啦：

4、指定元素跨越多少列

就是給被指定的某個元素應該跨多少列，這時候我們就要用到（column-span）這個屬性了，這個屬性有兩個值，一個是1，一個是all，這就是說如果有個文本我們把它分成3列，我們就可以指定它的標題占1列或者所有的列。如下圖：

5、指定列的寬度

我們不僅可以把文本分成幾列，還可以專門指定被分成列的寬度，這時候我們可以用column-width屬性，來指定列的寬度。例如：

CSS3行數限制

限制在一個塊元素顯示的文本的行數，我們就可以用-webkit-line-clamp，由于它是一個不規范的屬性，他沒有出現在CSS規范草案中，不過并不代表我們不能用，為了使用它達到我們想要的效果，我們得結合一些屬性，例如：

這樣一來，我們就可以讓我們的文本顯示6行，其余的用省略號代替。

此外，我們也可以顯示一行文本，多余的用省略號代替，例如：

CSS3 writing-mode 屬性

writing-mode 屬性定義了文本在水平或垂直方向上如何排版，這樣我們就可以省去大量的CSS代碼，一個屬性就可以搞定，writing-mode有5個值，分別是：

horizontal-tb：水平方向自上而下的書寫方式。即 left-right-top-bottom
vertical-rl：垂直方向自右而左的書寫方式。即 top-bottom-right-left
vertical-lr：垂直方向內內容從上到下，水平方向從左到右
sideways-rl：內容垂直方向從上到下排列
sideways-lr：內容垂直方向從下到上排列

我們可以讓元素以任何形式放置在我們的表格當中，例如下圖：

CSS3彈性盒子

這也是我們常用的知識，彈性盒子由彈性容器(Flex container)和彈性子元素(Flex item)組成。通過設置 display 屬性的值為 flex 或 inline-flex將其定義為彈性容器。容器內包含了一個或多個彈性子元素。

正常情況下，我們只需設置display:flex即可，彈性子元素元素就會在一行內顯示（彈性子元素通常在彈性盒子內一行顯示。默認情況每個容器只有一行），從左到右。

當然我們也可以修改排列方式，例如我們將body設置direction 屬性為 rtl （right-to-left），彈性子元素的排列方式也會改變，頁面布局也跟著改變，所有的子元素會靠近左側排列，并且以倒序排列。

1、flex-direction

flex-direction 屬性指定了彈性子元素在父容器中的位置。其屬性值：

row：橫向從左到右排列（左對齊），默認的排列方式。
row-reverse：反轉橫向排列（右對齊，從后往前排，最后一項排在最前面。
column：縱向排列。
column-reverse：反轉縱向排列，從后往前排，最后一項排在最上面。

例如我們用row-reverse將子元素倒序排列：

2、justify-content 屬性

內容對齊（justify-content）屬性應用在彈性容器上，把彈性項沿著彈性容器的主軸線（main axis）對齊。這樣我們就可以更好地排列我們的文本了，它呢有5個值，例如：

flex-start：彈性項目向行頭緊挨著填充。這個是默認值。第一個彈性項的main-start外邊距邊線被放置在該行的main-start邊線，而后續彈性項依次平齊擺放。
flex-end：彈性項目向行尾緊挨著填充。第一個彈性項的main-end外邊距邊線被放置在該行的main-end邊線，而后續彈性項依次平齊擺放。
center：彈性項目居中緊挨著填充。（如果剩余的自由空間是負的，則彈性項目將在兩個方向上同時溢出）。
space-between：彈性項目平均分布在該行上。如果剩余空間為負或者只有一個彈性項，則該值等同于flex-start。否則，第1個彈性項的外邊距和行的main-start邊線對齊，而最后1個彈性項的外邊距和行的main-end邊線對齊，然后剩余的彈性項分布在該行上，相鄰項目的間隔相等。
space-around：彈性項目平均分布在該行上，兩邊留有一半的間隔空間。如果剩余空間為負或者只有一個彈性項，則該值等同于center。否則，彈性項目沿該行分布，且彼此間隔相等（比如是20px），同時首尾兩邊和彈性容器之間留有一半的間隔（1/2*20px=10px）。

效果如下：

平時space-between用的最多，它會讓彈性子元素均勻的分布在彈性盒子呢，而且是響應式的排列。

CSS3多媒體查詢

CSS3多媒體查詢可以針對不同的媒體類型(包括顯示器、便攜設備、電視機，等等)設置不同的樣式規則。但是這些多媒體類型在很多設備上支持還不夠友好。目前很多針對蘋果手機，Android 手機，平板等設備都會使用到多媒體查詢。像別的媒體，例如打印機、屏幕閱讀器等的兼容性還不是很好。

使用 @media 查詢，你可以針對不同的媒體類型定義不同的樣式。

@media 可以針對不同的屏幕尺寸設置不同的樣式，特別是如果你需要設置設計響應式的頁面，@media 是非常有用的。

當你重置瀏覽器大小的過程中，頁面也會根據瀏覽器的寬度和高度重新渲染頁面。

比如說我們常用的響應式頁面，我們想在媒體寬度最大500px顯示圖片，其余媒體不顯示，我們就可以這樣寫：

總結

在使用本篇講解的CSS3屬性時，一定要注意其瀏覽器的兼容性，因為很多的CSS3屬性都不支持主流的低版本的瀏覽器，基本IE10以上、FireFox3.5以上、Chrome21.0以上、Safari4.0以上才能很好地兼容，希望小伙伴們注意。

本期的CSS3到這里就全部講解完了，也希望小伙伴們學的快樂，馬上也到了寒假過年的好日子，希望大家不要忘記學習哈！

接下來的我們會很長一段時間去學習JavaScript，如果你想學，關注我，我將帶領大家一起去學習。

打樣的核心是顯示器，ISO 12646規定了用于軟打樣顯示器的要求，主要包括基本要求、均勻性要求、觀察錐特性、反射特性等。ISO 12646：2015原文可以見https://www.doc88.com/p-14061600517057.html；國家標準《 GB/T 41598—2022 印刷技術彩色打樣用顯示器性能指標》等效采用了ISO 12646：2015。

（1）顏色均勻性評價

將屏幕分為5×5均勻的網格，以中心網格色塊在顯示器最大驅動值的測量值為參考白，計算25個網格的CIELAB值。在三種驅動水平下，即最大驅動水平（白）（8位顯示器R=G=B=255）、最大驅動水平的一半（灰）（8位顯示器R=G=B=127）、最大驅動水平的1/4（深灰）（8位顯示器R=G=B=63），如下圖所示，計算周圍24個網格和中心網格的CIEDE2000色差，要小于等于4。

(a) (b) (c)

圖1 顯示器均勻性評價的5×5網格及255、127、63三種驅動水平

（2）亮度均勻性評價

測量灰（最大驅動水平的一半，8位顯示器R=G=B=127）和白（最大驅動水平，8位顯示器R=G=B=255）的亮度（cd/m2），圖 1(a)和(b)，計算灰/白比。對于非中心區域的灰/白比Ti（i=1…24）由各非中心區域的亮度Ri（i=1…24）除以中心區域的亮度Rc，再減去1，并取絕對值，用式表示。亮度均勻性的偏差應小于10%，即Ti（i=1…24）的最大值最好小于10%。

亮度均勻性用max(Ti) (i=1, 2, …, 24)表示，最好小于0.1，也就是Ri 在0.9 Rc~1.1Rc之間。

在線咨詢

上一篇：《JSP》第05節：JSP基礎語法之JSP聲明（定義
下一篇：html獨立功能模塊增刪改查實例

您的項目需求

*請認真填寫需求信息，我們會在24小時內與您取得聯系。

整合營銷服務商