當前位置:成語大全網 - 新華字典 - 平臺行業詞雲分析中有哪幾種排序方式

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

常見的幾種算法:

①冒泡算法

②選擇排序

③插入排序

④快速排序件

認證

開源

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

搜索

登錄/註冊

會員中心

收藏

動態

創作

常見的幾種排序方法

從零開始學前端 於 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 的後面;

排序方式:

內排序:所有排序操作都在內存中完成,占用常數內存,不占用額外內存。

外排序:由於數據太大,因此把數據放在磁盤中,而排序通過磁盤和內存的數據傳輸才能進行,占用額外內存。

復雜度:

時間復雜度: 壹個算法執行所耗費的時間。

空間復雜度: 運行完壹個程序所需內存的大小。