資訊專欄INFORMATION COLUMN
摘要：介紹排序算法是算法中最常見的算法之一，我這里要介紹的是排序算法中的三種基本算法冒泡排序選擇排序插入排序，在文章的后面我會對三種算法的速度進行對比。
1.介紹
排序算法是算法中最常見的算法之一，我這里要介紹的是排序算法中的三種基本算法：冒泡排序、選擇排序、插入排序，在文章的后面我會對三種算法的速度進行對比。
2.冒泡排序冒泡排序其名來源與其算法實現(xiàn)，會使得數(shù)組中的元素一個個從數(shù)組一端漂到另一端而故這樣命名。下面我們實現(xiàn)的是對數(shù)組就行升序排列的冒泡：
function bubbleSort(arr){
if(!arr instanceof Array){
return;
}
if(arr.length == 0 || arr.length == 1){
return arr;
}
for(let outer = arr.length; outer >= 2; outer--){
for(let inner = 0; inner <= outer - 1; inner++){
if(arr[inner] > arr[inner + 1]){
let temp = arr[inner];
arr[inner] = arr[inner + 1];
arr[inner + 1] = temp;
}
}
}
return arr;
}
3.選擇排序
選擇排序我們也需要用到嵌套循環(huán)，算法思路如下：
從數(shù)組的第一個元素開始，將第一個元素逐個與其他元素比較，檢查完所有元素后，最小的元素會放到最前面。然后從第二個元素繼續(xù)，重復這一過程，直到進行到數(shù)組倒數(shù)第二個元素，排序并完成了。
外循環(huán)從數(shù)組的第一個元素移動到倒數(shù)第二個元素； 內(nèi)循環(huán)從第二個數(shù)組元素移動到最后一個元素， 查找比當前外循環(huán)所指向的元素小的元素。 每次內(nèi)循環(huán)迭代后， 數(shù)組中最小的值都會被賦值到合適的位置。
function selectionSort(arr){
if(!arr instanceof Array){
return;
}
if(arr.length == 0 || arr.length == 1){
return arr;
}
let min;
for(let outer = 0; outer <= arr.length - 2; outer++){
min = outer;
for(let inner = outer + 1; inner <= arr.length - 1; inner++){
if(arr[inner] < arr[min]){
min = inner;
}
}
let temp = arr[outer];
arr[outer] = arr[min];
arr[min] = temp;
}
return arr;
}
4.插入排序
插入排序有兩個循環(huán)。 外循環(huán)將數(shù)組元素挨個移動， 而內(nèi)循環(huán)則對外循環(huán)中選中的元素及它后面的那個元素進行比較。 如果外循環(huán)中選中的元素比內(nèi)循環(huán)中選中的元素小， 那么數(shù)組元素會向右移動， 為內(nèi)循環(huán)中的這個元素騰出位置。
function insertionSort(arr){
if(!arr instanceof Array){
return;
}
if(arr.length == 0 || arr.length == 1){
return arr;
}
let temp,inner;
for(let outer = 0; outer < arr.length; outer++){
temp = arr[outer];
inner = outer;
while(inner > 0 && (arr[inner - 1] >= temp)){
arr[inner] = arr[inner - 1];
--inner;
}
arr[inner] = temp;
}
return arr;
}
5.三種排序算法速度的比較
首先我們實現(xiàn)一個生成隨機數(shù)組的函數(shù)：
function createArr(n){
let arr = [];
if(typeof n !== "number"){
return;
}
if(n === 0){
return arr;
}
for(let i = 0; i < n ; i++){
arr[i] = Math.floor(Math.random() * (n + 1));
}
return arr;
}
我們通過獲取當前的時間戳和運行算法后時間戳進行對比來比較，主要比較數(shù)組的大小為100， 1000， 10000時來觀察三種算法。
//數(shù)組為100的情況
let arr = createArr(100);
let start = Date.now();
bubbleSort(arr);
let stop = Date.now();
cosnole.log(`冒泡排序用時${stop - start}`);
start = Date.now();
selectionSort(arr);
stop = Date.now();
cosnole.log(`選擇排序用時${stop - start}`);
start = Date.now();
insertionSort(arr);
stop = Date.now();
cosnole.log(`插入排序用時${stop - start}`);
最后得出的結果為
說明數(shù)組大小為100時，三種排序算法速度之間沒有什么太大的差別。
我把數(shù)組擴大為1000得到的結果如下：
現(xiàn)在我們可以看到選擇排序和插入排序比冒泡排序都快了很多。
接著我把數(shù)據(jù)增大為10000，得到的結果為：
現(xiàn)在我們可以很明顯的看出三種排序算法的速度誰快誰慢了，特別是我們處理比較大的數(shù)據(jù)時，對算法的選擇影響到程序的性能。
文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/85212.html
摘要：今天再來看看另外三種時間復雜度都是的排序算法，分別是希爾排序歸并排序和快速排序。三數(shù)取中法求將放到數(shù)組的末尾總結這三種排序算法的平均時間復雜度都是，歸并排序和快速排序的應用更廣泛。 1. 回顧 前面說完了三種較為簡單的排序算法，分別是冒泡排序，選擇排序和插入排序，它們的平均情況時間復雜度都是 O(n2)，比較的高，適合小規(guī)模的數(shù)據(jù)排序，其中插入排序的效率稍高，所以更推薦使用插入排序。今...
摘要：實現(xiàn)數(shù)組排序的算法很多其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數(shù)進行比較按照排序的條件進行互換例如對數(shù)值從小到大排序隨著不斷的互換最大的那個值會慢慢冒泡到數(shù)組的末端基于這個原理我們就可以寫冒泡排序了為了簡單起見下面的例子都是對數(shù)值 實現(xiàn)數(shù)組排序的算法很多,其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數(shù)進行比較,按照排序的條件進行互換,例如對數(shù)值從小到大排序,隨著不斷的互...
摘要：實現(xiàn)數(shù)組排序的算法很多其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數(shù)進行比較按照排序的條件進行互換例如對數(shù)值從小到大排序隨著不斷的互換最大的那個值會慢慢冒泡到數(shù)組的末端基于這個原理我們就可以寫冒泡排序了為了簡單起見下面的例子都是對數(shù)值 實現(xiàn)數(shù)組排序的算法很多,其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數(shù)進行比較,按照排序的條件進行互換,例如對數(shù)值從小到大排序,隨著不斷的互...
摘要：實現(xiàn)數(shù)組排序的算法很多其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數(shù)進行比較按照排序的條件進行互換例如對數(shù)值從小到大排序隨著不斷的互換最大的那個值會慢慢冒泡到數(shù)組的末端基于這個原理我們就可以寫冒泡排序了為了簡單起見下面的例子都是對數(shù)值 實現(xiàn)數(shù)組排序的算法很多,其中冒泡算法是比較簡單的冒泡的基本原理是相鄰的兩個數(shù)進行比較,按照排序的條件進行互換,例如對數(shù)值從小到大排序,隨著不斷的互...
閱讀 3027·2023-04-26 00:32
閱讀 511·2019-08-30 15:52
閱讀 2118·2019-08-30 15:52
閱讀 3363·2019-08-30 15:44
閱讀 3292·2019-08-30 14:09
閱讀 1425·2019-08-29 15:15
閱讀 3404·2019-08-28 18:12
閱讀 1088·2019-08-26 13:55
