快速排序
单路快排
获取随机一个元素，元素左边是小于它的，元素右边是大于它的。
partition：选择一个元素，交换left。比较nums[left]和nums[i]，如果nums[i]<nums[left]，找到一个小于标的元素的数据，交换到j的位置，j记录着最后一个小于标的元素的数据，切换j和left的位置，j所在的元素就是标的元素，返回j。获取left到right的随机一个索引，
new Random().nextInt(right - left + 1) + left;。0-9随机一个数，是10的随机数。
public class QuickSort1 {
public static void main(String[] args) {
int[] nums = new int[]{
3, 2, 1, 5, 7, 4, 6};
new QuickSort1().sort(nums);
System.out.println(Arrays.toString(nums));
}
public void sort(int[] nums) {
sort(nums, 0, nums.length - 1);
}
private void sort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int p = partition(nums, left, right);
sort(nums, left, p - 1);
sort(nums, p + 1, right);
}
private int partition(int[] nums, int left, int right) {
int p = new Random().nextInt(right - left + 1) + left;
swap(nums, p, left);
int j = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] < nums[left]) {
j++;
swap(nums, i, j);
}
}
swap(nums, left, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
双路快排
如果小于标的元素，符合要求，p1++；大于标的元素，符合要求，p2–。
找到前面不满足要求的元素，将前面的大的元素和后面小的元素互换位置。
选择p2：
[left,p1-1]是小于标的元素的，[p2+1,right]是大于标的元素。选择p2就是选择小于标的元素的数据和标的元素互换。
public class QuickSort2 {
public static void main(String[] args) {
int[] nums = new int[]{
3, 2, 1, 5, 7, 4, 6};
new QuickSort2().sort(nums);
System.out.println(Arrays.toString(nums));
}
public void sort(int[] nums) {
sort(nums, 0, nums.length - 1);
}
private void sort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int p = partition(nums, l, r);
sort(nums, l, p - 1);
sort(nums, p + 1, r);
}
private int partition(int[] nums, int l, int r) {
int p = new Random().nextInt(r - l + 1) + l;
swap(nums, l, p);
int p1 = l + 1;
int p2 = r;
while (true) {
//3 145672
while (p1 <= p2 && nums[p1] < nums[l]) {
p1++;
}
while (p1 <= p2 && nums[p2] > nums[l]) {
p2--;
}
if (p1 >= p2) {
break;
}
swap(nums, p1++, p2--);
}
swap(nums, l, p2);
return p2;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
堆排序
用数组存储完全二叉树，parent(i)=(i-1)/2；左孩子是
2*i+1，右孩子是2*1+2。构建大顶堆。找到所有有左孩子或者有孩子的节点（
0-len / 2 - 1）,和它的左孩子、右孩子比较，将大的元素切换到根节点。继续处理以小的元素为根节点的子树。把大顶堆的最大元素放在数组最后，将数组之前的元素重新构建大顶堆。
public class HeapSort {
public void sort(int[] nums) {
buildHeap(nums, nums.length);
for (int i = nums.length - 1; i > 0; i--) {
ArrayUtil.swap(nums, i, 0);
heapify(nums, 0, i);
}
}
private void buildHeap(int[] nums, int len) {
for (int i = len / 2 - 1; i >= 0; i--) {
heapify(nums, i, len);
}
}
private void heapify(int[] nums, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && nums[left] > nums[largest]) {
largest = left;
}
if (right < len && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
ArrayUtil.swap(nums, i, largest);
heapify(nums, largest, len);
}
}
}
算法题
LeetCode215.数组中的第K个最大元素
快排的解法
数组中存在两个相同元素，互换之后，i和j是满足条件的，互换之后要更新i和j的值。
快排之后，保证了j位置的元素
nums[j]<=x，如果有存在小于x的元素，没有就是r+1。
class Solution_LC215 {
public int findKthLargest(int[] nums, int k) {
return quickFind(nums, 0, nums.length - 1, nums.length - k);
}
private int quickFind(int[] nums, int l, int r, int index) {
if (l == r) return nums[index];
int x = nums[l], i = l-1, j = r+1;
while (i < j) {
do {
i++;
} while (nums[i] < x);
do {
j--;
} while (nums[j] > x);
if (i < j) {
swap(nums,i,j);
}
}
if (index <= j) return quickFind(nums, l, j, index);
else return quickFind(nums, j + 1, r, index);
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
堆排序的处理思路
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
buildHeap(nums, n);
for (int i = n - 1; i >= n - k + 1; i--) {
swap(nums, i, 0);
heapify(nums, 0, i);
}
return nums[0];
}
private void buildHeap(int[] nums, int len) {
for (int i = len / 2 - 1; i >= 0; i--) {
heapify(nums, i, len);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void heapify(int[] nums, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && nums[left] > nums[largest]) {
largest = left;
}
if (right < len && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums, i, largest);
heapify(nums, largest, len);
}
}
}
面试题 17.14. 最小K个数
使用优先队列，优先队列默认是小顶堆。
class Solution {
public int[] smallestK(int[] arr, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int num : arr) {
priorityQueue.add(num);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = priorityQueue.poll();
}
return res;
}
}
使用单路快排
class Solution {
public int[] smallestK(int[] arr, int k) {
qSort(arr, 0, arr.length - 1, k);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
private void qSort(int[] arr, int l, int r, int k) {
if (l >= r) {
return;
}
int p = partition(arr, l, r, k);
if (p == k) {
return;
} else if (p < k) {
qSort(arr, p + 1, r, k);
} else {
qSort(arr, l, p - 1, k);
}
}
private int partition(int[] arr, int l, int r, int k) {
int pos = new Random().nextInt(r - l + 1) + l;
swap(arr, l, pos);
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < arr[l]) {
j++;
swap(arr, i, j);
}
}
swap(arr, j, l);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
使用双路快排，
j--;必须要在i++前面。因为最后获取的值是i，i满足arr[i] <= x。i从数组最前面寻找大的元素，j从数组最后面寻找小的元素，当j和i相遇，j每一次都是先走的，走的位置就是小于i的位置。如果先走i++，后走j--，获取的就是j。
class Solution {
public int[] smallestK(int[] arr, int k) {
qSort(arr, 0, arr.length - 1, k);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
private void qSort(int[] arr, int l, int r, int k) {
if (l >= r) {
return;
}
int pos = new Random().nextInt(r - l + 1) + l;
swap(arr, l, pos);
int x = arr[l];
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= x) {
j--;
}
while (i < j && arr[i] <= x) {
i++;
}
swap(arr, i, j);
}
swap(arr, i, l);
if (i == k) {
return;
} else if (i < k) {
qSort(arr, i + 1, r, k);
} else {
qSort(arr, l, i - 1, k);
}
}
private int partition(int[] arr, int l, int r, int k) {
int pos = new Random().nextInt(r - l + 1) + l;
swap(arr, l, pos);
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < arr[l]) {
j++;
swap(arr, i, j);
}
}
swap(arr, j, l);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
Leetcode347. 前 K 个高频元素
使用优先队列，存入数组，排序按照数组中每个元素的第二个数字排序。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
priorityQueue.add(new int[] {
entry.getKey(), entry.getValue() });
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = priorityQueue.poll()[0];
}
return res;
}
}
LCR 164. 破解闯关密码
使用优先队列
class Solution {
public String crackPassword(int[] password) {
PriorityQueue<String> priorityQueue = new PriorityQueue<>((a, b) -> {
return (a + b).compareTo(b + a);
});
for (int num : password) {
priorityQueue.add(num + "");
}
StringBuilder stringBuilder = new StringBuilder();
while (!priorityQueue.isEmpty()) {
stringBuilder.append(priorityQueue.poll());
}
return stringBuilder.toString();
}
}
使用快排
找到比
strings[l]小的元素，判断如果比strings[l]大的话，进行j--。
class Solution {
public String crackPassword(int[] password) {
String[] pwd = new String[password.length];
for (int i = 0; i < password.length; i++) {
pwd[i] = String.valueOf(password[i]);
}
quickSort(pwd, 0, password.length - 1);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < pwd.length; i++) {
sb.append(pwd[i]);
}
return sb.toString();
}
private void quickSort(String[] strings, int l, int r) {
if (l >= r) {
return;
}
int i = l, j = r;
String tmp = strings[l];
while (i < j) {
while (i < j && (tmp + strings[j]).compareTo(strings[j] + tmp) <= 0) {
j--;
}
while (i < j && (tmp + strings[i]).compareTo(strings[i] + tmp) >= 0) {
i++;
}
swap(strings, i, j);
}
swap(strings, i, l);
quickSort(strings, i + 1, r);
quickSort(strings, l, i - 1);
}
public void swap(String[] strs, int i, int j) {
String tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
}
Leetcode179. 最大数
和上一题一样，需要判断第一个字符是否为0。
class Solution {
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, (a, b) -> {
return (b + a).compareTo(a + b);
});
if (strs[0].equals("0"))
return "0";
StringBuilder res = new StringBuilder();
for (String s : strs)
res.append(s);
return res.toString();
}
}
LeetCode148: 排序链表
