1.數組中第k大的數字

題目：

LeetCode：數組中的第k個最大元素，給定整數數組nums和整數k，請返回數組中第k個最大的元素，請注意，你需要找的是數組排序后第k個最大的元素，而不是第k個不同的元素。

運用快速排序的方法對數組進行排好序，然后選擇第k個元素就是要求的結果，

上一節我們寫了以中間元素作為哨兵的情況，這里我們來看下第一個元素作為哨兵，需要排序的序列是：

{26, 53, 48, 15, 13, 48, 32, 15 }，我們以26為哨兵。

?上面紅框位置表示哨兵交換過后的位置，根據指針的移動情況，當指針停止的時候進行比較，大于哨兵，就去哨兵的左側，而它空下來的位置就給哨兵，即紅色圈出的位置

雙指針移動：

left: arr[left] < pivot時，不移動，arr[left] > pivot時，left++。

right: arr[right] > pivot時，不移動，否則，right--。

對比上一節的代碼實現方式，我們來看下另一種的實現：

public void quickSort(int[] nums, int left, int right){int start = left;int end = right;//取中間位置作為哨兵int pivot = nums[(end + start) / 2];//每次循環將大的放左邊，小的放右邊while (start < end){while (nums[start] > pivot){start++;}while (nums[end] < pivot){end--;}//如果start>=end，說明左邊的值都大于pivot，右邊的反之if (start >= end){break;}//交換int temp = nums[start];nums[start] = nums[end];nums[end] = temp;//兩個指針指向最中間的兩個元素的時候，交換過后，兩個指針就不會移動了，所以需要再次處理//左邊指針等于pivot的時候，使右邊指針向左移動，if (nums[start] == pivot){end--;}//右邊指針等于pivot的時候，左邊向左移動if (nums[end] == pivot){start++;}}if (start == end){start++;end--;}if (left < end){quickSort(nums,left,end);}if (right > start){quickSort(nums,start,right);}}

對比上篇文章的代碼，還是上篇文章的代碼更容易理解，建議用下面代碼：

    public void quickSort2(int[] nums, int left, int right){if (left >= right){return;}int start = left;int end = right;int pivot = nums[(left+right) / 2];while (left <= right){//左邊都是大于pivot的元素while (nums[left] > pivot){left++;}//右邊都是小于pivot的元素while (nums[right] < pivot){right--;}if (left <= right){//交換int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}//向左遞歸quickSort2(nums,start,right);quickSort2(nums,left,end);}