javascript實作五大排序演算法（冒泡排序、選擇排序、插入排序、希爾排序、快速排序）j

排序演算法之冒泡排序演算法O(N*N)：

原理：
1、對未排序的各個元素從頭到尾依次比較相鄰的兩個元素大小關系
2、如果左邊的元素大，則兩元素交換位置
3、向右移動一個位置，比較下面兩個元素
4、移動到最右端是，此時最大的元素在最右端
5、然后從新按照思路開始，這次走到倒數第二個位置即可，依次類推 完成排序

代碼實作：

let array = [78,1,56,45,12,36,99,84,23,7]

for (let j = array.length - 1; j >= 0; j--) {
    for (let i = 0; i < j; i++) {
        if (array[i] > array[i+1]) {
            let temp = array[i]
            array[i] = array[i+1]
            array[i+1] = temp
        }
    }
}
console.log(array.join())

結果

1 7 12 23 36 45 56 78 84 99

排序演算法之選擇排序演算法O(N)：

原理：
1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
2、再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，
3、重復第二步，直到所有元素均排序完畢，

代碼實作：

let array = [78,1,56,45,12,36,99,84,23,7]
//選擇排序
for (let j = 0; j < array.length - 1; j++) {
    let min = j
    for (let i = min + 1; i < array.length; i++) {
        if (array[min] > array[i]) {
            min = i
        }
     }
    let temp = array[j]
    array[j] = array[min]
    array[min] = temp
}

結果：

1 7 12 23 36 45 56 78 84 99

排序演算法之插入排序演算法：

原理：
1、從陣列的第二個資料開始往前比較，即一開始用第二個數和他前面的一個比較，如果 符合條件（比前面的大或者小，自定義），則讓他們交換位置，
2、然后再用第三個數和第二個比較，符合則交換，但是此處還得繼續往前比較，比如有 5個數8，15，20，45, 17,17比45小，需要交換，但是17也比20小，也要交換，當不需 要和15交換以后，說明也不需要和15前面的資料比較了，肯定不需要交換，因為前 面的資料都是有序的，
3、重復步驟二，一直到資料全都排完，

代碼實作：

let array = [78,1,56,45,12,36,99,84,23,7]
//插入排序
for (let i = 1; i < array.length; i++) {
    let temp = array[i]
    let j = i
    while (array[j - 1] > temp && j > 0) {
        array[j] = array[j - 1]
        j--
    }
    array[j] = temp
}

結果：

1 7 12 23 36 45 56 78 84 99

排序演算法之希爾排序演算法：

希爾排序是希爾（Donald Shell）于1959年提出的一種排序演算法，希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，演算法便終止，

代碼實作：

let array = [78,1,56,45,12,36,99,84,23,7]
//第一種增量
//希爾排序
//初始化增量
let gap = Math.floor(array.length / 2)

while (gap >= 1) {
     for (let i = gap; i < array.length; i++) {
         let temp = array[i]
         let j = i

         while (array[j - gap] > temp && j > gap - 1) {
             array[j] = array[j - gap]
             j -= gap
         }
         array[j] = temp
     }

     gap = Math.floor(gap / 2)
}

結果：

1 7 12 23 36 45 56 78 84 99

排序演算法之快速排序演算法：

步驟：
1. 在陣列中選一個基準數；
2. 將陣列中小于基準數的資料移到基準數左邊，大于基準數的移到右邊；
3. 對于基準數左、右兩邊的陣列，不斷重復以上兩個程序，直到每個子集只有一個元素，即為全部有序，
基準數的選取：
通常選取陣列的第一個元素

let array = [78,1,56,45,12,36,99,84,23,7]
                       
function QuickSort(array,left,right) {
    if (left >= right) {
       return
    }

    let pivot = array[left] //將區間的第一個數作為基準數
    let l = left //從左到右進行查找時的“指標”，指示當前左位置
    let r = right //從右到左進行查找時的“指標”，指示當前右位置

   while ( l < r) {
        while ( l < r && array[r] > pivot) {
            r--
        }
       while ( l < r && array[l] <= pivot) {
           l++
       }
       if (l < r) {
           let temp = array[l]
           array[l] = array[r]
           array[r] = temp
       }
   }
    array[left] = array[l]
    array[l] = pivot
    QuickSort(array,left,l-1)
    QuickSort(array,l+1,right)
}

QuickSort(array,0,array.length - 1)
console.log(array.join(' '))

結果：

1 7 12 23 36 45 56 78 84 99