class Solution {
// 在数组nums[l..r]中寻找第k大的数
private int find(int[] nums, int l, int r, int k) {
if (l == r) return nums[l];
int x = nums[r];
int i = l - 1;
int t;
// 在循环中维持nums[l..i] <= x, nums[i+1..j] > x
for (int j = l; j <= r - 1; j++) {
if (nums[j] <= x) {
i++;
// 交换nums[i]和nums[j]
t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
// 交换nums[i+1]和nums[r]
t = nums[i+1];
nums[i+1] = nums[r];
nums[r] = t;
if (r - i == k) return nums[i+1];
else if (r - i > k) return find(nums, i+2, r, k);
else return find(nums, l, i, k - (r-i));
}
public int findKthLargest(int[] nums, int k) {
return find(nums, 0, nums.length-1, k);
}
}
堆排序
public class HeapSort {
public void heapSort(int[] arr) {
buildMaxHeap(arr);
for (int i = arr.length - 1; i >= 1; i--) {
// 交换arr[0]和arr[i]，将堆的最大元素保存到数组末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// arr[0..i-1]为新的堆，调整堆
maxHeapify(arr, 0, i);
}
}
// 自底向上建堆，时间复杂度O(n)
private void buildMaxHeap(int[] arr) {
for (int i = arr.length / 2; i >= 0; i--) {
maxHeapify(arr, i, arr.length);
}
}
// 维护最大堆的性质
private void maxHeapify(int[] arr, int i, int heapSize) {
// 找出arr[i]、arr[i]的左节点、右节点这三者的最大值
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = i;
if (l < heapSize && arr[l] > arr[i])
largest = l;
if (r < heapSize && arr[r] > arr[largest])
largest = r;
if (largest != i) {
// 交换arr[i]和arr[largest]
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 继续调整节点
maxHeapify(arr, largest, heapSize);
}
}
}
归并排序
public class MergeSort {
public void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}
}
// 合并两个有序数组arr[l..mid] arr[mid+1..r]
private void merge(int arr[], int l, int mid, int r) {
// 将arr[]中的左右两个有序子数组拷贝到新的数组中
int n1 = mid - l + 1;
int n2 = r - mid;
int[] L = new int[n1+1];
int[] R = new int[n2+1];
for (int i = 0; i < n1; i++)
L[i] = arr[l+i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid+1+j];
// 在两个数组最后各加上一个哨兵
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
// 合并两个有序数组
int i = 0, j = 0;
for (int k = l; k <= r; k++) {
if (L[i] < R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
}
}
}