【W(wǎng)eb前端基礎(chǔ)知識(shí)】冒泡排序和選擇排序

冒泡排序和數(shù)組排序是比較常見的數(shù)組排序算法

1.冒泡排序算法：

冒泡排序法是最基本的排序法之一，冒泡排序法的核心思想就是通過循環(huán)遍歷元素，每次比較的是相鄰兩項(xiàng)的數(shù)，并根據(jù)其比較大小的結(jié)果調(diào)整這兩項(xiàng)位置，一次循環(huán)之后可以得到當(dāng)前循環(huán)的較大值。經(jīng)過一輪循環(huán)并不能對(duì)該數(shù)組排序完成，所以我們的數(shù)組有多長就要有多少次循環(huán)，要在外進(jìn)行嵌套一次for循環(huán)，但這個(gè)外循環(huán)只是用來控制比較次數(shù)的，沒有參與實(shí)際的比較。

冒泡排序就是讓大數(shù)上浮，小數(shù)下沉，形式就像深海里的泡泡，也因此稱之為是冒泡排序。

例如我們有如下數(shù)組，使用冒泡排序算法的代碼為：

1. var arr = [10,5,3,7,9,4,2,8,6]; 
2.  
3.         // 外循環(huán)只是控制循環(huán)的次數(shù)，沒有參與實(shí)際意義上的比較 
4.         for(var i = 0; i<arr.length; i++){ 
5.             // 每次比較相鄰的兩項(xiàng) 一輪循環(huán) 
6.             for(var j = 0; j<arr.length; j++){ 
7.                 // 作比較 
8.                 if(arr[j] > arr[j+1]){ 
9.                     // 交換位置 
10.                     var temp = arr[j]; 
11.                     arr[j] = arr[j+1]; 
12.                     arr[j+1] = temp; 
13.                 } 
14.             } 
15.         } 

打印結(jié)果為：console.log(arr);//[2, 3, 4, 5, 6, 7, 8, 9, 10]

冒泡排序的整體代碼已經(jīng)實(shí)現(xiàn)，實(shí)際上我們可以對(duì)其做一些優(yōu)化，在內(nèi)循環(huán)的比較時(shí)，每一輪循環(huán)結(jié)束之后，我們都會(huì)得到一個(gè)較大的值，放在最后邊，那么在下次循環(huán)進(jìn)行比較時(shí)已經(jīng)沒有和后面的值作比較的意義了，因?yàn)橐脖炔贿^，也不會(huì)進(jìn)行交換位置。因此可以在內(nèi)循環(huán)的結(jié)束條件上進(jìn)行一個(gè)優(yōu)化，讓j<arr.length-i；

1. // 外循環(huán)只是控制循環(huán)的次數(shù)，沒有參與實(shí)際意義上的比較 
2.         for(var i = 0; i<arr.length; i++){ 
3.             // 每次比較相鄰的兩項(xiàng) 一輪循環(huán) 
4.             for(var j = 0; j<arr.length-i; j++){ 
5.                 // 作比較（升序排列） 
6.                 if(arr[j] > arr[j+1]){ 
7.                     // 交換位置 
8.                     var temp = arr[j]; 
9.                     arr[j] = arr[j+1]; 
10.                     arr[j+1] = temp; 
11.                 } 
12.             } 
13.             // 一輪循環(huán)結(jié)束后，得到本輪循環(huán)的最大值，放在最后 
14. } 

2. 選擇排序的思想是選擇第一項(xiàng)，后后面的所有項(xiàng)作比較，比后面的一項(xiàng)大，交換位置，之后選擇第二項(xiàng)，后后面的所有項(xiàng)作比較，比后面的一項(xiàng)大(升序排列)，交換位置...，以此類推。

也就是從第一項(xiàng)開始，選擇該項(xiàng)和后面的所有項(xiàng)進(jìn)行比較，后面的所有項(xiàng)也需要依次循環(huán)，所以在原本的for循環(huán)中需要在嵌套一個(gè)for循環(huán)，在內(nèi)循環(huán)中我們的初始條件為被選中作為比較元素的后一位，即i+1;

例如我們有如下數(shù)組，使用選擇排序算法的代碼為：

1. var arr = [10,5,3,7,9,4,2,8,6]; 
2.         // 外循環(huán)控制作為比較的項(xiàng) 
3.         for(var i = 0; i<arr.length; i++){ 
4.             // 內(nèi)循環(huán)依次和后面的項(xiàng)作比較 
5.             for(var j = i+1; j<arr.length; j++){ 
6.                 // 作比較（升序排列） 
7.                 if(arr[i] > arr[j]){ 
8.                     // 交換位置 
9.                     var temp = arr[i]; 
10.                     arr[i] = arr[j]; 
11.                     arr[j] = temp; 
12.                 } 
13.             } 
14.         } 

打印結(jié)果為： console.log(arr);//[2, 3, 4, 5, 6, 7, 8, 9, 10