算法性能：快速排序最好情況下時(shí)間復(fù)雜度為O(nlogn)，待排序列越接近無序，則該算法效率越高，在最壞情況下時(shí)間復(fù)雜度為O(n*n)，待排序列越接近有序，則該算法效率越低，算法的平均時(shí)間復(fù)雜度為O(nlogn)。就平均時(shí)間而言，快速排序是所有排序算法中最好的。該算法的空間復(fù)雜度為O(logn)，快速排序是遞歸進(jìn)行的，需要棧的輔助，因此需要的輔助空間比前面幾類排序方法要多。
快速排序的效率和選取的“樞軸”有關(guān)，選取的樞軸越接近中間值，算法效率就越高，因此為了提高算法效率，可以在第一次選取“樞軸”時(shí)做文章，如在數(shù)據(jù)堆中隨機(jī)選取3個(gè)值，取3個(gè)值的平均值作為“樞軸”，就如抽樣一般。關(guān)于具體如何提高快速排序算法的效率，在本文不做詳細(xì)介紹了，點(diǎn)到為止。（感興趣的讀者可以自行去研究）
選擇排序
算法思想：該算法的主要?jiǎng)幼骶褪?ldquo;選擇”，采用簡單的選擇方式，從頭至尾順序掃描序列，找出最小的一個(gè)記錄，和第一個(gè)記錄交換，接著從剩下的記錄中繼續(xù)這種選擇和交換，最終使序列有序。
- //選擇排序
- Array.prototype.selectionSort = function() {
- for (var i = 0; i < this.length; ++i)
- {
- var index = i;
- for (var j = i + 1; j < this.length; ++j)
- {
- if (this[j] < this[index])
- index = j;
- }
- this.swap(i, index);
- }
- }
算法性能：將最內(nèi)層循環(huán)中的比較視為基本操作，其執(zhí)行次數(shù)為(n-1+1)*(n-1)/2=n(n-1)/2，其時(shí)間復(fù)雜度為O(n*n)，本算法的額外空間只有一個(gè)temp，因此空間復(fù)雜度為O(1)。
堆排序
算法思想：堆是一種數(shù)據(jù)結(jié)構(gòu)，最好的理解堆的方式就是把堆看成一棵完全二叉樹，這個(gè)完全二叉樹滿足任何一個(gè)非葉節(jié)點(diǎn)的值，都不大于（或不小于）其左右孩子節(jié)點(diǎn)的值。若父親大孩子小，則這樣的堆叫做大頂堆；若父親小孩子大，這樣的堆叫做小頂堆。根據(jù)堆的定義，其根節(jié)點(diǎn)的值是最大（或最?。虼藢⒁粋€(gè)無序序列調(diào)整為一個(gè)堆，就可以找出這個(gè)序列的最大（或最?。┲?，然后將找出的這個(gè)值交換到序列的最后（或最前），這樣有序序列元素增加1個(gè)，無序序列中元素減少1個(gè)，對新的無序序列重復(fù)這樣的操作，就實(shí)現(xiàn)了序列排序。堆排序中最關(guān)鍵的操作是將序列調(diào)整為堆，整個(gè)排序的過程就是通過不斷調(diào)整使得不符合堆定義的完全二叉樹變?yōu)榉隙讯x的完全二叉樹的過程。
堆排序執(zhí)行過程（大頂堆）：
（1）從無序序列所確定的完全二叉樹的第一個(gè)非葉子節(jié)點(diǎn)開始，從右至左，從下至上，對每個(gè)節(jié)點(diǎn)進(jìn)行調(diào)整，最終將得到一個(gè)大頂堆。將當(dāng)前節(jié)點(diǎn)（a）的值與其孩子節(jié)點(diǎn)進(jìn)行比較，如果存在大于a值的孩子節(jié)點(diǎn)，則從中選出最大的一個(gè)與a交換。當(dāng)a來到下一層的時(shí)候重復(fù)上述過程，直到a的孩子節(jié)點(diǎn)值都小于a的值為止。
（2）將當(dāng)前無序序列中第一個(gè)元素，在樹中是根節(jié)點(diǎn)（a）與無序序列中最后一個(gè)元素（b）交換。a進(jìn)入有序序列，到達(dá)最終位置，無序序列中元素減少1個(gè)，有序序列中元素增加1個(gè)，此時(shí)只有節(jié)點(diǎn)b可能不滿足堆的定義，對其進(jìn)行調(diào)整。