常用排序演算法

語雀入口

　　https://www.yuque.com/along-n3gko/ezt5z9

冒泡排序

• 比較相鄰的兩個元素，如果前一個比后一個大，則交換位置，
• 比較完第一輪的時候，最后一個元素是最大的元素，
• 這時候最后一個元素是最大的，所以最后一個元素就不需要參與比較大小，

 1 let arr = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999];
 2   let sortArr = (arr) => {
 3     let temp = null;
 4     for (let i = 0; i < arr.length; i++) {
 5       for (let j = i + 1; j < arr.length; j++) {
 6         if (arr[i] > arr[j]) {
 7           temp = arr[i];
 8           arr[i] = arr[j];
 9           arr[j] = temp;
10         }
11       }
12     }
13     return arr;
14   }

sort排序

• arrayObject(sortby) 默認是按照字串UniCode編碼排序

字串排序

1 let next = ['a', 'c', 'g', 'h', 'b', 'e'];
2 
3 next.sort();
4 
5 // ['a', 'b', 'c', 'e', 'g', 'h' ]

升序，sort方法接受一個函式作為引數，引數傳遞兩個引數，即回傳一個a-b小于0的值，為升序

1 let arr2 = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999];
2   let sortArr2 = (arr) => {
3     return arr.sort((a, b) => {
4       return a - b
5     })
6   }

降序，sort方法接受一個函式作為引數，引數傳遞兩個引數，即回傳一個a-b大于0的值，為降序

1 let arr3 = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999];
2   let sortArr3 = (arr) => {
3     return arr.sort((a, b) => {
4       return b - a
5     })
6   }

陣列值為物件排序方法同上

 1 let arr6 = [
 2     { 'id': '1' },
 3     { 'id': '2' },
 4     { 'id': '5' },
 5     { 'id': '100' },
 6     { 'id': '101' },
 7     { 'id': '31' },
 8     { 'id': '11' }
 9   ]
10   let sortArr6 = (arr) => {
11     return arr.sort((a, b) => {
12       return a.id - b.id
13     })
14   }

取最小值

Math中的min方法實作

1 let arr4 = [1, 5, 8, 22, 66, 55, 1, 22, 4, 88, 999];
2   let sortArr4 = (arr) => {
3     return Math.min(...arr);
4   }

排序法:對陣列進行升序或者降序排列，然后取出陣列的第一個值或者最后一個值，即可取出最小值，

假設法：假設陣列的第一個值是最小值，然后陣列的每個元素和第一個值做比較，如果小于第一個值，則把值傳遞給第一個，

1 let a = [10,2,3,4,5,6,7,8];
2 var min = a[0];
3 
4 for(let i=0; i<a.length; i++) {
5     a[i] < min ? min = a[i] : null;
6 }

取最大值

Math中的max方法實作

1 let arr4 = [1, 5, 8, 22, 66, 55, 1, 22, 4, 88, 999];
2   let sortArr4 = (arr) => {
3     return Math.max(...arr);
4 }

排序法:對陣列進行升序或者降序排列，然后取出陣列的第一個值或者最后一個值，即可取出最大值，

比較法：取第一個值與所有值作比較，大于所有值則回傳第一個值，否者回傳大于它的那個值，

1 let a = [2,10,2,3,4,5,6,7,8];
2 const getMax = function (array){
3     var max = undefined;
4     for (var i = 0; i < array.length; ++i) {
5       max = max === undefined ? array[i] : (max >= array[i] ? max : array[i]);
6     }
7     return max;
8 }

亂序

　　使用sort方法

1 let a = [1,2,3,4,5,6,7,8];
2 
3 a.sort(() => {
4     return Math.random() - 0.5
5 })

　　弊端：允許多次的時候就會發現末尾大值的概率高，開頭小值概率高，

　　原來，在Chrome v8引擎原始碼中，處理sort方法時，使用了插入排序和快速排序兩種方案，當目標陣列長度小于10時，使用插入排序；反之，使用快速排序和插入排序的混合排序，

 1 const arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]
 2 function shuffle(arr) {
 3   return arr.sort(() => (Math.random() - 0.5))
 4 }
 5 
 6 let resultArr = Array(10).fill(0)
 7 for (let i = 0; i < 10000; i++) {
 8   // sort 會改變原陣列，必須用新陣列來進行亂序
 9   let newArr = [].concat(arr)
10   const tmp = shuffle(newArr)
11   resultArr.forEach((item, index) => {
12     // 不能直接改變 item 的值, item += tmp[index], 因為 forEach 不會改變原陣列
13     resultArr[index] += tmp[index]
14   })
15 }
16 console.log(resultArr)
17 const average = resultArr.map(i => i/ 10000)
18 console.log(average)
19 
20 // => [48544, 48860, 55333, 56927, 56797, 53396, 53790, 56762, 58967, 60624]
21 // => [4.8544, 4.886, 5.5333, 5.6927, 5.6797, 5.3396, 5.379, 5.6762, 5.8967, 6.0624]

洗牌演算法

　　先從陣列末尾開始，選取最后一個元素，與陣列中隨機一個位置的元素交換位置；然后在已經排好的最后一個元素以外的位置中，隨機產生一個位置，讓該位置元素與倒數第二個元素進行交換

1 function shuffle(a) {
2     for (let i = a.length; i; i--) {
3         let j = Math.floor(Math.random() * i);
4         [a[i - 1], a[j]] = [a[j], a[i - 1]];
5     }
6     return a;
7 }

測驗下看效果

 1 const arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]
 2 function shuffle(a) {
 3     for (let i = a.length; i; i--) {
 4         let j = Math.floor(Math.random() * i);
 5         [a[i - 1], a[j]] = [a[j], a[i - 1]];
 6     }
 7     return a;
 8 }
 9 
10 let resultArr = Array(10).fill(0)
11 for (let i = 0; i < 10000; i++) {
12   // sort 會改變原陣列，必須用新陣列來進行亂序
13   let newArr = [].concat(arr)
14   const tmp = shuffle(newArr)
15   resultArr.forEach((item, index) => {
16     // 不能直接改變 item 的值, item += tmp[index], 因為 forEach 不會改變原陣列
17     resultArr[index] += tmp[index]
18   })
19 }
20 console.log(resultArr)
21 const average = resultArr.map(i => i/ 10000)
22 console.log(average)
23 
24 // => [55070, 54854, 54588, 55169, 55458, 54670, 55311, 54944, 55030, 54906]
25 // =>  [5.507, 5.4854, 5.4588, 5.5169, 5.5458, 5.467, 5.5311, 5.4944, 5.503, 5.4906]

插入排序

• 從第二位（當前元素）開始從后向前查找
• 若新元素（當前元素的前面）大于當前元素，將新元素移到下一位置
• 重復2，直到在有序區找到大于或等于新元素的位置
• 將當前元素插到上面找到的位置
• 重復2~4

 1 function insertionSort(arr){
 2     var 
 3         len = arr.length,
 4         i = 1,
 5         j,
 6         buffer;
 7 
 8     for (; i < len; i++) {
 9         buffer = arr[i];
10 
11         //在當前元素從后向前遍歷,
12         //一旦找到比當前元素大的就進行“元素加位”
13         for (j = i - 1; j >= 0 && arr[j] > buffer; j--) {
14                 arr[j+1] = arr[j];
15         }
16         //找到的位置替換為當前元素，比它大的在上面已經“加位”了
17         arr[j+1] = buffer;
18     }
19     
20     return arr;
21 }

...

標籤：JavaScript

上一篇：散串列

下一篇：JavaScript連載10-流程控制陳述句if（快速總結）