? 五大經典排序算法動圖演示-【元標seo】

五大經典排序算法動圖演示

作者: 杭州網站優化公司 分類: 搜索引擎算法 發布時間: 2018-04-30 16:05 0

0、算法概述

0.1 算法分類

十種常見排序算法可以分為兩大類:

非線性時間比較類排序:通過比較來決定元素間的相對次序,由于其時間復雜度不能突破O(nlogn),因此稱為非線性時間比較類排序。

線性時間非比較類排序:不通過比較來決定元素間的相對次序,它可以突破基于比較排序的時間下界,以線性時間運行,因此稱為線性時間非比較類排序。 

十大經典排序算法動圖演示

0.2 算法復雜度

十大經典排序算法動圖演示

0.3 相關概念

穩定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

不穩定:如果a原本在b的前面,而a=b,排序之后 a 可能會出現在 b 的后面。

時間復雜度:對排序數據的總的操作次數。反映當n變化時,操作次數呈現什么規律。

空間復雜度:是指算法在計算機內執行時所需存儲空間的度量,它也是數據規模n的函數。 

1、冒泡排序(Bubble Sort)

冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。 

1.1 算法描述

  • 比較相鄰的元素。如果第一個比第二個大,就交換它們兩個;
  • 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最后一對,這樣在最后的元素應該會是最大的數;
  • 針對所有的元素重復以上的步驟,除了最后一個;
  • 重復步驟1~3,直到排序完成。

1.2 動圖演示

十大經典排序算法動圖演示

1.3 代碼實現

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; 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;
}

2、選擇排序(Selection Sort)

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再從剩余未排序元素中繼續尋找最小(大)元素,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。 

2.1 算法描述

n個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下:

  • 初始狀態:無序區為R[1..n],有序區為空;
  • 第i趟排序(i=1,2,3…n-1)開始時,當前有序區和無序區分別為R[1..i-1]和R(i..n)。該趟排序從當前無序區中-選出關鍵字最小的記錄 R[k],將它與無序區的第1個記錄R交換,使R[1..i]和R[i+1..n)分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區;
  • n-1趟結束,數組有序化了。

2.2 動圖演示

十大經典排序算法動圖演示  

2.3 代碼實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;

2.4 算法分析

表現最穩定的排序算法之一,因為無論什么數據進去都是O(n2)的時間復雜度,所以用到它的時候,數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。理論上講,選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

3、插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列,對于未排序數據,在已排序序列中從后向前掃描,找到相應位置并插入。

3.1 算法描述

一般來說,插入排序都采用in-place在數組上實現。具體算法描述如下:

  • 從第一個元素開始,該元素可以認為已經被排序;
  • 取出下一個元素,在已經排序的元素序列中從后向前掃描;
  • 如果該元素(已排序)大于新元素,將該元素移到下一位置;
  • 重復步驟3,直到找到已排序的元素小于或者等于新元素的位置;
  • 將新元素插入到該位置后;
  • 重復步驟2~5。

3.2 動圖演示

十大經典排序算法動圖演示

3.2 代碼實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

3.4 算法分析

插入排序在實現上,通常采用in-place排序(即只需用到O(1)的額外空間的排序),因而在從后向前掃描過程中,需要反復把已排序元素逐步向后挪位,為最新元素提供插入空間。

4、希爾排序(Shell Sort)

1959年Shell發明,第一個突破O(n2)的排序算法,是簡單插入排序的改進版。它與插入排序的不同之處在于,它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序

4.1 算法描述

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序,具體算法描述:

  • 選擇一個增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  • 按增量序列個數k,對序列進行k 趟排序;
  • 每趟排序,根據對應的增量ti,將待排序列分割成若干長度為m 的子序列,分別對各子表進行直接插入排序。僅增量因子為1 時,整個序列作為一個表來處理,表長度即為整個序列的長度。

4.2 動圖演示

十大經典排序算法動圖演示

4.3 代碼實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while (gap < len / 3) {         // 動態定義間隔序列
        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;
}

4.4 算法分析

希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列,也可以動態的定義間隔序列。動態定義間隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的。 

5、歸并排序(Merge Sort)

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為2-路歸并。 

5.1 算法描述

  • 把長度為n的輸入序列分成兩個長度為n/2的子序列;
  • 對這兩個子序列分別采用歸并排序;
  • 將兩個排序好的子序列合并成一個最終的排序序列。

5.2 動圖演示

十大經典排序算法動圖演示

5.3 代碼實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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>0 && right.length>0) {
        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.4 算法分析

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

轉載請注明出處:http://www./seojishu/suanfa/865.html