Kth Smallest Numbers in Unsorted Array（分别使用快排、归并、快选三种方法）

本文主要是介绍Kth Smallest Numbers in Unsorted Array（分别使用快排、归并、快选三种方法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Find the kth smallest numbers in an unsorted integer array.

Have you met this question in a real interview? Yes
Example
Given [3, 4, 1, 2, 5], k = 3, the 3rd smallest numbers are [1, 2, 3].

快排

public class Solution {/** @param k: An integer* @param nums: An integer array* @return: kth smallest element*/public int kthSmallest(int k, int[] nums) {// write your code hereif (nums == null || nums.length == 0 || nums.length < k) {return -1;}quickSort(nums, 0, nums.length - 1);return nums[k - 1];}private void quickSort(int[] nums, int start, int end) {if (start >= end) {return;}int left = start;int right = end;int pivot = nums[(left + right) / 2];while (left <= right) {while (left <= right && nums[left] < pivot) {left++;}while (left <= right && nums[right] > pivot) {right--;}if (left <= right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}quickSort(nums, start, right);quickSort(nums, left, end);}
}

归并

public class Solution {/** @param k: An integer* @param nums: An integer array* @return: kth smallest element*/public int kthSmallest(int k, int[] nums) {// write your code hereif (nums == null || nums.length == 0 || nums.length < k || k <= 0) {return -1;}int[] val = new int[nums.length];mergeSort(nums, val, 0, nums.length - 1);return nums[k - 1];}private void mergeSort(int[] nums, int[] val, int start, int end) {if (start >= end) {return;}int mid = (start + end) / 2;mergeSort(nums, val, start, mid);mergeSort(nums, val, mid + 1, end);merge(nums, val, start, mid, end);}private void merge(int[] nums, int[] val, int start, int mid, int end) {int left = start;int right = mid + 1;int index = start;while (left <= mid && right <= end) {if (nums[left] < nums[right]) {val[index++] = nums[left++];} else {val[index++] = nums[right++];}}while (left <= mid) {val[index++] = nums[left++];}while (right <= end) {val[index++] = nums[right++];}for (int i = start; i <= end; i++) {nums[i] = val[i];}}
}

快选（最优解）

public class Solution {/** @param k: An integer* @param nums: An integer array* @return: kth smallest element*/public int kthSmallest(int k, int[] nums) {// write your code hereif (nums == null || nums.length == 0 || nums.length < k) {return -1;}quickSelect(nums, 0, nums.length - 1, k - 1);return nums[k - 1];}private void quickSelect(int[] nums, int start, int end, int k) {if (start >= end) {return;}int left = start;int right = end;int pivot = nums[(left + right) / 2];while (left <= right) {while (left <= right && nums[left] < pivot) {left++;}while (left <= right && nums[right] > pivot) {right--;}if (left <= right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}if (right >= k) {quickSelect(nums, start, right, k);} else {quickSelect(nums, left, end, k);}}
}