算法學(xué)習(xí)-JavaScript冒泡排序與選擇排序

法與數(shù)據(jù)結(jié)構(gòu)構(gòu)成了程序，數(shù)據(jù)結(jié)構(gòu)用于實(shí)現(xiàn)數(shù)據(jù)的表示、存儲(chǔ)、管理，算法通過使用數(shù)據(jù)完成一定的業(yè)務(wù)邏輯與操作，最終實(shí)現(xiàn)了程序的功能。因此算法在編程中的重要性是不言而喻的。很多復(fù)雜的算法都是借助最基本的算法實(shí)現(xiàn)的。本文主要選取經(jīng)典排序算法中的冒泡排序與選擇排序?qū)avaScript編程實(shí)現(xiàn)算法進(jìn)行簡(jiǎn)單描述與說(shuō)明。

程序算法

算法說(shuō)明

算法（Algorithm）是解決問題的一種策略機(jī)制，算法也是有限操作指令的集合。按照算法策略輸入符合要求的數(shù)據(jù)，最終獲得解決問題的輸出結(jié)果。冒泡算法與選擇算法主要用于實(shí)現(xiàn)對(duì)無(wú)序的數(shù)字集合進(jìn)行排序。算法描述分別如下：

1、冒泡排序算法

冒泡算法顧名思義，可以將待排序序列中的每一個(gè)元素看成一個(gè)個(gè)氣泡，假設(shè)氣泡的大小用元素的數(shù)值表示，這樣的話最大氣泡（最大的元素?cái)?shù)字）會(huì)最先升起來(lái)，這一過程即為冒泡。冒泡算法的關(guān)鍵在于將未排序部分最大元素依次后移動(dòng)，在序列尾端從小到大形成排序好的有序序列。冒泡排序示意如下圖所示：

冒泡排序算法示意圖

冒泡排序算法示意圖如上圖所示，其中每一行表示一次排序，排序目的找到最大值，從待排序序列中取出最大值，放到紅色小球區(qū)域中，紅色小球區(qū)域表示已完成排序的序列。通過上圖我們可以看出，每趟排序冒泡出來(lái)的元素分別為（17，12，9，5，1）。最終排好的序列為（1，5，9，12，17）。

2、選擇排序算法

選擇排序是指從未排序的序列中找到最小的值并取出放到已經(jīng)排好順序的序列中，一直到未排序序列中的元素個(gè)數(shù)為零。即所有的元素都放到已經(jīng)排好順序的序列中。該算法的關(guān)鍵在于從未排序的序列中找到最輕（數(shù)值最小）元素，放到已經(jīng)排序好的序列中。選擇排序算法示意如下圖所示：

選擇排序示意圖

選擇排序示意圖如上圖所示，選擇的關(guān)鍵在于找到最小的值，并將其放到已經(jīng)排序好的序列中。上圖中未排序（待排序）集合為黃色部分，排序好的部分為綠色背景部分，每一行為一次排序，排序目的找到最小元素。通過上圖可知選擇出來(lái)的最小值依次為（1，5，9，12，17）。

冒泡排序?qū)崿F(xiàn)

JavaScript冒泡排序主要借助JavaScript array數(shù)字對(duì)象實(shí)現(xiàn)待排序序列的存儲(chǔ)，通過循環(huán)語(yǔ)句遍歷數(shù)組，從待排序序列的第一個(gè)元素開始與后面元素比較，如大于后面元素則交換，因此經(jīng)過一趟遍歷，最大元素將會(huì)跑到array數(shù)組的末尾。實(shí)現(xiàn)代碼描述如下：

 var arr1=[9,1,4,13,7,8,20,23,15]; 
 var wlen1=arr1.length;
 var count1=0;//記錄總執(zhí)行次數(shù) 
 for(var i=0;i<arr1.length-1;i++) { 
 for(var j=0;j<wlen1;j++) { 
 if(arr1[j]>arr1[j+1]) { 
 var temp; 
 temp=arr1[j]; 
 arr1[j]=arr1[j+1]; 
 arr1[j+1]=temp; 
 count1++; 
 } 
 } 
 wlen1=wlen1-1; 
 }

選擇排序?qū)崿F(xiàn)

按照算法描述選擇排序需要使用兩個(gè)JavaScript數(shù)組對(duì)象，一個(gè)為待排序序列存儲(chǔ)數(shù)據(jù)，一個(gè)為排序完成數(shù)組。分別從待排序序列數(shù)組中找到最小值并取出存儲(chǔ)到完成排序數(shù)組中。arr數(shù)組為待排序數(shù)組，res數(shù)組為排序完成數(shù)組。使用javaScript實(shí)現(xiàn)選擇排序代碼描述如下：

 var arr=[9,1,4,13,7,8,20,23,15]; 
 var wlen=arr.length; 
 var count=0;//記錄已完成排序元素?cái)?shù)量 
 var res=[];//最終排序結(jié)果數(shù)組 
 var minvalue=0; //思路從未排序序列選擇最小元素放到已經(jīng)完成排序的數(shù)組中 
 for(var i=0;i<wlen;i++) { //找到最小元素 
 minvalue=arr[0]; 
 for(var j=0;j<arr.length;j++) { 
 if(minvalue>arr[j]) { 
 minvalue=arr[j]; 
 var temp; 
 temp=arr[0]; 
 arr[0]=arr[j]; 
 arr[j]=temp; 
 } 
 count++; 
 } 
 arr.shift(); 
 res[i]=minvalue; 
 }

JavaScript實(shí)現(xiàn)基本冒泡與選擇排序算法描述如上所示，本例設(shè)計(jì)測(cè)試用例為（9,1,4,13,7,8,20,23,15），該待排序測(cè)試用例分別執(zhí)行冒泡排序與選擇排序，效果展示如下圖

冒泡排序與選擇測(cè)試結(jié)果

本頭條號(hào)長(zhǎng)期關(guān)注編程資訊分享；編程課程、素材、代碼分享及編程培訓(xùn)。如果您對(duì)以上方面有興趣或代碼錯(cuò)誤、建議與意見，可以聯(lián)系作者，共同探討。期待大家關(guān)注！本文分類類別：算法學(xué)習(xí)|javasScript編程。

@Author：Runsen」

插入排序

插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。

一個(gè)有序的數(shù)組，我們往里面添加一個(gè)新的數(shù)據(jù)后，如何繼續(xù)保持?jǐn)?shù)據(jù)有序呢？很簡(jiǎn)單，我們只要遍歷數(shù)組，找到數(shù)據(jù)應(yīng)該插入的位置將其插入即可。

圖片來(lái)自王爭(zhēng)算法專欄

通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

插入排序在實(shí)現(xiàn)上，在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

因此，代碼編寫需要判斷插入元素和當(dāng)前元素的大小關(guān)系，遍歷時(shí)需要從數(shù)組的第二個(gè)數(shù)開始。

如果插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位。

如果插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位。直到找到一個(gè)當(dāng)前元素小于插入元素。

因此，在for循環(huán)遍歷時(shí)，又有一個(gè)while內(nèi)循環(huán)的條件，條件的內(nèi)容是插入元素的索引減一和零進(jìn)行對(duì)比。如果插入元素小于當(dāng)前元素，同時(shí)對(duì)索引進(jìn)行減一操作。如果出現(xiàn)了索引等于零的情況，那么表示插入元素等于當(dāng)前元素。

下面是插入排序的具體Python代碼。

def insert_sort(a):
    length = len(a)
    if length <= 1:
        return a
    # 從數(shù)組的第二個(gè)數(shù)開始
    for i in range(1, length):
        # 從后向前掃描
        j = i - 1
        # value指的是插入元素
        value = a[i]
        while j >= 0:
            if a[j] < value:
                # 插入元素大于當(dāng)前元素，則將待插入元素插入到當(dāng)前元素的后一位
                a[j + 1] = value
                break
            else:
                # 插入元素小于當(dāng)前元素，則將當(dāng)前元素后移一位
                a[j + 1] = a[j]
                if j == 0:
                    a[j] = value
            j -= 1
    return a


def insertionSort(arr):
    # 對(duì)上面的代碼進(jìn)行簡(jiǎn)單化
    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

if __name__ == '__main__':
    nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    insert_sort(nums)
    print(nums) # [17, 20, 26, 31, 44, 54, 55, 77, 93]

下面對(duì)Python代碼改為Java代碼。代碼來(lái)自菜鳥教程。

// Java
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        InsertSort(new int[] { 9 ,20 , 10, 13 , 12});
    }
    public static void InsertSort(int [] arr){
        int value; //待插入元素
        int index; //初始值為待插入元素前一個(gè)元素的索引

        for(int i= 1 ; i< arr.length;i++){
            //i從第二個(gè)元素開始，默認(rèn)第一個(gè)元素是有序的
            //循環(huán)條件是小于數(shù)組長(zhǎng)度，因?yàn)橐惨獙⒆詈笠粋€(gè)元素插入到前面的序列
            value = arr[i];
            index = i - 1;//初始為前一個(gè)元素
            while(index >=0 && value < arr[index]){
                //需要保證index合法
                //每當(dāng)前面的元素比待插入元素大，就向后移動(dòng)
                arr[index + 1] = arr[index];
                //不用怕覆蓋，因?yàn)関alue保存著待插入的值
                index--;
            }
            //當(dāng)退出循環(huán)，表明已經(jīng)找到了待插入位置，即index + 1
            arr[index + 1] = value;
        }

        System.out.println(Arrays.toString(arr));
    }
}

下面對(duì)Python代碼改為JavaScript代碼。代碼來(lái)自菜鳥教程。

// JavaScript
function insertionSort(arr) {
    var len = arr.length;
    // JavaScript需要聲明變量先
    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;
}

對(duì)于不同的查找插入點(diǎn)方法（從頭到尾、從尾到頭），元素的比較次數(shù)是有區(qū)別的。但對(duì)于一個(gè)給定的初始序列，移動(dòng)操作的次數(shù)總是固定的，就等于逆序度。

在插入排序中，對(duì)于值相同的元素，我們可以選擇將后面出現(xiàn)的元素，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩(wěn)定的排序算法。

對(duì)于插入排序來(lái)說(shuō)，每次插入操作都相當(dāng)于在數(shù)組中插入一個(gè)數(shù)據(jù)，循環(huán)執(zhí)行 n 次插入操作，所以平均時(shí)間復(fù)雜度為 O(n2)。

如果輸入數(shù)組已經(jīng)是排好序的話，插入排序出現(xiàn)最佳情況，其運(yùn)行時(shí)間是輸入規(guī)模的一個(gè)線性函數(shù)，其時(shí)間代價(jià)是O(n)。

如果輸入數(shù)組是逆序排列的，將出現(xiàn)最壞情況。平均情況與最壞情況一樣，其時(shí)間代價(jià)是 O(n2)。

參考：https://www.runoob.com/w3cnote/insertion-sort.html

選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。

選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。但是選擇排序每次會(huì)從未排序區(qū)間中找到最小的元素，將其放到已排序區(qū)間的末尾。

它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序：首先搜索整個(gè)列表，找到最小項(xiàng)的位置，如果該位置不是列表的第1項(xiàng)，就交換這兩個(gè)位置的元素。然后從列表的第2個(gè)元素開始，重復(fù)上述過程，直到算法達(dá)到整個(gè)過程的最后一個(gè)位置，圖形解釋如下

圖片來(lái)自王爭(zhēng)算法專欄

選擇排序還有一種代碼的形式是將最大值逐一選擇到后面，因此遍歷的時(shí)候需要逆序遍歷。

def selection_sort1(nums):
    # 思路是將最小值逐一選擇到前面
    n = len(nums)
    # 第一層for表示循環(huán)選擇的遍數(shù)

    for i in range(n - 1):
        min_index = i  # 記錄最小值的位置
        # 第二層for表示最小元素和后面的元素逐個(gè)比較

        for j in range(i + 1, n):
            if nums[j] < nums[min_index]:
                min_index = j
        if min_index != i:
           # 查找一遍后將最小元素與起始元素互換
            nums[i], nums[min_index] = nums[min_index], nums[i]

def selection_sort2(nums):
    # 思路是將最大值逐一選擇到后面
    n = len(nums)
    for i in range(n - 1, 0, -1):
        max_index = i  # 記錄最大值的位置
        for j in range(i):
            if nums[j] > nums[max_index]:
                max_index = j
        if max_index != i:
            nums[i], nums[max_index] = nums[max_index], nums[i]

下面對(duì)Python代碼改為Java代碼。代碼來(lái)自菜鳥教程，選擇第一種思路。

下面對(duì)Python代碼改為JavaScript代碼。代碼來(lái)自菜鳥教程。

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]) {     // 尋找最小的數(shù)
                minIndex = j;                 // 將最小數(shù)的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

選擇排序是一種不穩(wěn)定的排序算法。選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩(wěn)定性。

當(dāng)出現(xiàn)幾個(gè)值相同的時(shí)候，比如 5，8，5，2，9這樣一組數(shù)據(jù)，使用選擇排序算法來(lái)排序的話，第一次找到最小元素 2，與第一個(gè) 5 交換位置，那第一個(gè) 5 和中間的 5 順序就變了，所以就不穩(wěn)定了。

選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素。

它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換。

無(wú)論數(shù)列初始狀態(tài)怎樣，在第 i 趟排序中選出最小關(guān)鍵字的記錄，需做n-i次比較，因此，總的比較次數(shù)為：n(n-1)/2=O(n2)。

因此直接選擇排序的平均時(shí)間復(fù)雜度為 O(n2)。直接選擇排序是一個(gè)就地排序，空間復(fù)雜度為S(n)=O(1)。

參考：https://www.runoob.com/w3cnote/selection-sort.html

參考：極客時(shí)間王爭(zhēng)算法專欄

總結(jié) 來(lái)自極客時(shí)間王爭(zhēng)算法專欄

?
本文已收錄 GitHub，傳送門~[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。
?

Reference

[1]

傳送門~: https://github.com/MaoliRUNsen/runsenlearnpy100

冒泡排序概述

冒泡排序是通過遍歷待排序的數(shù)列，一次比較兩個(gè)元素，根據(jù)大小調(diào)換位置，直到把最大的或最小的冒出來(lái)的排序方式。與選擇排序、插入排序是比較常見的排序方式，也非常好理解。

冒泡排序平均時(shí)間復(fù)雜度是：O(n^2)

步驟是：

1、先建立兩個(gè)循環(huán)，外循環(huán)用于遍歷整個(gè)數(shù)組，內(nèi)循環(huán)遍歷待排序的區(qū)間。

2、內(nèi)循環(huán)每次都從第一項(xiàng)開始，將該項(xiàng)與后項(xiàng)進(jìn)行比較，再兩兩交換，一直到待排序結(jié)尾。

3、重復(fù)第二項(xiàng)，一直到數(shù)組遍歷完。

可以看成是用手捏住第一個(gè)位置，往右邊一個(gè)一個(gè)比較交換，把最大或最小的找出來(lái)，放在最后1位。然后再拿第一位置的數(shù)字，逐個(gè)比較，找出第二大的數(shù)字來(lái)放在倒數(shù)第2的位置。以此類推，把所有的數(shù)字都篩選一遍即可。

冒泡排序執(zhí)行過程分析

冒泡排序?qū)崿F(xiàn)

自左往右逐個(gè)將最大項(xiàng)冒出：

兩個(gè)循環(huán)，外循環(huán)是整個(gè)數(shù)列，內(nèi)循環(huán)是數(shù)列減去已排好序的數(shù)列。

自右往左逐個(gè)將最小項(xiàng)冒出：

冒泡排序的優(yōu)化

加入一個(gè)標(biāo)記，用來(lái)記錄上一趟排序中是否發(fā)生過交換，如果沒有進(jìn)行過交換，說(shuō)明當(dāng)前數(shù)組已經(jīng)排好序了，則不必再繼續(xù)后面的遍歷。

在線咨詢

上一篇：AngularJS 視圖
下一篇：小程序富文本（HTML+MarkDown），200+

您的項(xiàng)目需求

*請(qǐng)認(rèn)真填寫需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。

整合營(yíng)銷服務(wù)商

算法學(xué)習(xí)-JavaScript冒泡排序與選擇排序

算法說(shuō)明

冒泡排序?qū)崿F(xiàn)

選擇排序?qū)崿F(xiàn)

插入排序

選擇排序

Reference

冒泡排序概述

冒泡排序執(zhí)行過程分析

冒泡排序?qū)崿F(xiàn)

冒泡排序的優(yōu)化

您的項(xiàng)目需求