當前位置:首頁 » 網頁前端 » 前端詞雲抖動
擴展閱讀
宜搜離線緩存怎麼設置 2022-08-20 04:18:27
sql15247 2022-08-20 04:18:09
存儲卡滑動 2022-08-20 04:15:03

前端詞雲抖動

發布時間: 2022-06-27 17:22:46

⑴ 平台行業詞雲分析中有哪幾種排序方式

常見的幾種演算法:
①冒泡演算法
②選擇排序
③插入排序
④快速排序件
認證
開源

平台行業詞雲分析中有哪幾種排序方式
搜索
登錄/注冊
會員中心
收藏
動態
創作
常見的幾種排序方法

從零開始學前端 於 2019-06-01 09:34:54 發布 4965 收藏
分類專欄: 從零開始學前端
版權

從零開始學前端
專欄收錄該內容
198 篇文章2 訂閱
訂閱專欄
【常見的幾種排序方法】

1.背景介紹

在計算機科學與數學中,一個排序演算法(英語:Sorting algorithm)是一種能將一串資料依照特定排序方式進行排列的一種演算法。 最常用到的排序方式是數值順序以及字典順序。有效的排序演算法在一些演算法(例如搜尋演算法與合並演算法)中是重要的, 如此這些演算法才能得到正確解答。 排序演算法也用在處理文字資料以及產生人類可讀的輸出結果。 基本上,排序演算法的輸出必須遵守下列兩個原則:
輸出結果為遞增序列(遞增是針對所需的排序順序而言)
輸出結果是原輸入的一種排列、或是重組
雖然排序演算法是一個簡單的問題,但是從計算機科學發展以來,在此問題上已經有大量的研究。 更多的新演算法仍在不斷的被發明。

2.知識剖析

查找和排序演算法是演算法的入門知識,其經典思想可以用於很多演算法當中。因為其實現代碼較短,應用較常見。 所以在面試中經常會問到排序演算法及其相關的問題。但萬變不離其宗,只要熟悉了思想,靈活運用也不是難事。 一般在面試中最常考的是快速排序和歸並排序,並且經常有面試官要求現場寫出這兩種排序的代碼。 對這兩種排序的代碼一定要信手拈來才行。還有插入排序、冒泡排序、堆排序、基數排序、桶排序等。
常見的幾種演算法:
①冒泡演算法
②選擇排序
③插入排序
④快速排序

常見問題

問題一:各種排序演算法用JavaScript 如何實現?
問題二:各種排序演算法的優劣及其應用?
解決方案
問題一:各種排序演算法用JavaScript 如何實現?
問題二:各種排序演算法的優劣及其應用?

解決方案、

冒泡排序
冒泡排序(英語:Bubble Sort)是一種簡單的排序演算法。它重復地走訪過要排序的數列,一次比較兩個元素, 如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有元素再需要交換, 也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。
冒泡排序演演算法的運作如下:
比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數。
針對所有的元素重復以上的步驟,除了最後一個。
持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較。
代碼實現:

Array.prototype.bubbleSort = function () {undefined
var i, j, temp;
for (i = 0; i < this.length - 1; i++)
for (j = 0; j < this.length - 1 - i; j++)
if (this[j] > this[j + 1]) {undefined
temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
}
return this;
};

var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];//定義一個數組
num.bubbleSort();//數組調用冒泡排序演算法

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素, 然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。 選擇排序的思想其實和冒泡排序有點類似,都是在一次排序後把最小的元素放到最前面。但是過程不同, 冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇。

Array.prototype.selectionSort = function() {undefined
var i, j, min;
var temp;
for (i = 0; i < this.length - 1; i++) {undefined
min = i;
for (j = i + 1; j < this.length; j++)
if (this[min] > this[j])
min = j;
temp = this[min];
this[min] = this[i];
this[i] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數組
num.selectionSort(); //數組定義選擇排序演算法

插入排序(英語:Insertion Sort)是一種簡單直觀的排序演算法。它的 工作原理是通過構建有序序列,對於未排序數據, 在已排序序列中從後向前掃描,找到相應位置並插入。插入排序在實現上,通常採用in-place排序 (即只需用到O(1)的額外空間的排序),因而在從後向前掃描過程中,需要反復把已排序元素逐步向後挪位, 為最新元素提供插入空間。
從第一個元素開始,該元素可以認為已經被排序
取出下一個元素,在已經排序的元素序列中從後向前掃描
如果該元素(已排序)大於新元素,將該元素移到下一位置
將新元素插入到該位置後

Array.prototype.insertionSort = function () {undefined
for (var i = 1; i < this.length; i++) {undefined
var temp = this[i];
var j = i - 1;
//如果將賦值放到下一行的for循環內, 會導致在第13行出現j未聲明的錯誤
for (; j >= 0 && this[j] > temp; j–) {undefined
this[j + 1] = this[j];
}
this[j + 1] = temp;
}
return this;
}
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數組

num.insertionSort(); //數組調用插入排序演算法

快速排序
快速排序(英語:Quicksort),又稱劃分交換排序(partition-exchange sort), 一種排序演算法, 最早由東尼·霍爾提出。在平均狀況下,排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較, 但這種狀況並不常見。事實上,快速排序通常明顯比其他Ο(n log n)演演算法更快, 因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來。 快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為兩個子序列(sub-lists)。
步驟為:
從數列中挑出一個元素,稱為"基準"(pivot),
重新排序數列,所有比基準值小的元素擺放在基準前面,所有比基準值大的元素擺在基準後面(相同的數可以到任一邊)。在這個分割結束之後,該基準就處於數列的中間位置。這個稱為分割(partition)操作。
遞歸地(recursively)把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸到最底部時,數列的大小是零或一,也就是已經排序好了。這個演演算法一定會結束,因為在每次的迭代(iteration)中,它至少會把一個元素擺到它最後的位置去。

Array.prototype.quickSort = function () {undefined
var len = this.length;
if (len <= 1)
return this.slice(0);
var left = [];
var right = [];
var mid = [this[0]];
for (var i = 1; i < len; i++)
if (this[i] < mid[0])
left.push(this[i]);
else
right.push(this[i]);
return left.quickSort().concat(mid.concat(right.quickSort()));
};

var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quickSort();

編碼實戰

擴展思考

各種排序演算法的時間復雜度和空間復雜度
演算法優劣評價術語
穩定性:
穩定:如果 a 原本在 b 前面,而 a = b,排序之後 a 仍然在 b 的前面;
不穩定:如果 a 原本在 b 的前面,而 a = b,排序之後 a 可能會出現在 b 的後面;
排序方式:
內排序:所有排序操作都在內存中完成,佔用常數內存,不佔用額外內存。
外排序:由於數據太大,因此把數據放在磁碟中,而排序通過磁碟和內存的數據傳輸才能進行,佔用額外內存。
復雜度:
時間復雜度: 一個演算法執行所耗費的時間。
空間復雜度: 運行完一個程序所需內存的大小。