資訊專欄INFORMATION COLUMN
摘要：基本排序算法在計算機科學中，一個排序算法是一種能將一串數據依照特定的排列方式進行排列的一種算法。畢竟他們的效率都不太理想在實際應用中，應該選擇高級排序算法快速排序在隨機生成數據測試的時候，發現很多時候，插入排序要快于冒泡排序以及選擇排序。
基本排序算法
在計算機科學中，一個排序算法是一種能將一串數據依照特定的排列方式進行排列的一種算法。
這里簡單的介紹三種最基本的排序，分別是：冒泡排序、選擇排序以及插入排序
排序的過程中，經常要用到交換元素位置，故抽離為公共函數 swap。// 交換位置
export function swap(arr, index1, index2) {
var temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
冒泡排序
冒泡排序是最簡單的排序，一一對比相鄰的兩個數，順序不對就交換過來，這樣子，每一輪最大的值總會慢慢的被交換到最右側。所以才會叫冒泡排序
描述假設數組長度為 n
比較相鄰的兩個數，如果第 1 個大于第 2 個，就交換位置
重復第 1 步，一輪下來最大值被交換到第 n 個位置，也就是最右側
開啟新一輪，重復 1~2 步，最大值會被冒泡到第 n-1 個位置
重復上述步驟，直到所有都排序好
例子：對 3, 1, 5, 2, 4 進行排序
1,3,5,2,4 3 > 1 ,交換位置 1,3,5,2,4 3 < 5 ,不變 1,3,2,5,4 5 > 2 ,交換位置 1,3,2,4,5 5 > 4 ,交換位置,第一輪結束 1,3,2,4,5 1 < 3 ,不變 1,2,3,4,5 3 > 2 ,交換位置 1,2,3,4,5 ...依次對比 1,2,3,4,5 ... 1,2,3,4,5 ... 結束代碼實現
// 冒泡排序
export function bubbleSort(array) {
for (let i = array.length - 1; i >= 1; i--) {
let hasSwap = false;
for (let j = 0; j <= i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
hasSwap = true;
}
}
if (!hasSwap) {
// 這里用于優化，如果某一輪之后，沒有進行任何交換，說明已經排序完成了，所以退出循環
break;
}
}
}
效果演示
https://global.chen4342024.co...
注意打開開發者工具，切換到移動端模式小結
冒泡算法是比較慢的排序之一，也是最容易實現的算法之一。
穩定性：穩定
時間復雜度： 平均 O(n^2) 、 最壞 O(n^2) 、最好 O(n)
額外空間復雜度 O(1)
選擇排序選擇排序是指每一輪從數組中取出最小值，然后跟第一個元素交換位置。然后再找出第二個最小值，跟第二個元素交換位置，。。。以此類推。直到倒數第二個位置
例子對 3, 1, 5, 2, 4 進行排序
// 這里只展示每一輪的結果 3 1 5 2 4 //開始 1 3 5 2 4 //第 1 輪 1 2 5 3 4 //第 2 輪 1 2 3 5 4 //第 3 輪 1 2 3 4 5 //第 4 輪代碼實現
// 選擇排序從開頭開始，找出最小的值，放在第一個位置
// 有點類似打撲克拍的時候，抽取每一張最小的放在最左邊
export function selectSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
let min = array[i];
for (let j = i + 1; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
minIndex = j;
}
}
swap(array, i, minIndex);
}
}
效果演示
https://global.chen4342024.co...
注意打開開發者工具，切換到移動端模式
穩定性：不穩定
時間復雜度： O(n^2)
額外空間復雜度 O(1)
插入排序插入排序的思想是，依次從數組中未排序的部分，取出數據，然后插入到已排序的部分。直到清空未排序的部分
描述假設數組長度為 n , 從第 2 項開始
從第一個元素開始，該元素可以認為已經被排序；
取出下一個元素，在已經排序的元素序列中從后向前掃描；
如果該元素大于新元素，將該元素移到下一位置；
重復步驟 3，直到找到已排序的元素小于或者等于新元素的位置；
將新元素插入到該位置后；
重復步驟 2~5。
代碼實現export function insertSort(array) {
for (let i = 0; i < array.length; i++) {
let temp = array[i];
let j = i;
while (j > 0 && array[j - 1] > temp) {
// 將所有大于temp的往右移
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
}
效果演示
https://global.chen4342024.co...
注意打開開發者工具，切換到移動端模式
穩定性：穩定
時間復雜度：平均 O(n^2) 、 最壞 O(n^2) 、最好 O(n)
額外空間復雜度 O(1)
效果演示（匯總）https://global.chen4342024.co...
注意打開開發者工具，切換到移動端模式總結
這三種最基本的排序算法的復雜度非常相似，從理論上來說，它們的執行效率也應該差不多。
在實際使用中，如果需要排序的數據比較多，是不推薦使用這 3 種排序的。畢竟他們的效率都不太理想
在實際應用中，應該選擇高級排序算法： 快速排序 ...
在隨機生成數據測試的時候，發現很多時候，插入排序要快于冒泡排序以及選擇排序。大概是冒泡/選擇排序的快 1 倍
這是因為 插入排序需要比較的次數是 1+2+3+..+n = n * (n-1) /2,這是最壞的情況，大部分時候并不需要全部比較，所以平均下來只需要 n*(n-1)/4
而冒泡/選擇排序都需要n * (n-1)/2,所以平均下來，插入排序大概是冒泡/選擇排序的快 1 倍
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100206.html
摘要：介紹排序算法是算法中最常見的算法之一，我這里要介紹的是排序算法中的三種基本算法冒泡排序選擇排序插入排序，在文章的后面我會對三種算法的速度進行對比。 1.介紹 排序算法是算法中最常見的算法之一，我這里要介紹的是排序算法中的三種基本算法：冒泡排序、選擇排序、插入排序，在文章的后面我會對三種算法的速度進行對比。 2.冒泡排序 冒泡排序其名來源與其算法實現，會使得數組中的元素一個個從數組一端漂...
摘要：本篇主要實現九八大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序計數排序。希爾排序是非穩定排序算法。歸并排序算法依賴歸并操作。但是，計數排序可以用在基數排序算法中，能夠更有效的排序數據范圍很大的數組。 本篇主要實現九(八）大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序,計數排序。希望大家回顧知識的時候也能從我的這...
摘要：數據結構程序數據結構算法數據結構基本概念數據的邏輯結構反映數據元素之間的關系的數據元素集合的表示。這兩部分信息組成數據元素的存儲映象，稱為結點。 本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本數據結構和查找算法 本文主要是基礎的數據結構和算法概念，可能部分地方會涉及更高級的算法和算法，具體內容以...
摘要：基本排序算法總結前言隨著的興起將推向的一個前所未有的高度作為為建立高性能的服務端而創建的運行平臺隨著時間的推移和生態鏈的完善已經不再局部于服務端包括前端后端桌面這篇文章介紹的傳統的散打排序方法并用實現其功能如有需要可以對其封裝在隨后會介紹高 基本排序算法總結 前言 隨著node的興起, 將javascript推向的一個前所未有的高度, node作為為建立高性能的服務端而創建的js運行平...
摘要：由于排序的算法有很多，在本次算法系列的分享當中，我們先從簡單易上手的選擇排序法開始，其它的排序算法會隨后陸續跟大家一起分享。 HTML5學堂-碼匠：數據快速的計算與排序，與前端頁面性能有直接的關系。由于排序的算法有很多，在本次算法系列的分享當中，我們先從簡單易上手的選擇排序法開始，其它的排序算法會隨后陸續跟大家一起分享。 算法的基本概念 算法是什么，它有何作用 為解決一個問題而采取的方...
閱讀 3083·2023-04-26 00:53
閱讀 3534·2021-11-19 09:58
閱讀 1696·2021-09-29 09:35
閱讀 3286·2021-09-28 09:46
閱讀 3866·2021-09-22 15:38
閱讀 2696·2019-08-30 15:55
閱讀 3014·2019-08-23 14:10
閱讀 3828·2019-08-22 18:17
