快速排序

一、排序是什

排序說白了其實就是對一個無序的列表中的所有元素按順序排列。

二、快速排序

快速排序其實是交換排序的一種，而交換排序也就是根據(jù)那個待排序列中兩個關鍵字的比較結果，來對換他們兩個在序列中的位置。

三、快速排序思想

假如從小到大排序...

1. 在待排序的列表中選定一個元素，將這個元素作為此次排序的樞紐。正常來講這個樞紐選首元素就好。
2. 然后通過遍歷，對待排序的所有元素與此次遍歷的樞紐做比較，將比這個樞紐小的元素放在左側，比這個樞紐大的元素放在它的右側。
3. 經(jīng)過一次排序，此次排序的樞紐就已經(jīng)確定了它的最終位置，此后不用在改變了。
4. 同時在一次排序后，將此次執(zhí)行的待排序列分成了兩個新的待排序列，通過遞歸，分別對這兩個待排序列作為新的執(zhí)行待排序列進行前幾步。
5. 當遞歸完成時，每一個元素都在它的最終位置了，快速排序結束。

四、算法性能

• 當初始序列越接近有序，導致算法的遞歸層數(shù)越高，也就是執(zhí)行次數(shù)越多，性能越差，
• 完全有序時最差，時間復雜度為為O(n*n)，空間復雜度為O(n)
• 反之性能最好，時間復雜度為O(n*log2(n))，空間復雜度為O(log2(n))

五、代碼實現(xiàn)

?function quickSort(arr) {
???if (arr.length <= 1) return arr;
???const pivot = arr[0];
???const low = [],high = []; 
???for (let i = 1; i < arr.length; i++) {
?????if (arr[i] < pivot) {
???????low.push(arr[i]);
????} else {
???????high.push(arr[i]);
????}
??}
???return quickSort(low).concat(pivot, quickSort(high));
?}