js快速排序演算法
⑴ JS實現隨機化快速排序的實例代碼
演算法的平均時間復雜度為O(nlogn)。但是當輸入是已經排序的數組或幾乎排好序的輸入，時間復雜度卻為O(n^2)。為解決這一問題並保證平均時間復雜度為O(nlogn)的方法是引入預處理步驟，它惟一的目的是改變元素的順序使之隨機排序。這種預處理步驟可在O(n)時間內運行。能夠起到同樣作用的另一種簡單方法是在演算法中引入一個隨機元素，這可以通過隨機地選擇拆分元素的主元來實現。隨機選擇主元的結果放寬了關於輸入元素的所有排列的可能性相同的步驟。引入這一步來修正原先的快速排序，可得到下面所示的隨機化快速排序。新演算法只是在區間[low…high]中一致隨機地選擇一個索引v，並將A[v]和A[low]交換，然後按照原來的快速排序演算法繼續。這里，parseInt(Math.random()*(high-low+1)
+
low)返回一個在low和high之間的數。
復制代碼
代碼如下:
/****************************************
演算法：split
輸入：數組A[low...high]
輸出：
1.若有必要，輸出按上述描述的重新排列的數組A;
2.劃分元素A[low]的新位置w;
****************************************/
function
split(array,
low,
high)
{
var
i
=
low;
var
x
=
array[low];
for(var
j
=
low
+
1;
j
<=
high;
j++)
{
if(array[j]
<=
x)
{
i
++;
if(i
!=
j)
{
var
temp
=
array[i];
array[i]
=
array[j];
array[j]
=
temp;
}
}
}
temp
=
array[low];
array[low]
=
array[i];
array[i]
=
temp;
return
i;
}
/****************************************
演算法：rquicksort
輸入：A[0...n-1]
輸出：按非降序排列數組A[0...n-1]
rquicksort(A,
0,
n-1);
****************************************/
function
rquicksort(array,
low,
high)
{
if(low
<
high)
{
/******隨機化拆分元素的主元*******/
var
v
=
parseInt(Math.random()*(high-low+1)
+
low);
var
tmp
=
array[low];
array[low]
=
array[v];
array[v]
=
tmp;
/******隨機化拆分元素的主元*******/
var
w
=
split(array,
low,
high);
rquicksort(array,
low,
w
-1);
rquicksort(array,
w
+1,
high);
return
array;
}
}
var
array
=
[33,
22,
11,
88,
23,
32];
array
=
rquicksort(array,
0,
array.length-1);
console.log(array);
⑵ 快速排序的原理是什麼
先
數據序列
選
元素,並
序列
所
比該元素
元素都放
右邊或左邊,再
左右兩邊
別用同
處
直
每
待處理
序列
度
1,
處理結束
前
序區R[1..H]
任取
數據元素作
比較
"基準"(
妨記
X)
用
基準
前
序區劃
左右兩
較
序區：R[1..I-1]
R[I+1..H]
且左邊
序
區
數據元素均
於等於基準元素
右邊
序
區
數據元素均
於等於基準元素
基準X則位於
終排序
位置
即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)
R[1..I-1]
R[I+1..H]均非空
別
進行
述
劃
程
直至所
序
區
數據元素均已排序
止
快速排序
基本思想
基於
治策略
於輸入
序列L[p..r]
規模足夠
則直接進行排序（比
用前述
冒泡、選擇、插入排序均
）
否則
三步處理：
解(Divide)：
待排序列L[p..r]劃
兩
非空
序列L[p..q]
L[q+1..r]
使L[p..q]
任
元素
值
於L[q+1..r]
任
元素
值
具體
通
途徑實現：
序列L[p..r]
選擇數據元素L[q]
經比較
移
L[q]
處於L[p..r]
間
適
位置
使
數據元素L[q]
值
於L[q+1..r]
任
元素
值
遞歸求解(Conquer)：通
遞歸調用快速排序算
別
L[p..q]
L[q+1..r]進行排序
合並(Merge)：由於
解
兩
序列
排序
進行
所
L[p..q]
L[q+1..r]都排
序
需要執行任何計算L[p..r]
已排
序
即自
合並
解決流程
符合
治
基本步驟
快速排序
治
經典應用實例
⑶ 快速排序法的平均時間復雜度和最壞時間復雜度分別是多少
快速排序的平均時間復雜度和最壞時間復雜度分別是O(nlgn)、O(n^2)。
當排序已經成為基本有序狀態時，快速排序退化為O(n^2)，一般情況下，排序為指數復雜度。
快速排序最差情況遞歸調用棧高度O(n)，平均情況遞歸調用棧高度O(logn)，而不管哪種情況棧的每一層處理時間都是O(n)，所以，平均情況（最佳情況也是平均情況）的時間復雜度O(nlogn)，最差情況的時間復雜度為O(n^2)。
(3)js快速排序演算法擴展閱讀
快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序，它採用了一種分治的策略，通常稱其為分治法。快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：
（1）首先設定一個分界值，通過該分界值將數組分成左右兩部分。
（2）將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。
（3）然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
（4）重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。
⑷ JS中的各種排序方法
數據結構演算法中排序有很多種，常見的、不常見的，至少包含十種以上。根據它們的特性，可以大致分為兩種類型：比較類排序和非比較類排序
冒泡排序是一次比較兩個元素，如果順序是錯誤的就把它們交換過來。，直到不需要再交換
快速排序的基本思想是通過一趟排序，將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可以分別對這兩部分記錄繼續進行排序，以達到整個序列有序
從數列中挑出一個元素，稱為 「基準」（pivot）；然後重新排序數列，所有元素比基準值小的擺放在基準前面、比基準值大的擺在基準的後面；在這個區分搞定之後，該基準就處於數列的中間位置；然後把小於基準值元素的子數列（left）和大於基準值元素的子數列（right）遞歸地調用 quick 方法排序完成，這就是快排的思路
通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入，從而達到排序的效果
插入排序的思路是基於數組本身進行調整的，首先循環遍歷從 i 等於 1 開始，拿到當前的 current 的值，去和前面的值比較，如果前面的大於當前的值，就把前面的值和當前的那個值進行交換，通過這樣不斷循環達到了排序的目的
將最小的元素存放在序列的起始位置，再從剩餘未排序元素中繼續尋找最小元素，然後放到已排序的序列後面……以此類推，直到所有元素均排序完畢
堆排序是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質，即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆的底層實際上就是一棵完全二叉樹，可以用數組實現
歸並排序是建立在歸並操作上的一種有效的排序演算法，該演算法是採用分治法的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並
通過 mid 可以把該數組分成左右兩個數組，分別對這兩個進行遞歸調用排序方法，最後將兩個數組按照順序歸並起來