冒泡排序

冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀(guān)的排序算法。它重復地走訪(fǎng)過(guò)要排序的數列，一次比較兩個(gè)元素，如果他們的順序錯誤就把他們交換過(guò)來(lái)。走訪(fǎng)數列的工作是重復地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因為越小的元素會(huì )經(jīng)由交換慢慢“浮”到數列的頂端。

作為最簡(jiǎn)單的排序算法之一，冒泡排序給我的感覺(jué)就像 Abandon 在單詞書(shū)里出現的感覺(jué)一樣，每次都在第一頁(yè)第一位，所以最熟悉。冒泡排序還有一種優(yōu)化算法，就是立一個(gè) flag，當在一趟序列遍歷中元素沒(méi)有發(fā)生交換，則證明該序列已經(jīng)有序。但這種改進(jìn)對于提升性能來(lái)說(shuō)并沒(méi)有什么太大作用。

1、算法步驟

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對每一對相鄰元素作同樣的工作，從開(kāi)始第一對到結尾的最后一對。這步做完后，最后的元素會(huì )是最大的數。
針對所有的元素重復以上的步驟，除了最后一個(gè)。
持續每次對越來(lái)越少的元素重復上面的步驟，直到?jīng)]有任何一對數字需要比較。

2. 動(dòng)圖演示

3、什么時(shí)候最快

當輸入的數據已經(jīng)是正序時(shí)（都已經(jīng)是正序了，我還要你冒泡排序有何用?。?。

4、什么時(shí)候最慢

當輸入的數據是反序時(shí)（寫(xiě)一個(gè) for 循環(huán)反序輸出數據不就行了，干嘛要用你冒泡排序呢，我是閑的嗎）。

5、 JavaScript 代碼實(shí)現

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

6. Python 代碼實(shí)現

def bubbleSort(arr):    for i in range(1, len(arr)):        for j in range(0, len(arr)-i):            if arr[j] > arr[j+1]:                arr[j], arr[j + 1] = arr[j + 1], arr[j]    return arr

7. Go 代碼實(shí)現

func bubbleSort(arr []int) []int {    length := len(arr)    for i := 0; i < length; i++ {        for j := 0; j < length-1-i; j++ {            if arr[j] > arr[j+1] {                arr[j], arr[j+1] = arr[j+1], arr[j]            }        }    }    return arr}

選擇排序

選擇排序是一種簡(jiǎn)單直觀(guān)的排序算法，無(wú)論什么數據進(jìn)去都是 O(n2) 的時(shí)間復雜度。所以用到它的時(shí)候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。

1. 算法步驟

首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置
再從剩余未排序元素中繼續尋找最?。ù螅┰?，然后放到已排序序列的末尾。
重復第二步，直到所有元素均排序完畢。

2. 動(dòng)畫(huà)演示

3. JavaScript 代碼實(shí)現

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

4. Python 代碼實(shí)現

def selectionSort(arr):    for i in range(len(arr)-1):        for j in range(i+1, len(arr)):            if arr[j] < arr[i]:                arr[i], arr[j] = arr[j], arr[i]    return arr

5. Go 代碼實(shí)現

func selectionSort(arr []int) []int {    length := len(arr)    for i := 0; i < length-1; i++ {        min := i        for j := i + 1; j < length; j++ {            if arr[min] > arr[j] {                min = j            }        }        arr[i], arr[min] = arr[min], arr[i]    }    return arr}

插入排序

插入排序的代碼實(shí)現雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應該是最容易理解的了，因為只要打過(guò)撲克牌的人都應該能夠秒懂。

插入排序是一種最簡(jiǎn)單直觀(guān)的排序算法，它的工作原理是通過(guò)構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。

1. 算法步驟

將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當成是未排序序列。
從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）

2. 動(dòng)圖演示

3. JavaScript 代碼實(shí)現

function insertionSort(arr) {    var len = arr.length;    var preIndex, current;    for (var i = 1; i < len; i++) {        preIndex = i - 1;        current = arr[i];        while(preIndex >= 0 && arr[preIndex] > current) {            arr[preIndex+1] = arr[preIndex];            preIndex--;        }        arr[preIndex+1] = current;    }    return arr;}

4. Python 代碼實(shí)現

def insertionSort(arr):    for i in range(len(arr)):        preIndex = i-1        current = arr[i]        while preIndex >= 0 and arr[preIndex] > current:            arr[preIndex+1] = arr[preIndex]            preIndex-=1        arr[preIndex+1] = current    return arr

5. Go 代碼實(shí)現

func insertionSort(arr []int) []int {    for i := range arr {        preIndex := i - 1        current := arr[i]        for preIndex >= 0 && arr[preIndex] > current {            arr[preIndex+1] = arr[preIndex]            preIndex -= 1        }        arr[preIndex+1] = current    }    return arr}

希爾排序

希爾排序，也稱(chēng)遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩定排序算法。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

插入排序在對幾乎已經(jīng)排好序的數據操作時(shí)，效率高，即可以達到線(xiàn)性排序的效率；
但插入排序一般來(lái)說(shuō)是低效的，因為插入排序每次只能將數據移動(dòng)一位；

希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行依次直接插入排序。

1. 算法步驟

選擇一個(gè)增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列個(gè)數 k，對序列進(jìn)行 k 趟排序；
每趟排序，根據對應的增量 ti，將待排序列分割成若干長(cháng)度為 m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為 1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(cháng)度即為整個(gè)序列的長(cháng)度。

2. JavaScript 代碼實(shí)現

function shellSort(arr) {    var len = arr.length,        temp,        gap = 1;    while(gap < len/3) {          //動(dòng)態(tài)定義間隔序列        gap =gap*3+1;    }    for (gap; gap > 0; gap = Math.floor(gap/3)) {        for (var i = gap; i < len; i++) {            temp = arr[i];            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {                arr[j+gap] = arr[j];            }            arr[j+gap] = temp;        }    }    return arr;}

3. Python 代碼實(shí)現

def shellSort(arr):    import math    gap=1    while(gap < len(arr)/3):        gap = gap*3+1    while gap > 0:        for i in range(gap,len(arr)):            temp = arr[i]            j = i-gap            while j >=0 and arr[j] > temp:                arr[j+gap]=arr[j]                j-=gap            arr[j+gap] = temp        gap = math.floor(gap/3)    return arr}

4. Go 代碼實(shí)現

func shellSort(arr []int) []int {    length := len(arr)    gap := 1    for gap < gap/3 {        gap = gap*3 + 1    }    for gap > 0 {        for i := gap; i < length; i++ {            temp := arr[i]            j := i - gap            for j >= 0 && arr[j] > temp {                arr[j+gap] = arr[j]                j -= gap            }            arr[j+gap] = temp        }        gap = gap / 3    }    return arr}

歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應用。

作為一種典型的分而治之思想的算法應用，歸并排序的實(shí)現由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫(xiě)，所以就有了第 2 種方法）；
自下而上的迭代；

和選擇排序一樣，歸并排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因為始終都是 O(nlogn) 的時(shí)間復雜度。代價(jià)是需要額外的內存空間。

2. 算法步驟

申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；
設定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
比較兩個(gè)指針所指向的元素，選擇相對小的元素放入到合并空間，并移動(dòng)指針到下一位置；
重復步驟 3 直到某一指針達到序列尾；
將另一序列剩下的所有元素直接復制到合并序列尾。

3. 動(dòng)圖演示

4. JavaScript 代碼實(shí)現

function mergeSort(arr) {  // 采用自上而下的遞歸方法    var len = arr.length;    if(len < 2) {        return arr;    }    var middle = Math.floor(len / 2),        left = arr.slice(0, middle),        right = arr.slice(middle);    return merge(mergeSort(left), mergeSort(right));}
function merge(left, right){    var result = [];
    while (left.length && right.length) {        if (left[0] <= right[0]) {            result.push(left.shift());        } else {            result.push(right.shift());        }    }
    while (left.length)        result.push(left.shift());
    while (right.length)        result.push(right.shift());
    return result;}

5. Python 代碼實(shí)現

def mergeSort(arr):    import math    if(len(arr)<2):        return arr    middle = math.floor(len(arr)/2)    left, right = arr[0:middle], arr[middle:]    return merge(mergeSort(left), mergeSort(right))
def merge(left,right):    result = []    while left and right:        if left[0] <= right[0]:            result.append(left.pop(0));        else:            result.append(right.pop(0));    while left:        result.append(left.pop(0));    while right:        result.append(right.pop(0));    return result

6. Go 代碼實(shí)現

func mergeSort(arr []int) []int {    length := len(arr)    if length < 2 {        return arr    }    middle := length / 2    left := arr[0:middle]    right := arr[middle:]    return merge(mergeSort(left), mergeSort(right))}
func merge(left []int, right []int) []int {    var result []int    for len(left) != 0 && len(right) != 0 {        if left[0] <= right[0] {            result = append(result, left[0])            left = left[1:]        } else {            result = append(result, right[0])            right = right[1:]        }    }
    for len(left) != 0 {        result = append(result, left[0])        left = left[1:]    }
    for len(right) != 0 {        result = append(result, right[0])        right = right[1:]    }
    return result}

快速排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實(shí)現出來(lái)。

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應用。本質(zhì)上來(lái)看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起的是簡(jiǎn)單粗暴，因為一聽(tīng)到這個(gè)名字你就知道它存在的意義，就是快，而且效率高！它是處理大數據最快的排序算法之一了。雖然 Worst Case 的時(shí)間復雜度達到了 O(n2)，但是人家就是優(yōu)秀，在大多數情況下都比平均時(shí)間復雜度為 O(n logn) 的排序算法表現要更好。

1. 算法步驟

從數列中挑出一個(gè)元素，稱(chēng)為 “基準”（pivot）;
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個(gè)分區退出之后，該基準就處于數列的中間位置。這個(gè)稱(chēng)為分區（partition）操作；
遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序；

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì )退出，因為在每次的迭代（iteration）中，它至少會(huì )把一個(gè)元素擺到它最后的位置去。

2. 動(dòng)圖演示

3. JavaScript 代碼實(shí)現

function quickSort(arr, left, right) {    var len = arr.length,        partitionIndex,        left = typeof left != 'number' ? 0 : left,        right = typeof right != 'number' ? len - 1 : right;
    if (left < right) {        partitionIndex = partition(arr, left, right);        quickSort(arr, left, partitionIndex-1);        quickSort(arr, partitionIndex+1, right);    }    return arr;}
function partition(arr, left ,right) {     // 分區操作    var pivot = left,                      // 設定基準值（pivot）        index = pivot + 1;    for (var i = index; i <= right; i++) {        if (arr[i] < arr[pivot]) {            swap(arr, i, index);            index++;        }    }    swap(arr, pivot, index - 1);    return index-1;}
function swap(arr, i, j) {    var temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}functiion paritition2(arr, low, high) {  let pivot = arr[low];  while (low < high) {    while (low < high && arr[high] > pivot) {      --high;    }    arr[low] = arr[high];    while (low < high && arr[low] <= pivot) {      ++low;    }    arr[high] = arr[low];  }  arr[low] = pivot;  return low;}
function quickSort2(arr, low, high) {  if (low < high) {    let pivot = paritition2(arr, low, high);    quickSort2(arr, low, pivot - 1);    quickSort2(arr, pivot + 1, high);  }  return arr;}

4. Python 代碼實(shí)現

def quickSort(arr, left=None, right=None):    left = 0 if not isinstance(left,(int, float)) else left    right = len(arr)-1 if not isinstance(right,(int, float)) else right    if left < right:        partitionIndex = partition(arr, left, right)        quickSort(arr, left, partitionIndex-1)        quickSort(arr, partitionIndex+1, right)    return arr
def partition(arr, left, right):    pivot = left    index = pivot+1    i = index    while  i <= right:        if arr[i] < arr[pivot]:            swap(arr, i, index)            index+=1        i+=1    swap(arr,pivot,index-1)    return index-1
def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]

5. Go 代碼實(shí)現

func quickSort(arr []int) []int {    return _quickSort(arr, 0, len(arr)-1)}
func _quickSort(arr []int, left, right int) []int {    if left < right {        partitionIndex := partition(arr, left, right)        _quickSort(arr, left, partitionIndex-1)        _quickSort(arr, partitionIndex+1, right)    }    return arr}
func partition(arr []int, left, right int) int {    pivot := left    index := pivot + 1
    for i := index; i <= right; i++ {        if arr[i] < arr[pivot] {            swap(arr, i, index)            index += 1        }    }    swap(arr, pivot, index-1)    return index - 1}
func swap(arr []int, i, j int) {    arr[i], arr[j] = arr[j], arr[i]}

6. C++版

 //標準分割函數 Paritition1(int A[], int low, int high) {   int pivot = A[low];   while (low < high) {     while (low < high && A[high] >= pivot) {       --high;     }     A[low] = A[high];     while (low < high && A[low] <= pivot) {       ++low;     }     A[high] = A[low];   }   A[low] = pivot;   return low; }
 void QuickSort(int A[], int low, int high) //快排母函數 {   if (low < high) {     int pivot = Paritition1(A, low, high);     QuickSort(A, low, pivot - 1);     QuickSort(A, pivot + 1, high);   } }

堆排序

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結構，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結點(diǎn)的鍵值或索引總是小于（或者大于）它的父節點(diǎn)。堆排序可以說(shuō)是一種利用堆的概念來(lái)排序的選擇排序。分為兩種方法：

大頂堆：每個(gè)節點(diǎn)的值都大于或等于其子節點(diǎn)的值，在堆排序算法中用于升序排列；
小頂堆：每個(gè)節點(diǎn)的值都小于或等于其子節點(diǎn)的值，在堆排序算法中用于降序排列；

堆排序的平均時(shí)間復雜度為 Ο(nlogn)。

1. 算法步驟

創(chuàng )建一個(gè)堆 H[0……n-1]；
把堆首（最大值）和堆尾互換；
把堆的尺寸縮小 1，并調用 shift_down(0)，目的是把新的數組頂端數據調整到相應位置；
重復步驟 2，直到堆的尺寸為 1。

2. JavaScript 代碼實(shí)現

var len;    // 因為聲明的多個(gè)函數都需要數據長(cháng)度，所以把len設置成為全局變量
function buildMaxHeap(arr) {   // 建立大頂堆    len = arr.length;    for (var i = Math.floor(len/2); i >= 0; i--) {        heapify(arr, i);    }}
function heapify(arr, i) {     // 堆調整    var left = 2 * i + 1,        right = 2 * i + 2,        largest = i;
    if (left < len && arr[left] > arr[largest]) {        largest = left;    }
    if (right < len && arr[right] > arr[largest]) {        largest = right;    }
    if (largest != i) {        swap(arr, i, largest);        heapify(arr, largest);    }}
function swap(arr, i, j) {    var temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}
function heapSort(arr) {    buildMaxHeap(arr);
    for (var i = arr.length-1; i > 0; i--) {        swap(arr, 0, i);        len--;        heapify(arr, 0);    }    return arr;}

3. Python 代碼實(shí)現

def buildMaxHeap(arr):    import math    for i in range(math.floor(len(arr)/2),-1,-1):        heapify(arr,i)
def heapify(arr, i):    left = 2*i+1    right = 2*i+2    largest = i    if left < arrLen and arr[left] > arr[largest]:        largest = left    if right < arrLen and arr[right] > arr[largest]:        largest = right
    if largest != i:        swap(arr, i, largest)        heapify(arr, largest)
def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):    global arrLen    arrLen = len(arr)    buildMaxHeap(arr)    for i in range(len(arr)-1,0,-1):        swap(arr,0,i)        arrLen -=1        heapify(arr, 0)    return arr

4. Go 代碼實(shí)現

func heapSort(arr []int) []int {    arrLen := len(arr)    buildMaxHeap(arr, arrLen)    for i := arrLen - 1; i >= 0; i-- {        swap(arr, 0, i)        arrLen -= 1        heapify(arr, 0, arrLen)    }    return arr}
func buildMaxHeap(arr []int, arrLen int) {    for i := arrLen / 2; i >= 0; i-- {        heapify(arr, i, arrLen)    }}
func heapify(arr []int, i, arrLen int) {    left := 2*i + 1    right := 2*i + 2    largest := i    if left < arrLen && arr[left] > arr[largest] {        largest = left    }    if right < arrLen && arr[right] > arr[largest] {        largest = right    }    if largest != i {        swap(arr, i, largest)        heapify(arr, largest, arrLen)    }}
func swap(arr []int, i, j int) {    arr[i], arr[j] = arr[j], arr[i]}

計數排序

計數排序的核心在于將輸入的數據值轉化為鍵存儲在額外開(kāi)辟的數組空間中。作為一種線(xiàn)性時(shí)間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

1. 動(dòng)圖演示

2. JavaScript 代碼實(shí)現

function countingSort(arr, maxValue) {    var bucket = new Array(maxValue+1),        sortedIndex = 0;        arrLen = arr.length,        bucketLen = maxValue + 1;
    for (var i = 0; i < arrLen; i++) {        if (!bucket[arr[i]]) {            bucket[arr[i]] = 0;        }        bucket[arr[i]]++;    }
    for (var j = 0; j < bucketLen; j++) {        while(bucket[j] > 0) {            arr[sortedIndex++] = j;            bucket[j]--;        }    }
    return arr;}

3. Python 代碼實(shí)現

def countingSort(arr, maxValue):    bucketLen = maxValue+1    bucket = [0]*bucketLen    sortedIndex =0    arrLen = len(arr)    for i in range(arrLen):        if not bucket[arr[i]]:            bucket[arr[i]]=0        bucket[arr[i]]+=1    for j in range(bucketLen):        while bucket[j]>0:            arr[sortedIndex] = j            sortedIndex+=1            bucket[j]-=1    return arr

4. Go 代碼實(shí)現

func countingSort(arr []int, maxValue int) []int {    bucketLen := maxValue + 1    bucket := make([]int, bucketLen) // 初始為0的數組
    sortedIndex := 0    length := len(arr)
    for i := 0; i < length; i++ {        bucket[arr[i]] += 1    }
    for j := 0; j < bucketLen; j++ {        for bucket[j] > 0 {            arr[sortedIndex] = j            sortedIndex += 1            bucket[j] -= 1        }    }
    return arr}

桶排序

桶排序是計數排序的升級版。它利用了函數的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點(diǎn)：

在額外空間充足的情況下，盡量增大桶的數量
使用的映射函數能夠將輸入的 N 個(gè)數據均勻的分配到 K 個(gè)桶中

同時(shí)，對于桶中元素的排序，選擇何種比較排序算法對于性能的影響至關(guān)重要。

1. 什么時(shí)候最快

當輸入的數據可以均勻的分配到每一個(gè)桶中。

2. 什么時(shí)候最慢

當輸入的數據被分配到了同一個(gè)桶中。

3. JavaScript 代碼實(shí)現

function bucketSort(arr, bucketSize) {    if (arr.length === 0) {      return arr;    }
    var i;    var minValue = arr[0];    var maxValue = arr[0];    for (i = 1; i < arr.length; i++) {      if (arr[i] < minValue) {          minValue = arr[i];                // 輸入數據的最小值      } else if (arr[i] > maxValue) {          maxValue = arr[i];                // 輸入數據的最大值      }    }
    //桶的初始化    var DEFAULT_BUCKET_SIZE = 5;            // 設置桶的默認數量為5    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;    var buckets = new Array(bucketCount);    for (i = 0; i < buckets.length; i++) {        buckets[i] = [];    }
    //利用映射函數將數據分配到各個(gè)桶中    for (i = 0; i < arr.length; i++) {        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);    }
    arr.length = 0;    for (i = 0; i < buckets.length; i++) {        insertionSort(buckets[i]);                      // 對每個(gè)桶進(jìn)行排序，這里使用了插入排序        for (var j = 0; j < buckets[i].length; j++) {            arr.push(buckets[i][j]);        }    }
    return arr;}

基數排序

基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個(gè)位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點(diǎn)數，所以基數排序也不是只能使用于整數。

1. 基數排序 vs 計數排序 vs 桶排序

基數排序有兩種方法：

這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異：

基數排序：根據鍵值的每位數字來(lái)分配桶；
計數排序：每個(gè)桶只存儲單一鍵值；
桶排序：每個(gè)桶存儲一定范圍的數值；

2. LSD 基數排序動(dòng)圖演示

3. JavaScript 代碼實(shí)現

//LSD Radix Sortvar counter = [];function radixSort(arr, maxDigit) {    var mod = 10;    var dev = 1;    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {        for(var j = 0; j < arr.length; j++) {            var bucket = parseInt((arr[j] % mod) / dev);            if(counter[bucket]==null) {                counter[bucket] = [];            }            counter[bucket].push(arr[j]);        }        var pos = 0;        for(var j = 0; j < counter.length; j++) {            var value = null;            if(counter[j]!=null) {                while ((value = counter[j].shift()) != null) {                      arr[pos++] = value;                }          }        }    }    return arr;}

本文完~

本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請點(diǎn)擊舉報。

欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久

冒泡排序

1、算法步驟

2. 動(dòng)圖演示

3、 什么時(shí)候最快

4、 什么時(shí)候最慢

5、 JavaScript 代碼實(shí)現

6. Python 代碼實(shí)現

7. Go 代碼實(shí)現

選擇排序

1. 算法步驟

2. 動(dòng)畫(huà)演示

3. JavaScript 代碼實(shí)現

4. Python 代碼實(shí)現

5. Go 代碼實(shí)現

插入排序

1. 算法步驟

2. 動(dòng)圖演示

3. JavaScript 代碼實(shí)現

4. Python 代碼實(shí)現

5. Go 代碼實(shí)現

希爾排序

1. 算法步驟

2. JavaScript 代碼實(shí)現

3. Python 代碼實(shí)現

4. Go 代碼實(shí)現

歸并排序

2. 算法步驟

3. 動(dòng)圖演示

4. JavaScript 代碼實(shí)現

5. Python 代碼實(shí)現

6. Go 代碼實(shí)現

快速排序

1. 算法步驟

2. 動(dòng)圖演示

3. JavaScript 代碼實(shí)現

4. Python 代碼實(shí)現

5. Go 代碼實(shí)現

6. C++版

堆排序

1. 算法步驟

2. JavaScript 代碼實(shí)現

3. Python 代碼實(shí)現

4. Go 代碼實(shí)現

計數排序

1. 動(dòng)圖演示

2. JavaScript 代碼實(shí)現

3. Python 代碼實(shí)現

4. Go 代碼實(shí)現

桶排序

1. 什么時(shí)候最快

2. 什么時(shí)候最慢

3. JavaScript 代碼實(shí)現

基數排序

1. 基數排序 vs 計數排序 vs 桶排序

2. LSD 基數排序動(dòng)圖演示

3. JavaScript 代碼實(shí)現

1、算法步驟

3、什么時(shí)候最快

4、什么時(shí)候最慢

5、 JavaScript 代碼實(shí)現