好程序員web前端培訓分享JavaScript學習筆數組的排序

　　 好程序員web 前端培訓分享 JavaScript 學習筆數組的排序 ， 排序，就是把一個亂序的數組，通過我們的處理，讓他變成一個有序的數組 ， 今天我們講解兩種方式來排序一個數組  冒泡排序   和   選擇排序

冒泡排序

·  先遍歷數組，讓挨著的兩個進行比較，如果前一個比后一個大，那么就把兩個換個位置

·  數組遍歷一遍以后，那么最后一個數字就是最大的那個了

·  然后進行第二遍的遍歷，還是按照之前的規則，第二大的數字就會跑到倒數第二的位置

·  以此類推，最后就會按照順序把數組排好了

1、我們先來準備一個亂序的數組

var   arr   =   [ 3 ,   1 ,   5 ,   6 ,   4 ,   9 ,   7 ,   2 ,   8 ]

·  接下來我們就會用代碼讓數組排序

2、先不著急循環，先來看數組里面內容換個位置

// 假定我現在要讓數組中的第 0 項和第 1 項換個位置// 需要借助第三個變量 var   tmp   =   arr[ 0 ]arr[ 0 ]   =   arr[ 1 ]arr[ 1 ]   =   tmp

3、第一次遍歷數組，把最大的放到最后面去

for   ( var   i   =   0 ;   i   <   arr.length;   i ++ )   {

   // 判斷，如果數組中的當前一個比后一個大，那么兩個交換一下位置    if   (arr[i]   >   arr[i   +   1 ])   {

     var   tmp   =   arr[i]

     arr[i]   =   arr[i   +   1 ]

     arr[i   +   1 ]   =   tmp

   }}

// 遍歷完畢以后，數組就會變成 [3, 1, 5, 6, 4, 7, 2, 8, 9]

·  第一次結束以后，數組中的最后一個，就會是最大的那個數字

·  然后我們把上面的這段代碼執行多次。數組有多少項就執行多少次

4、按照數組的長度來遍歷多少次

for   ( var   j   =   0 ;   j   <   arr.length;   j ++ )   {

   for   ( var   i   =   0 ;   i   <   arr.length;   i ++ )   {

     // 判斷，如果數組中的當前一個比后一個大，那么兩個交換一下位置      if   (arr[i]   >   arr[i   +   1 ])   {

       var   tmp   =   arr[i]

       arr[i]   =   arr[i   +   1 ]

       arr[i   +   1 ]   =   tmp

     }

   }}

// 結束以后，數組就排序好了

5、給一些優化

·  想象一個問題，假設數組長度是 9，第八次排完以后

·  后面八個數字已經按照順序排列好了，剩下的那個最小的一定是在最前面

·  那么第九次就已經沒有意義了，因為最小的已經在最前面了，不會再有任何換位置出現了

·  那么我們第九次遍歷就不需要了，所以我們可以減少一次

for   ( var   j   =   0 ;   j   <   arr.length   -   1 ;   j ++ )   {

   for   ( var   i   =   0 ;   i   <   arr.length;   i ++ )   {

     // 判斷，如果數組中的當前一個比后一個大，那么兩個交換一下位置      if   (arr[i]   >   arr[i   +   1 ])   {

       var   tmp   =   arr[i]

       arr[i]   =   arr[i   +   1 ]

       arr[i   +   1 ]   =   tmp

     }

   }}

·  第二個問題，第一次的時候，已經把最大的數字放在最后面了

·  那么第二次的時候，其實倒數第二個和最后一個就不用比了

·  因為我們就是要把倒數第二大的放在倒數第二的位置，即使比較了，也不會換位置

·  第三次就要倒數第三個數字就不用再和后兩個比較了

·  以此類推，那么其實每次遍歷的時候，就遍歷當前次數 - 1 次

for   ( var   j   =   0 ;   j   <   arr.length   -   1 ;   j ++ )   {

   for   ( var   i   =   0 ;   i   <   arr.length   -   1   -   j;   i ++ )   {

     // 判斷，如果數組中的當前一個比后一個大，那么兩個交換一下位置      if   (arr[i]   >   arr[i   +   1 ])   {

       var   tmp   =   arr[i]

       arr[i]   =   arr[i   +   1 ]

       arr[i   +   1 ]   =   tmp

     }

   }}

6、至此，一個冒泡排序就完成了

選擇排序

·  先假定數組中的第 0 個就是最小的數字的索引

·  然后遍歷數組，只要有一個數字比我小，那么就替換之前記錄的索引

·  知道數組遍歷結束后，就能找到最小的那個索引，然后讓最小的索引換到第 0 個的位置

·  再來第二趟遍歷，假定第 1 個是最小的數字的索引

·  在遍歷一次數組，找到比我小的那個數字的索引

·  遍歷結束后換個位置

·  依次類推，也可以把數組排序好

1、準備一個數組 var arr = [3, 1, 5, 6, 4, 9, 7, 2, 8]

2、假定數組中的第 0 個是最小數字的索引 var minIndex = 0

3、遍歷數組，判斷，只要數字比我小，那么就替換掉原先記錄的索引

var   minIndex   =   0 for   ( var   i   =   0 ;   i   <   arr.length;   i ++ )   {

   if   (arr[i]   <   arr[minIndex])   {

     minIndex   =   i

   }}

// 遍歷結束后找到最小的索引// 讓第 minIndex 個和第 0 個交換 var   tmp   =   arr[minIndex]arr[minIndex]   =   arr[ 0 ]arr[ 0 ]   =   tmp

4、按照數組的長度重復執行上面的代碼

for   ( var   j   =   0 ;   j   <   arr.length;   j ++ )   {

   // 因為第一遍的時候假定第 0 個，第二遍的時候假定第 1 個    // 所以我們要假定第 j 個就行    var   minIndex   =   j

   // 因為之前已經把最小的放在最前面了，后面的循環就不需要判斷前面的了    // 直接從 j + 1 開始    for   ( var   i   =   j   +   1 ;   i   <   arr.length;   i ++ )   {

     if   (arr[i]   <   arr[minIndex])   {

       minIndex   =   i

     }

   }

   // 遍歷結束后找到最小的索引    // 第一堂的時候是和第 0 個交換，第二趟的時候是和第 1 個交換    // 我們直接和第 j 個交換就行    var   tmp   =   arr[minIndex]

   arr[minIndex]   =   arr[j]

   arr[j]   =   tmp}

5、一些優化

·  和之前一樣，倒數第二次排序完畢以后，就已經排好了，最后一次沒有必要了

for   ( var   j   =   0 ;   j   <   arr.length   -   1 ;   j ++ )   {

   var   minIndex   =   j

   for   ( var   i   =   j   +   1 ;   i   <   arr.length;   i ++ )   {

     if   (arr[i]   <   arr[minIndex])   {

       minIndex   =   i

     }

   }

   var   tmp   =   arr[minIndex]

   arr[minIndex]   =   arr[j]

   arr[j]   =   tmp}

·  在交換變量之前，可以判斷一下，如果我們遍歷后得到的索引和當前的索引一直

·  那么就證明當前這個就是目前最小的，那么就沒有必要交換

·  做一我們要判斷，最小作引和當前作引不一樣的時候，才交換

for   ( var   j   =   0 ;   j   <   arr.length   -   1 ;   j ++ )   {

   var   minIndex   =   j

   for   ( var   i   =   j   +   1 ;   i   <   arr.length;   i ++ )   {

     if   (arr[i]   <   arr[minIndex])   {

       minIndex   =   i

     }

   }

   if   (minIndex   !==   j)   {

     var   tmp   =   arr[minIndex]

     arr[minIndex]   =   arr[j]

     arr[j]   =   tmp    

   }}

6、至此，選擇排序完成