整合營銷服務商
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
法與數據結構構成了程序，數據結構用于實現數據的表示、存儲、管理，算法通過使用數據完成一定的業務邏輯與操作，最終實現了程序的功能。因此算法在編程中的重要性是不言而喻的。很多復雜的算法都是借助最基本的算法實現的。本文主要選取經典排序算法中的冒泡排序與選擇排序對JavaScript編程實現算法進行簡單描述與說明。
程序算法
算法（Algorithm）是解決問題的一種策略機制，算法也是有限操作指令的集合。按照算法策略輸入符合要求的數據，最終獲得解決問題的輸出結果。冒泡算法與選擇算法主要用于實現對無序的數字集合進行排序。算法描述分別如下：
1、冒泡排序算法
冒泡算法顧名思義，可以將待排序序列中的每一個元素看成一個個氣泡，假設氣泡的大小用元素的數值表示，這樣的話最大氣泡（最大的元素數字）會最先升起來，這一過程即為冒泡。冒泡算法的關鍵在于將未排序部分最大元素依次后移動，在序列尾端從小到大形成排序好的有序序列。冒泡排序示意如下圖所示：
冒泡排序算法示意圖
冒泡排序算法示意圖如上圖所示，其中每一行表示一次排序，排序目的找到最大值，從待排序序列中取出最大值，放到紅色小球區域中，紅色小球區域表示已完成排序的序列。通過上圖我們可以看出，每趟排序冒泡出來的元素分別為（17，12，9，5，1）。最終排好的序列為（1，5，9，12，17）。
2、選擇排序算法
選擇排序是指從未排序的序列中找到最小的值并取出放到已經排好順序的序列中，一直到未排序序列中的元素個數為零。即所有的元素都放到已經排好順序的序列中。該算法的關鍵在于從未排序的序列中找到最輕（數值最小）元素，放到已經排序好的序列中。選擇排序算法示意如下圖所示：
選擇排序示意圖
選擇排序示意圖如上圖所示，選擇的關鍵在于找到最小的值，并將其放到已經排序好的序列中。上圖中未排序（待排序）集合為黃色部分，排序好的部分為綠色背景部分，每一行為一次排序，排序目的找到最小元素。通過上圖可知選擇出來的最小值依次為（1，5，9，12，17）。
JavaScript冒泡排序主要借助JavaScript array數字對象實現待排序序列的存儲，通過循環語句遍歷數組，從待排序序列的第一個元素開始與后面元素比較，如大于后面元素則交換，因此經過一趟遍歷，最大元素將會跑到array數組的末尾。實現代碼描述如下：
var arr1=[9,1,4,13,7,8,20,23,15];
var wlen1=arr1.length;
var count1=0;//記錄總執行次數
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;
}
按照算法描述選擇排序需要使用兩個JavaScript數組對象，一個為待排序序列存儲數據，一個為排序完成數組。分別從待排序序列數組中找到最小值并取出存儲到完成排序數組中。arr數組為待排序數組，res數組為排序完成數組。使用javaScript實現選擇排序代碼描述如下：
var arr=[9,1,4,13,7,8,20,23,15];
var wlen=arr.length;
var count=0;//記錄已完成排序元素數量
var res=[];//最終排序結果數組
var minvalue=0; //思路從未排序序列選擇最小元素放到已經完成排序的數組中
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實現基本冒泡與選擇排序算法描述如上所示，本例設計測試用例為（9,1,4,13,7,8,20,23,15），該待排序測試用例分別執行冒泡排序與選擇排序，效果展示如下圖
冒泡排序與選擇測試結果
本頭條號長期關注編程資訊分享；編程課程、素材、代碼分享及編程培訓。如果您對以上方面有興趣或代碼錯誤、建議與意見，可以聯系作者，共同探討。期待大家關注！本文分類類別：算法學習|javasScript編程。
@Author：Runsen」
插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。
一個有序的數組，我們往里面添加一個新的數據后，如何繼續保持數據有序呢？很簡單，我們只要遍歷數組，找到數據應該插入的位置將其插入即可。
圖片來自王爭算法專欄
通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。
插入排序在實現上，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
因此，代碼編寫需要判斷插入元素和當前元素的大小關系，遍歷時需要從數組的第二個數開始。
如果插入元素大于當前元素，則將待插入元素插入到當前元素的后一位。
如果插入元素小于當前元素，則將當前元素后移一位。直到找到一個當前元素小于插入元素。
因此，在for循環遍歷時，又有一個while內循環的條件，條件的內容是插入元素的索引減一和零進行對比。如果插入元素小于當前元素，同時對索引進行減一操作。如果出現了索引等于零的情況，那么表示插入元素等于當前元素。
下面是插入排序的具體Python代碼。
def insert_sort(a):
length = len(a)
if length <= 1:
return a
# 從數組的第二個數開始
for i in range(1, length):
# 從后向前掃描
j = i - 1
# value指的是插入元素
value = a[i]
while j >= 0:
if a[j] < value:
# 插入元素大于當前元素，則將待插入元素插入到當前元素的后一位
a[j + 1] = value
break
else:
# 插入元素小于當前元素，則將當前元素后移一位
a[j + 1] = a[j]
if j == 0:
a[j] = value
j -= 1
return a
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
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]
下面對Python代碼改為Java代碼。代碼來自菜鳥教程。
// 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; //初始值為待插入元素前一個元素的索引
for(int i= 1 ; i< arr.length;i++){
//i從第二個元素開始，默認第一個元素是有序的
//循環條件是小于數組長度，因為也要將最后一個元素插入到前面的序列
value = arr[i];
index = i - 1;//初始為前一個元素
while(index >=0 && value < arr[index]){
//需要保證index合法
//每當前面的元素比待插入元素大，就向后移動
arr[index + 1] = arr[index];
//不用怕覆蓋，因為value保存著待插入的值
index--;
}
//當退出循環，表明已經找到了待插入位置，即index + 1
arr[index + 1] = value;
}
System.out.println(Arrays.toString(arr));
}
}
下面對Python代碼改為JavaScript代碼。代碼來自菜鳥教程。
// 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;
}
對于不同的查找插入點方法（從頭到尾、從尾到頭），元素的比較次數是有區別的。但對于一個給定的初始序列，移動操作的次數總是固定的，就等于逆序度。
在插入排序中，對于值相同的元素，我們可以選擇將后面出現的元素，插入到前面出現元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩定的排序算法。
對于插入排序來說，每次插入操作都相當于在數組中插入一個數據，循環執行 n 次插入操作，所以平均時間復雜度為 O(n2)。
如果輸入數組已經是排好序的話，插入排序出現最佳情況，其運行時間是輸入規模的一個線性函數，其時間代價是O(n)。
如果輸入數組是逆序排列的，將出現最壞情況。平均情況與最壞情況一樣，其時間代價是 O(n2)。
參考：https://www.runoob.com/w3cnote/insertion-sort.html
選擇排序（Selection sort）是一種簡單直觀的排序算法。
選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素，將其放到已排序區間的末尾。
它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序：首先搜索整個列表，找到最小項的位置，如果該位置不是列表的第1項，就交換這兩個位置的元素。然后從列表的第2個元素開始，重復上述過程，直到算法達到整個過程的最后一個位置，圖形解釋如下
圖片來自王爭算法專欄
選擇排序還有一種代碼的形式是將最大值逐一選擇到后面，因此遍歷的時候需要逆序遍歷。
def selection_sort1(nums):
# 思路是將最小值逐一選擇到前面
n = len(nums)
# 第一層for表示循環選擇的遍數
for i in range(n - 1):
min_index = i # 記錄最小值的位置
# 第二層for表示最小元素和后面的元素逐個比較
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]
下面對Python代碼改為Java代碼。代碼來自菜鳥教程，選擇第一種思路。
下面對Python代碼改為JavaScript代碼。代碼來自菜鳥教程。
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;
}
選擇排序是一種不穩定的排序算法。選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩定性。
當出現幾個值相同的時候，比如 5，8，5，2，9這樣一組數據，使用選擇排序算法來排序的話，第一次找到最小元素 2，與第一個 5 交換位置，那第一個 5 和中間的 5 順序就變了，所以就不穩定了。
選擇排序的主要優點與數據移動有關。如果某個元素位于正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素。
它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換。
無論數列初始狀態怎樣，在第 i 趟排序中選出最小關鍵字的記錄，需做n-i次比較，因此，總的比較次數為：n(n-1)/2=O(n2)。
因此直接選擇排序的平均時間復雜度為 O(n2)。直接選擇排序是一個就地排序，空間復雜度為S(n)=O(1)。
參考：https://www.runoob.com/w3cnote/selection-sort.html
參考：極客時間王爭算法專欄
總結 來自極客時間王爭算法專欄
?
本文已收錄 GitHub，傳送門~[1] ，里面更有大廠面試完整考點，歡迎 Star。
?
[1]
傳送門~: https://github.com/MaoliRUNsen/runsenlearnpy100
冒泡排序是通過遍歷待排序的數列，一次比較兩個元素，根據大小調換位置，直到把最大的或最小的冒出來的排序方式。與選擇排序、插入排序是比較常見的排序方式，也非常好理解。
冒泡排序平均時間復雜度是：O(n^2)
1、先建立兩個循環，外循環用于遍歷整個數組，內循環遍歷待排序的區間。
2、內循環每次都從第一項開始，將該項與后項進行比較，再兩兩交換，一直到待排序結尾。
3、重復第二項，一直到數組遍歷完。
可以看成是用手捏住第一個位置，往右邊一個一個比較交換，把最大或最小的找出來，放在最后1位。然后再拿第一位置的數字，逐個比較，找出第二大的數字來放在倒數第2的位置。以此類推，把所有的數字都篩選一遍即可。
兩個循環，外循環是整個數列，內循環是數列減去已排好序的數列。
*請認真填寫需求信息，我們會在24小時內與您取得聯系。
