最佳化：增加pivot的隨機性可以讓演算法更加穩定
解法：快排基礎上微改程式碼
先手寫快排程式碼
//快排核心 private int quickSort（int［］ nums， int start， int end）{ //這裡沒有寫遞迴終止條件，這題不是要遞迴排序 int i = start； int j = end； int pivot = nums［start］； //選擇第一個為錨點元素 while（i < j）{ while（i < j && nums［j］ >= pivot）{ j——； } while（i < j && nums［i］ <= pivot）{ i++； } //交換元素 // swap（nums， i， j） ； //用這個沒有全部透過，bug int temp = nums［i］； nums［i］ = nums［j］； nums［j］ = temp； } //交換錨點元素至臨界位置 // swap（nums， start， j）；用這個沒有全部透過，bug nums［start］ = nums［j］； nums［j］ = pivot； return i； //繼承遞迴； // quickSort（nums， start， i-1）； // quickSort（nums， i+1， end）； }}
快排思想
兩個指標，left，指向第一個，right，指最後一個。向中間靠攏，右邊找比錨點元素小的值，左邊找比錨點元素大的值。找到了，讓這個兩個值交換位置，直到left == right ， 這個時候把錨點元素和left的值交換。這樣錨點元素左邊 都是比他小的， 右邊都是比他大的
上面的返回值是int 就是我們要找的第k 大嗎，不是。返回的只是隨機的一個位置。這個時候利用二分查詢。
int resIndex = quickSort（nums， start， end）；
if（resIndex
==
kTarget）{
return nums［resIndex］；
}else if（resIndex
>
kTarget）{
end = resIndex - 1；
}else if（resIndex
<
kTarget）{
start = resIndex + 1；
}
全部程式碼：
時間複雜度：O(N)，N 是陣列的長度
空間複雜度：O(1)，沒有藉助額外的空間。
class Solution { public int findKthLargest（int［］ nums， int k） { // int start = 0， end = nums。length - 1； int kTarget = nums。length - k； while（true）{ int resIndex = quickSort（nums， start， end）； if（resIndex == kTarget）{ return nums［resIndex］； }else if（resIndex > kTarget）{ end = resIndex - 1； }else if（resIndex < kTarget）{ start = resIndex + 1； } } } //快排核心 private int quickSort（int［］ nums， int start， int end）{ //這裡沒有寫遞迴終止條件，這題不是要遞迴排序 int i = start； int j = end； int pivot = nums［start］； //選擇第一個為錨點元素 while（i < j）{ while（i < j && nums［j］ >= pivot）{ j——； } while（i < j && nums［i］ <= pivot）{ i++； } //交換元素 // swap（nums， i， j） ； //用這個沒有全部透過，bug int temp = nums［i］； nums［i］ = nums［j］； nums［j］ = temp； } //交換錨點元素至臨界位置 // swap（nums， start， j）；用這個沒有全部透過，bug nums［start］ = nums［j］； nums［j］ = pivot； return i； //繼承遞迴； // quickSort（nums， start， i-1）； // quickSort（nums， i+1， end）； } private void swap（int［］ nums， int i， int j）{ int temp = nums［i］； nums［i］ = nums［j］； nums［j］ = nums［i］； }}
但是這樣寫，面試官會讓你最佳化的！
最佳化：增加pivot的隨機性可以讓演算法更加穩定
Random
。
nextInt
（n）
方法
，是生成一個隨機的int值，該值介於［0，n）的區間
Random
random
=
new
Random
（）；
// 在區間隨機選擇一個元素作為
if
（start
>
end） {
int
randomIndex
=
1
+
random。
nextInt
（end）；
//包含0 不包含end， 為了不是0， 加一個1；
swap
（nums， start， randomIndex）；
}
完整程式碼：
import java。util。Random；class Solution { public int findKthLargest（int［］ nums， int k） { // int start = 0， end = nums。length - 1； int kTarget = nums。length - k； while（true）{ int resIndex = quickSort（nums， start， end）； if（resIndex == kTarget）{ return nums［resIndex］； }else if（resIndex > kTarget）{ end = resIndex - 1； }else if（resIndex < kTarget）{ start = resIndex + 1； } } } //快排核心 private int quickSort（int［］ nums， int start， int end）{ //這裡沒有寫遞迴終止條件，這題不是要遞迴排序 int i = start； int j = end； Random random = new Random（）； // 在區間隨機選擇一個元素作為 if （start > end） { int randomIndex = 1 + random。nextInt（end）； //包含0 不包含end， 為了不是0， 加一個1； swap（nums， start， randomIndex）； } int pivot = nums［start］； //選擇第一個為錨點元素 while（i < j）{ while（i < j && nums［j］ >= pivot）{ j——； } while（i < j && nums［i］ <= pivot）{ i++； } //交換元素 // swap（nums， i， j） ； //用這個沒有全部透過，bug int temp = nums［i］； nums［i］ = nums［j］； nums［j］ = temp； } //交換錨點元素至臨界位置 // swap（nums， start， j）；用這個沒有全部透過，bug nums［start］ = nums［j］； nums［j］ = pivot； return i； //繼承遞迴； // quickSort（nums， start， i-1）； // quickSort（nums， i+1， end）； } private void swap（int［］ nums， int i， int j）{ int temp = nums［i］； nums［i］ = nums［j］； nums［j］ = nums［i］； }}
加油啊：：：：：PPPP
