文內(nèi)容包括:(雙向)冒泡排序、選擇排序、插入排序、快速排序(填坑和交換)、歸并排序、桶排序、基數(shù)排序、計數(shù)排序(優(yōu)化)、堆排序、希爾排序。
先推薦一個數(shù)據(jù)結(jié)構(gòu)和算法動態(tài)可視化工具,可以查看各種算法的動畫演示。下面開始正文。
通過相鄰元素的比較和交換,使得每一趟循環(huán)都能找到未有序數(shù)組的最大值或最小值。
最好: O(n),只需要冒泡一次數(shù)組就有序了。
最壞: O(n2)
平均: O(n2)
單向冒泡
function bubbleSort(nums) { for(let i=0, len=nums.length; i<len-1; i++) { // 如果一輪比較中沒有需要交換的數(shù)據(jù),則說明數(shù)組已經(jīng)有序。主要是對[5,1,2,3,4]之類的數(shù)組進行優(yōu)化 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; }}
雙向冒泡
普通的冒泡排序在一趟循環(huán)中只能找出一個最大值或最小值,雙向冒泡則是多一輪循環(huán)既找出最大值也找出最小值。
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; }}
和冒泡排序相似,區(qū)別在于選擇排序是將每一個元素和它后面的元素進行比較和交換。
最好: 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]]; } } }}
以第一個元素作為有序數(shù)組,其后的元素通過在這個已有序的數(shù)組中找到合適的位置并插入。
最好: O(n),原數(shù)組已經(jīng)是升序的。
最壞: 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; }}
選擇一個元素作為基數(shù)(通常是第一個元素),把比基數(shù)小的元素放到它左邊,比基數(shù)大的元素放到它右邊(相當(dāng)于二分),再不斷遞歸基數(shù)左右兩邊的序列。
最好: O(n * logn),所有數(shù)均勻分布在基數(shù)的兩邊,此時的遞歸就是不斷地二分左右序列。
最壞: O(n2),所有數(shù)都分布在基數(shù)的一邊,此時劃分左右序列就相當(dāng)于是插入排序。
平均: O(n * logn)
參考學(xué)習(xí)鏈接:
算法 3:最常用的排序——快速排序
三種快速排序以及快速排序的優(yōu)化
快速排序之填坑
從右邊向中間推進的時候,遇到小于基數(shù)的數(shù)就賦給左邊(一開始是基數(shù)的位置),右邊保留原先的值等之后被左邊的值填上。
function quickSort(nums) { // 遞歸排序基數(shù)左右兩邊的序列 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; } // 將小于基數(shù)的數(shù)放到基數(shù)左邊,大于基數(shù)的數(shù)放到基數(shù)右邊,并返回基數(shù)的位置 function partition(arr, left, right) { // 取第一個數(shù)為基數(shù) 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]; } // 修改基數(shù)的位置 arr[left]=temp; return left; } recursive(nums, 0, nums.length-1);}
快速排序之交換
從左右兩邊向中間推進的時候,遇到不符合的數(shù)就兩邊交換值。
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--; } } // 修改基數(shù)的位置 [arr[left], arr[q]]=[arr[q], arr[left]]; return q; } recursive(nums, 0, nums.length-1);}
遞歸將數(shù)組分為兩個序列,有序合并這兩個序列。
最好: O(n * logn)
最壞: O(n * logn)
平均: O(n * logn)
參考學(xué)習(xí)鏈接:
圖解排序算法(四)之歸并排序
function mergeSort(nums) { // 有序合并兩個數(shù)組 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++]; // 將有序合并后的數(shù)組修改回原數(shù)組 for(let t=0; t<index; t++) { nums[l1 + t]=arr[t]; } } // 遞歸將數(shù)組分為兩個序列 function recursive(left, right) { if(left >=right) return; // 比起(left+right)/2,更推薦下面這種寫法,可以避免數(shù)溢出 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 個桶,根據(jù)數(shù)組的最大值和最小值確認(rèn)每個桶存放的數(shù)的區(qū)間,將數(shù)組元素插入到相應(yīng)的桶里,最后再合并各個桶。
最好: O(n),每個數(shù)都在分布在一個桶里,這樣就不用將數(shù)插入排序到桶里了(類似于計數(shù)排序以空間換時間)。
最壞: O(n2),所有的數(shù)都分布在一個桶里。
平均: O(n + k),k表示桶的個數(shù)。
參考學(xué)習(xí)鏈接:
拜托,面試別再問我桶排序了!!!
function bucketSort(nums) { // 桶的個數(shù),只要是正數(shù)即可 let num=5; let max=Math.max(...nums); let min=Math.min(...nums); // 計算每個桶存放的數(shù)值范圍,至少為1, let range=Math.ceil((max - min) / num) || 1; // 創(chuàng)建二維數(shù)組,第一維表示第幾個桶,第二維表示該桶里存放的數(shù) let arr=Array.from(Array(num)).map(()=> Array().fill(0)); nums.forEach(val=> { // 計算元素應(yīng)該分布在哪個桶 let index=parseInt((val - min) / range); // 防止index越界,例如當(dāng)[5,1,1,2,0,0]時index會出現(xiàn)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; }) // 修改回原數(shù)組 let res=[].concat.apply([], arr); nums.forEach((val, i)=> { nums[i]=res[i]; })}
使用十個桶 0-9,把每個數(shù)從低位到高位根據(jù)位數(shù)放到相應(yīng)的桶里,以此循環(huán)最大值的位數(shù)次。但只能排列正整數(shù),因為遇到負(fù)號和小數(shù)點無法進行比較。
最好: O(n * k),k表示最大值的位數(shù)。
最壞: O(n * k)
平均: O(n * k)
參考學(xué)習(xí)鏈接:
算法總結(jié)系列之五: 基數(shù)排序(Radix Sort)
function radixSort(nums) { // 計算位數(shù) function getDigits(n) { let sum=0; while(n) { sum++; n=parseInt(n / 10); } return sum; } // 第一維表示位數(shù)即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把每一個數(shù)都填充成相同的位數(shù) nums[i]=(nums[i] + '').padStart(maxDigits, 0); // 先根據(jù)個位數(shù)把每一個數(shù)放到相應(yīng)的桶里 let temp=nums[i][nums[i].length-1]; arr[temp].push(nums[i]); } // 循環(huán)判斷每個位數(shù) for(let i=maxDigits-2; i>=0; i--) { // 循環(huán)每一個桶 for(let j=0; j<=9; j++) { let temp=arr[j] let len=temp.length; // 根據(jù)當(dāng)前的位數(shù)i把桶里的數(shù)放到相應(yīng)的桶里 while(len--) { let str=temp[0]; temp.shift(); arr[str[i]].push(str); } } } // 修改回原數(shù)組 let res=[].concat.apply([], arr); nums.forEach((val, index)=> { nums[index]=+res[index]; }) }
以數(shù)組元素值為鍵,出現(xiàn)次數(shù)為值存進一個臨時數(shù)組,最后再遍歷這個臨時數(shù)組還原回原數(shù)組。因為 JavaScript 的數(shù)組下標(biāo)是以字符串形式存儲的,所以計數(shù)排序可以用來排列負(fù)數(shù),但不可以排列小數(shù)。
最好: 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; // 還原原數(shù)組 for(let i=min; i<=max; i++) { while(arr[i] > 0) { nums[index++]=i; arr[i]--; } }}
計數(shù)排序優(yōu)化
把每一個數(shù)組元素都加上 min 的相反數(shù),來避免特殊情況下的空間浪費,通過這種優(yōu)化可以把所開的空間大小從 max+1 降低為 max-min+1, max 和 min 分別為數(shù)組中的最大值和最小值。
比如數(shù)組 [103, 102, 101, 100],普通的計數(shù)排序需要開一個長度為 104 的數(shù)組,而且前面 100 個值都是 undefined,使用該優(yōu)化方法后可以只開一個長度為 4 的數(shù)組。
function countingSort(nums) { let arr=[]; let max=Math.max(...nums); let min=Math.min(...nums); // 加上最小值的相反數(shù)來縮小數(shù)組范圍 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--; } }}
根據(jù)數(shù)組建立一個堆(類似完全二叉樹),每個結(jié)點的值都大于左右結(jié)點(最大堆,通常用于升序),或小于左右結(jié)點(最小堆,通常用于降序)。對于升序排序,先構(gòu)建最大堆后,交換堆頂元素(表示最大值)和堆底元素,每一次交換都能得到未有序序列的最大值。重新調(diào)整最大堆,再交換堆頂元素和堆底元素,重復(fù) n-1 次后就能得到一個升序的數(shù)組。
最好: O(n * logn),logn是調(diào)整最大堆所花的時間。
最壞: O(n * logn)
平均: O(n * logn)
參考學(xué)習(xí)鏈接:
常見排序算法 - 堆排序 (Heap Sort)
圖解排序算法(三)之堆排序
function heapSort(nums) { // 調(diào)整最大堆,使index的值大于左右節(jié)點 function adjustHeap(nums, index, size) { // 交換后可能會破壞堆結(jié)構(gòu),需要循環(huán)使得每一個父節(jié)點都大于左右結(jié)點 while(true) { let max=index; let left=index * 2 + 1; // 左節(jié)點 let right=index * 2 + 2; // 右節(jié)點 if(left < size && nums[max] < nums[left]) max=left; if(right < size && nums[max] < nums[right]) max=right; // 如果左右結(jié)點大于當(dāng)前的結(jié)點則交換,并再循環(huán)一遍判斷交換后的左右結(jié)點位置是否破壞了堆結(jié)構(gòu)(比左右結(jié)點小了) if(index !==max) { [nums[index], nums[max]]=[nums[max], nums[index]]; index=max; } else { break; } } } // 建立最大堆 function buildHeap(nums) { // 注意這里的頭節(jié)點是從0開始的,所以最后一個非葉子結(jié)點是 parseInt(nums.length/2)-1 let start=parseInt(nums.length / 2) - 1; let size=nums.length; // 從最后一個非葉子結(jié)點開始調(diào)整,直至堆頂。 for(let i=start; i>=0; i--) { adjustHeap(nums, i, size); } } buildHeap(nums); // 循環(huán)n-1次,每次循環(huán)后交換堆頂元素和堆底元素并重新調(diào)整堆結(jié)構(gòu) for(let i=nums.length-1; i>0; i--) { [nums[i], nums[0]]=[nums[0], nums[i]]; adjustHeap(nums, 0, i); }}
通過某個增量 gap,將整個序列分給若干組,從后往前進行組內(nèi)成員的比較和交換,隨后逐步縮小增量至 1。希爾排序類似于插入排序,只是一開始向前移動的步數(shù)從 1 變成了 gap。
最好: O(n * logn),步長不斷二分。
最壞: O(n * logn)
平均: O(n * logn)
參考學(xué)習(xí)鏈接:
圖解排序算法(二)之希爾排序
function shellSort(nums) { let len=nums.length; // 初始步數(shù) let gap=parseInt(len / 2); // 逐漸縮小步數(shù) 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前端進階指南”關(guān)注我呦
跟程序員小強一起學(xué)前端
這一篇呢,我們來說說CSS3一些高級有趣的屬性,幫助我們更好的,更高效的去開發(fā)我們的頁面,不僅在效率上提高很多,而且頁面效果上更炫酷,下面一起來看看吧。
CSS3多列屬性有很多,我們一一來介紹一下,包括以下幾個屬性:
1、CSS3創(chuàng)建多列
column-count屬性指定了需要分割的列數(shù),就是說你想要讓你的文本顯示多少列,我們不需要寫很多個div,然后去限制字?jǐn)?shù),分別在每個div里調(diào)用多少字,還需要讓div浮動,麻煩滴很啊,這是用CSS3多列我們自己就可以達(dá)到這樣的需求。如圖所示:
效果如下:
這樣一來,我們就可以將文本分成3列顯示,超出的文本自動隱藏,我們在寫響應(yīng)式頁面的時候就可以用到它哦!
2、CSS3 多列中列與列間的間隙
調(diào)整多列中列與列間的間隙的時候我們就可以用column-gap,它就指定了列與列間的間隙,我們再也不需要專門給div設(shè)定浮動,還要設(shè)置它們之間的margin,有了它就可以像Swiper那樣一個屬性,輕輕松松設(shè)置間距,效果如上圖那樣,分成三列,并設(shè)置間距。代碼如下:
3、CSS3 列邊框
還有更好玩的多列屬性。上面我們設(shè)置完了列與列的間距,這呢我們用column-rule-style屬性來設(shè)置列與列之間的邊框樣式,我們不再用圖片或者更多的CSS去寫,它就可以了,例如:
這樣我們就可以將文本分成3列,間距40px,列邊框的樣式為虛線,此外,我們還設(shè)定邊框的寬度(column-rule-width),顏色(column-rule-color),并且像CSS中那樣去用(column-rule)簡寫我們的多列邊框,例如:
達(dá)到的效果如下:
順便給大家說一下CSS有哪些邊框樣式,直接上圖啦:
4、指定元素跨越多少列
就是給被指定的某個元素應(yīng)該跨多少列,這時候我們就要用到(column-span)這個屬性了,這個屬性有兩個值,一個是1,一個是all,這就是說如果有個文本我們把它分成3列,我們就可以指定它的標(biāo)題占1列或者所有的列。如下圖:
5、指定列的寬度
我們不僅可以把文本分成幾列,還可以專門指定被分成列的寬度,這時候我們可以用column-width屬性,來指定列的寬度。例如:
限制在一個塊元素顯示的文本的行數(shù),我們就可以用-webkit-line-clamp,由于它是一個不規(guī)范的屬性,他沒有出現(xiàn)在CSS規(guī)范草案中,不過并不代表我們不能用,為了使用它達(dá)到我們想要的效果,我們得結(jié)合一些屬性,例如:
這樣一來,我們就可以讓我們的文本顯示6行,其余的用省略號代替。
此外,我們也可以顯示一行文本,多余的用省略號代替,例如:
writing-mode 屬性定義了文本在水平或垂直方向上如何排版,這樣我們就可以省去大量的CSS代碼,一個屬性就可以搞定,writing-mode有5個值,分別是:
我們可以讓元素以任何形式放置在我們的表格當(dāng)中,例如下圖:
這也是我們常用的知識,彈性盒子由彈性容器(Flex container)和彈性子元素(Flex item)組成。通過設(shè)置 display 屬性的值為 flex 或 inline-flex將其定義為彈性容器。容器內(nèi)包含了一個或多個彈性子元素。
正常情況下,我們只需設(shè)置display:flex即可,彈性子元素元素就會在一行內(nèi)顯示(彈性子元素通常在彈性盒子內(nèi)一行顯示。默認(rèn)情況每個容器只有一行),從左到右。
當(dāng)然我們也可以修改排列方式,例如我們將body設(shè)置direction 屬性為 rtl (right-to-left),彈性子元素的排列方式也會改變,頁面布局也跟著改變,所有的子元素會靠近左側(cè)排列,并且以倒序排列。
1、flex-direction
flex-direction 屬性指定了彈性子元素在父容器中的位置。其屬性值:
例如我們用row-reverse將子元素倒序排列:
2、justify-content 屬性
內(nèi)容對齊(justify-content)屬性應(yīng)用在彈性容器上,把彈性項沿著彈性容器的主軸線(main axis)對齊。這樣我們就可以更好地排列我們的文本了,它呢有5個值,例如:
效果如下:
平時space-between用的最多,它會讓彈性子元素均勻的分布在彈性盒子呢,而且是響應(yīng)式的排列。
CSS3多媒體查詢可以針對不同的媒體類型(包括顯示器、便攜設(shè)備、電視機,等等)設(shè)置不同的樣式規(guī)則。但是這些多媒體類型在很多設(shè)備上支持還不夠友好。目前很多針對蘋果手機,Android 手機,平板等設(shè)備都會使用到多媒體查詢。像別的媒體,例如打印機、屏幕閱讀器等的兼容性還不是很好。
使用 @media 查詢,你可以針對不同的媒體類型定義不同的樣式。
@media 可以針對不同的屏幕尺寸設(shè)置不同的樣式,特別是如果你需要設(shè)置設(shè)計響應(yīng)式的頁面,@media 是非常有用的。
當(dāng)你重置瀏覽器大小的過程中,頁面也會根據(jù)瀏覽器的寬度和高度重新渲染頁面。
比如說我們常用的響應(yīng)式頁面,我們想在媒體寬度最大500px顯示圖片,其余媒體不顯示,我們就可以這樣寫:
在使用本篇講解的CSS3屬性時,一定要注意其瀏覽器的兼容性,因為很多的CSS3屬性都不支持主流的低版本的瀏覽器,基本IE10以上、FireFox3.5以上、Chrome21.0以上、Safari4.0以上才能很好地兼容,希望小伙伴們注意。
本期的CSS3到這里就全部講解完了,也希望小伙伴們學(xué)的快樂,馬上也到了寒假過年的好日子,希望大家不要忘記學(xué)習(xí)哈!
接下來的我們會很長一段時間去學(xué)習(xí)JavaScript,如果你想學(xué),關(guān)注我,我將帶領(lǐng)大家一起去學(xué)習(xí)。
打樣的核心是顯示器,ISO 12646規(guī)定了用于軟打樣顯示器的要求,主要包括基本要求、均勻性要求、觀察錐特性、反射特性等。ISO 12646:2015原文可以見https://www.doc88.com/p-14061600517057.html;國家標(biāo)準(zhǔn)《 GB/T 41598—2022 印刷技術(shù) 彩色打樣用顯示器 性能指標(biāo)》等效采用了ISO 12646:2015。
(1)顏色均勻性評價
將屏幕分為5×5均勻的網(wǎng)格,以中心網(wǎng)格色塊在顯示器最大驅(qū)動值的測量值為參考白,計算25個網(wǎng)格的CIELAB值。在三種驅(qū)動水平下,即最大驅(qū)動水平(白)(8位顯示器R=G=B=255)、最大驅(qū)動水平的一半(灰)(8位顯示器R=G=B=127)、最大驅(qū)動水平的1/4(深灰)(8位顯示器R=G=B=63),如下圖所示,計算周圍24個網(wǎng)格和中心網(wǎng)格的CIEDE2000色差 ,要小于等于4。
(a) (b) (c)
圖1 顯示器均勻性評價的5×5網(wǎng)格及255、127、63三種驅(qū)動水平
(2)亮度均勻性評價
測量灰(最大驅(qū)動水平的一半,8位顯示器R=G=B=127)和白(最大驅(qū)動水平,8位顯示器R=G=B=255)的亮度(cd/m2),圖 1(a)和(b),計算灰/白比。對于非中心區(qū)域的灰/白比Ti(i=1…24)由各非中心區(qū)域的亮度Ri(i=1…24)除以中心區(qū)域的亮度Rc,再減去1,并取絕對值,用式表示。亮度均勻性的偏差應(yīng)小于10%,即Ti(i=1…24)的最大值最好小于10%。
亮度均勻性用max(Ti) (i=1, 2, …, 24)表示,最好小于0.1,也就是Ri 在0.9 Rc~1.1Rc之間。
*請認(rèn)真填寫需求信息,我們會在24小時內(nèi)與您取得聯(lián)系。