DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> 關於JavaScript >> JavaScript實現in-place思想的快速排序方法
JavaScript實現in-place思想的快速排序方法
編輯:關於JavaScript     

快速排序,又稱劃分交換排序。以分治法為策略實現的快速排序算法。

本文主要要談的是利用javascript實現in-place思想的快速排序

分治法:

在計算機科學中,分治法是建基於多項分支遞歸的一種很重要的算法范式。字面上的解釋是“分而治之”,就是把一個復雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合並。(摘自維基百科)

快速排序的思想

數組中指定一個元素作為標尺,比它大的放到該元素後面,比它小的放到該元素前面,如此重復直至全部正序排列。

快速排序分三步:

選基准:在數據結構中選擇一個元素作為基准(pivot)

劃分區:參照基准元素值的大小,劃分無序區,所有小於基准元素的數據放入一個區間,所有大於基准元素的數據放入另一區間,分區操作結束後,基准元素所處的位置就是最終排序後它應該所處的位置

遞歸:對初次劃分出來的兩個無序區間,遞歸調用第 1步和第 2步的算法,直到所有無序區間都只剩下一個元素為止。

現在先說說普遍的實現方法(沒有用到原地算法)

function quickSort(arr) {
if (arr.length <= 1) return ;
//取數組最接近中間的數位基准,奇數與偶數取值不同,但不印象,當然,你可以選取第一個,或者最後一個數為基准,這裡不作過多描述
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
//左右區間,用於存放排序後的數
var left = [];
var right = [];
console.log('基准為:' + pivot + ' 時');
for (var i = 0; i < arr.length; i++) {
console.log('分區操作的第 ' + (i + 1) + ' 次循環:');
//小於基准,放於左區間,大於基准,放於右區間
if (arr[i] < pivot) {
left.push(arr[i]);
console.log('左邊:' + (arr[i]))
} else {
right.push(arr[i]);
console.log('右邊:' + (arr[i]))
}
}
//這裡使用concat操作符,將左區間,基准,右區間拼接為一個新數組
//然後遞歸1,2步驟,直至所有無序區間都 只剩下一個元素 ,遞歸結束
return quickSort(left).concat([pivot], quickSort(right));
}
var arr = [14, 3, 15, 7, 2, 76, 11];
console.log(quickSort(arr));
/*
* 基准為7時,第一次分區得到左右兩個子集[ 3, 2,] 7 [14, 15, 76, 11];
* 以基准為2,對左邊的子集[3,2]進行劃分區排序,得到[2] 3。左子集排序全部結束
* 以基准為76,對右邊的子集進行劃分區排序,得到[14, 15, 11] 76
* 此時對上面的[14, 15, 11]以基准為15再進行劃分區排序, [14, 11] 15
* 此時對上面的[14, 11]以基准為11再進行劃分區排序, 11 [14]
* 所有無序區間都只剩下一個元素,遞歸結束
*
*/

通過斷點調試,可得出結果。

弊端:

它需要Ω(n)的額外存儲空間,跟歸並排序一樣不好。在生產環境中,需要額外的內存空間,影響性能。

同時,很多人認為上邊的就是真正的快速排序了。 所以,在下面,很有必要的推薦in-place算法的快速排序

有關於原地算法可參考維基百科,被牆的同學,百度也差不多。

in-place

快速排序一般是用遞歸實現,最關鍵是partition分割函數,它將數組劃分為兩部分,一部分小於pivot,另一部分大於pivot。具體原理上邊提過

function quickSort(arr) {
// 交換
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// 分區
function partition(arr, left, right) {
/**
* 開始時不知最終pivot的存放位置,可以先將pivot交換到後面去
* 這裡直接定義最右邊的元素為基准
*/
var pivot = arr[right];
/**
* 存放小於pivot的元素時,是緊挨著上一元素的,否則空隙裡存放的可能是大於pivot的元素,
* 故聲明一個storeIndex變量,並初始化為left來依次緊挨著存放小於pivot的元素。
*/
var storeIndex = left;
for (var i = left; i < right; i++) {
if (arr[i] < pivot) {
/**
* 遍歷數組,找到小於的pivot的元素,(大於pivot的元素會跳過)
* 將循環i次時得到的元素,通過swap交換放到storeIndex處,
* 並對storeIndex遞增1,表示下一個可能要交換的位置
*/
swap(arr, storeIndex, i);
storeIndex++;
}
}
// 最後: 將pivot交換到storeIndex處,基准元素放置到最終正確位置上
swap(arr, right, storeIndex);
return storeIndex;
}
function sort(arr, left, right) {
if (left > right) return;
var storeIndex = partition(arr, left, right);
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
sort(arr, 0, arr.length - 1);
return arr;
}
console.log(quickSort([8, 4, 90, 8, 34, 67, 1, 26, 17]));

分區的優化

這裡細心的同學可能會提出,選取不同的基准時,是否會有不同性能表現,答案是肯定的,但,因為,我是搞前端的,對算法不是很了解,所以,這個坑留給厲害的人來填補。

復雜度

快速排序是排序速度最快的算法,它的時間復雜度是O(log n)

在平均狀況下,排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較.

https://github.com/LYZ0106/

以上所述是小編給大家介紹的JavaScript實現in-place思想的快速排序方法,希望對大家有所幫助,如果大家有任何疑問歡迎給我留言,小編會及時回復大家的,在此也非常感謝大家對網站的支持!

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved