目录
实现归并排序【MergeSort】并提供升序和降序方法
/**
* 归并排序
*/
public class MergeSort {
// 升序排列
private static final int UP_SORT_TYPE = 1;
// 降序排列
private static final int DOWN_SORT_TYPE = -1;
/**
* 升序排列
*
* @param nums:要排序的数组
*/
public static void upSort(int[] nums) {
if (nums == null || nums.length < 2)
return;
split(nums, 0, nums.length - 1, UP_SORT_TYPE);
}
/**
* 降序排列
*
* @param nums:要排序的数组
*/
public static void downSort(int[] nums) {
if (nums == null || nums.length < 2)
return;
split(nums, 0, nums.length - 1, DOWN_SORT_TYPE);
}
/**
* 分-治-合思想的体现
*/
private static void split(int[] nums, int low, int high, int sortType) {
if (low == high)
return;
int mid = (low + high) >>> 1;
split(nums, low, mid, sortType);
split(nums, mid + 1, high, sortType);
merge(nums, low, mid, high, sortType);
}
private static void merge(int[] nums, int low, int mid, int high, int sortType) {
int[] help = new int[high - low + 1];
int i = 0;
// 双指针
int p1 = low;
int p2 = mid + 1;
while (p1 <= mid && p2 <= high) {
if (sortType == UP_SORT_TYPE) {
// 处理成升序排列
help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
} else {
// 处理成降序排列
help[i++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
}
}
while (p1 <= mid)
help[i++] = nums[p1++];
while (p2 <= high)
help[i++] = nums[p2++];
for (i = 0; i < help.length; i++) {
nums[low + i] = help[i];
}
}
}
归并排序方法测试
import java.util.Arrays;
public class MergeSortTest {
public static void main(String[] args) {
// 测试升序
int[] nums1 = {23, 12, 34, 42, 345, 56, 45, 34, 37, 43, 1, 23, 44, 67};
MergeSort.upSort(nums1);
// [1, 12, 23, 23, 34, 34, 37, 42, 43, 44, 45, 56, 67, 345]
System.out.println(Arrays.toString(nums1));
// 测试降序
int[] nums2 = {23, 12, 34, 42, 345, 56, 45, 34, 37, 43, 1, 23, 44, 67};
MergeSort.downSort(nums2);
// [345, 67, 56, 45, 44, 43, 42, 37, 34, 34, 23, 23, 12, 1]
System.out.println(Arrays.toString(nums2));
}
}
LeetCode-215题
求数组中的第K个最大元素,这里使用归并排序方式
class Solution {
public int findKthLargest(int[] nums, int k) {
MergeSort.downSort(nums);
return nums[k - 1];
}
/**
* 归并排序
*/
class MergeSort {
// 升序排列
private static final int UP_SORT_TYPE = 1;
// 降序排列
private static final int DOWN_SORT_TYPE = -1;
/**
* 升序排列
*
* @param nums:要排序的数组
*/
public static void upSort(int[] nums) {
if (nums == null || nums.length < 2)
return;
split(nums, 0, nums.length - 1, UP_SORT_TYPE);
}
/**
* 降序排列
*
* @param nums:要排序的数组
*/
public static void downSort(int[] nums) {
if (nums == null || nums.length < 2)
return;
split(nums, 0, nums.length - 1, DOWN_SORT_TYPE);
}
/**
* 分-治-合思想的体现
*/
private static void split(int[] nums, int low, int high, int sortType) {
if (low == high)
return;
int mid = (low + high) >>> 1;
split(nums, low, mid, sortType);
split(nums, mid + 1, high, sortType);
merge(nums, low, mid, high, sortType);
}
private static void merge(int[] nums, int low, int mid, int high, int sortType) {
int[] help = new int[high - low + 1];
int i = 0;
// 双指针
int p1 = low;
int p2 = mid + 1;
while (p1 <= mid && p2 <= high) {
if (sortType == UP_SORT_TYPE) {
// 处理成升序排列
help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
} else {
// 处理成降序排列
help[i++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
}
}
while (p1 <= mid)
help[i++] = nums[p1++];
while (p2 <= high)
help[i++] = nums[p2++];
for (i = 0; i < help.length; i++) {
nums[low + i] = help[i];
}
}
}
}