前端之多種排序方式

ShevaKuilin 發(fā)布于2019-08-26 14:05 / 2995人閱讀

摘要：前言排序是編程中很基礎(chǔ)卻很有學(xué)問的算法。常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。本文主要闡述前端面試中最常問的三種排序冒泡排序選擇排序，其他排序方法詳情點我。冒泡排序算法描述比較相鄰的元素。

前言

排序是編程中很基礎(chǔ)卻很有學(xué)問的算法。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。本文主要闡述前端面試中最常問的三種排序：冒泡排序、選擇排序，其他排序方法詳情點我。
*本文參考鏈接點我。

冒泡排序

算法描述：

比較相鄰的元素。如果前一個比后一個大，就交換他們兩個，這樣循環(huán)到最后，最后一位數(shù)將是最大的數(shù)。

最后一個數(shù)確定了后不再進(jìn)行比較，重復(fù)步驟1，不斷確定新一輪最大的數(shù)值后將其固定不比較，最后所有數(shù)據(jù)比較完則完成排序。

動圖演示：

代碼實現(xiàn)：

function bubbleSort(arr) {   
    for (var i = 0; i < arr.length - 1; i++) {   
        for (var j = 0; j < arr.length - 1 - i; j++) {   
            if (arr[j] > arr[j+1]) {        // 相鄰元素兩兩對比   
                var temp = arr[j+1];        // 元素交換   
                arr[j+1] = arr[j];   
                arr[j] = temp;   
            }   
        }   
    }   
    return arr;   
}

選擇排序

算法描述：每次都找一個最大或者最小的排在開始即可。例如，你想從小到大排列，就找出最大的放第一位，通過循環(huán)不斷找出當(dāng)時最大值并插入第一位，最后就會從小到大排列了。

動圖演示：

代碼實現(xiàn)：

function selectionSort(arr) {      
    var minIndex, temp;                                               
    for (var i = 0; i < arr.length - 1; i++) {   
        minIndex = i;   
        for (var j = i + 1; j < arr.length ; j++) {   
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數(shù)   
                minIndex = j;                 // 將最小數(shù)的索引保存   
            }   
        }   
        temp = arr[i];   
        arr[i] = arr[minIndex];   
        arr[minIndex] = temp;   
    }   
    return arr;   
}