前面說到了三種簡單的排序和歸并排序叹坦，今天中午就開始來談一談我理解的快速排序熊镣。快速排序是前面冒泡排序的一個改進版本立由，我們在學習的時候可以對照兩個來進行學習
一轧钓、 首先來個簡單的需求
首先我們在了解快排之前，我們先來完成這樣一個需求：在一個無序數(shù)組中隨機選定一個值為基點锐膜，將數(shù)組的根據(jù)該基點進行排序毕箍，將比基點小的元素放在基點的左邊，比基點大的元素放在基點的右邊道盏。
具體的操作如下：
1.1而柑、 初始化數(shù)組和指針
假定我們得到這樣一個數(shù)組：
| 序列號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 5 | 4 | 9 | 1 | 7 | 6 | 2 |
| 指針 | i?? | j?? |
temp=5
如上表格所示，給定一個無序數(shù)組荷逞，然后再給定兩個指針i媒咳、j，分別將指針i种远，j撥向數(shù)組的首尾位置涩澡。然后再設(shè)置一個變量temp用來存儲數(shù)組中的第一個元素5。也就是說將temp定義成我們前面的基點坠敷。
1.2妙同、撥動指針
1> 首先我們先撥動指針j，從數(shù)組的末端開始查找 直到找到一個比temp要小的元素膝迎，找到之后將該值賦值給數(shù)組的首位粥帚。
| 序列號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 2 | 4 | 9 | 1 | 7 | 6 | 2 |
| 指針 | i?? | j?? |
temp=5
2> 然后再撥動指針i，從數(shù)組的開頭開始查找限次，直到找到一個比temp要大的元素位置芒涡，并且將該值賦值給上面查到的數(shù)組位置。
| 序列號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 2 | 4 | 9 | 1 | 7 | 6 | 9 |
| 指針 | i?? | j?? |
temp=5
3> 重復(fù)上面兩步操作，直到兩指針指向同一個元素
| 序列號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 2 | 4 | 1 | 1 | 7 | 6 | 9 |
| 指針 | ij?? |
temp=5
1.3费尽、賦值
最后將temp賦值給指針i赠群，j指向的位置，此時左邊的元素肯定比該元素要小依啰，右邊的肯定比該元素要大乎串，就滿足了前面說的需求了店枣。
| 序列號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | 2 | 4 | 1 | 5 | 7 | 6 | 9 |
| 指針 | ij?? |
temp=5
1.3速警、詳細的代碼如下：
function partition(arr,left,right){
let temp = arr[left];
while(left<right){
// 從右邊開始查找
while(left<right&&arr[right]>=temp) right--;
// 如果指針沒有相遇的情況下，找到就鸯两，就賦值
if(left<right) arr[left] =arr[right];
// 從左邊開始查找
while(left<right&&arr[left]<=temp) left++;
// 如果指針沒有相遇的情況下闷旧，找到就，就賦值
if(left<right) arr[right]=arr[left];
}
// 將temp賦值到最中間的元素
arr[left]=temp;
return arr;
}
二钧唐、 真正的快速排序來了
前面一章我們在使用歸并排序的時候其實也講到了分治忙灼，那么快速排序是不是也可以用分治來解決呢？
回答是肯定的钝侠，沒錯该园，快排的思想也是分治。
我們重新整理一下思想：
給定一個數(shù)組：
[5 ,4 ,9 ,1 ,7 ,6 ,2]
| | |
[2,4,1] 5 [7,6,9]
1 2 4 5 6 7 9
如上圖所示帅韧，我們首先利用一次快排將比5小的數(shù)值放在5的左邊里初，比5大的數(shù)值放在5的右邊。然后我們可以將5左邊的數(shù)列在進行快排忽舟，同樣在該數(shù)列內(nèi)2左邊的肯定比2小双妨，2右邊的肯定比大。就這樣不斷的細分 就將原本無序的數(shù)列組合成了一個有序的數(shù)列了叮阅。
具體分治的代碼如下：
function quickSort(arr,left,right){
if(left<right){
//找到中心的位置
let datas = partition(arr,left,right);
// 排序中心左邊的數(shù)列
quickSort(arr,left,datas-1);
// 排序中心右邊的數(shù)列
quickSort(arr,datas+1,right);
}
return arr;
}
全套代碼如下：
function partition(arr,left,right){
let temp = arr[left];
while(left<right){
// 從右邊開始查找
while(left<right&&arr[right]>=temp) right--;
// 如果指針沒有相遇的情況下刁品，找到就，就賦值
if(left<right) arr[left] =arr[right];
// 從左邊開始查找
while(left<right&&arr[left]<=temp) left++;
// 如果指針沒有相遇的情況下浩姥，找到就挑随，就賦值
if(left<right) arr[right]=arr[left];
}
// 將temp賦值到最中間的元素
arr[left]=temp;
return left;
}
function quickSort(arr,left,right){
if(left<right){
//找到中心的位置
let datas = partition(arr,left,right);
// 排序中心左邊的數(shù)列
quickSort(arr,left,datas-1);
// 排序中心右邊的數(shù)列
quickSort(arr,datas+1,right);
}
return arr;
}
三、 其實還有更簡單的排序方式
其實關(guān)于這個勒叠，我還想到了更簡單的解決方法兜挨。思想大概就是尋找一個基點，我這里尋找的是數(shù)組的最后一項temp作為基點（當然你也可以選擇其他的元素）缴饭。然后數(shù)組內(nèi)剩下的元素進行遍歷暑劝，并且將比temp小的元素放在一個新的數(shù)組內(nèi)，比數(shù)組大的放在另一個新的數(shù)組內(nèi)颗搂。然后再將兩個新數(shù)組通過分治在進行快速排序特幔，直到數(shù)組的長度為小于2時停止隐轩，最后將排序好的數(shù)組和基點進行組合习蓬，就得到了新的有序數(shù)列了崇裁。
具體的代碼如下：
function quickSort(arr){
// 如果數(shù)組只有一項就直接放回了
if(arr.length<=1) return arr;
//取出元素的最后一項
let temp=arr.pop();
let left=[];
let right=[];
for(let i=0;i<arr.length;i++){
// 將比pivot
if(arr[i]<=temp) left.push(arr[i]);
else right.push(arr[i]);
}
return [...quickSort(left),...[temp],...quickSort(right)]
}
說在最后
快速排序也是面試經(jīng)常會考的點，怎么說呢拗盒？有備無患吧。額，要睡覺了仇奶，只能睡5分鐘了 中午不睡 下午崩潰呀！比驻！
