😉毛遂自荐
毛遂自荐一下，给大家推荐一下自己的专栏😁，欢迎小伙伴们收藏关注😊
?题目
2021-09-13力扣每日一题：面试题 17.14. 最小K个数
🔥思路
这题表面上一看，其实就是一个数组排序问题
简单思路：将数组排序后，建立长度为k的数组，将原数组前k个元素赋给新数组，然后返回。
思路虽简单，但是千万不可调用什么已有的方法进行排序，比如：Arrays.sort()，这是Java的，相信其他语言应该也有类似的方法
重要的事情说三遍：不可以调用已有方法！不可以调用已有方法！不可以调用已有方法！
🌈为什么？
因为这是面试题啊🤣，面试官出这种题目，基本上就是让你手写排序算法，例如：快排、堆排、归并，如果写出来的话，说不定还让你优化😉
下面给大家提供常见排序算法题解和优化代码，觉得不错的小伙伴可以给个一键三连哦😁
?代码
🌝快速排序
class Solution {
public int[] smallestK(int[] arr, int k) {
quickSort(arr,k,0,arr.length - 1);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
public void quickSort(int[] arr, int k,int start,int end) {
if (start < end) {
int mid = getMiddle(arr,start,end);
quickSort(arr,k,start,mid - 1);
quickSort(arr,k,mid + 1,end);
}
}
private int getMiddle(int[] arr, int start, int end) {
int left = start,right = end;
int mid = arr[left];
while (left < right) {
while (left < right && arr[right] >= mid) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= mid) {
left++;
}
arr[right] = arr[left];
}
arr[left] = mid;
return left;
}
}
🌑快排分区思想（优化）
class Solution {
public int[] smallestK(int[] arr, int k) {
quickSort(arr,0,arr.length - 1,k - 1);
int[] res = new int[k];
int i = 0;
while(i < k) {
res[i] = arr[i];
i++;
}
return res;
}
private void quickSort(int[] nums,int start,int end,int k) {
if(start >= end) return;
int mid = getMiddle(nums,start,end);
if(mid == k) {
return;
}
if(k > mid) {
quickSort(nums,mid + 1,end,k);
}else {
quickSort(nums,start,mid - 1,k);
}
}
private int getMiddle(int[] nums,int start,int end) {
int left = start,right = end;
int mid = nums[left];
while(left < right) {
while(left < right && nums[right] >= mid) {
right--;
}
nums[left] = nums[right];
while(left < right && nums[left] <= mid) {
left++;
}
nums[right] = nums[left];
}
nums[left] = mid;
return left;
}
}
🌒堆排序
class Solution {
public int[] smallestK(int[] arr, int k) {
heapSort(arr,arr.length);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
public static void heapSort(int[] arr,int heapSize) {
//上浮
for (int i = heapSize / 2 - 1; i >= 0; i--) {
builderHeap(arr,i,arr.length);
}
//下沉
for (int i = heapSize - 1; i >= 0; i--) {
swap(arr,0,i);
builderHeap(arr,0,i);
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void builderHeap(int[] arr, int index, int length) {
//当前节点
int tmp = arr[index];
//左子节点
for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {
//如果右子节点值大于左子节点
if (i + 1 < length && arr[i + 1] > arr[i]) {
i++;
}
//如果左子节点和右子节点的最大值大于父节点，则进行交换
if (arr[i] > tmp) {
arr[index] = arr[i];
index = i;
}else
break;
}
arr[index] = tmp;
}
}
🌓堆排序（优化）——>构造固定堆
class Solution {
public int[] smallestK(int[] arr, int k) {
if(k == 0) return new int[0];
return topK(arr,k);
}
private static int[] topK(int[] data, int k) {
int[] topK = new int[k];
//构造固定大小堆
for (int i = 0; i < k; i++) {
topK[i] = data[i];
}
//
buildHeap(topK);
for (int i = k; i < data.length; i++) {
int root = topK[0];
if (data[i] < root) {
//如果data元素大于堆顶元素，放入堆中，替换堆顶元素，并重新构建小根堆
topK[0] = data[i];
heapify(topK,0,topK.length);
}
}
return topK;
}
private static void buildHeap(int[] data) {
//从最后一个父节点的下标开始遍历 子推父：(data.length - 1 - 1)/2
int heapSize = data.length;
for (int i = heapSize / 2 - 1; i >= 0; i--) {
heapify(data,i,heapSize);
}
}
private static void heapify(int[] arr,int index,int len) {
int tmp = arr[index];
for (int i = index * 2 + 1; i < len; i = i * 2 + 1) {
if (i + 1 < len && arr[i + 1] > arr[i]) {
i += 1;
}
if (arr[i] > tmp) {
arr[index] = arr[i];
index = i;
}else
break;
}
arr[index] = tmp;
}
}
🌔归并排序
class Solution {
int[] tmp;
public int[] smallestK(int[] arr, int k) {
if(k == 0) return new int[0];
tmp = new int[arr.length];
mergeSort(arr,0,arr.length - 1);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
private void mergeSort(int[] nums, int start, int end) {
if (start >= end) return;
//以mid为中心将数组分为两个数组
int mid = start + (end - start) / 2;
mergeSort(nums,start,mid);
mergeSort(nums,mid + 1,end);
int i = start,j = mid + 1;
int cnt = 0;
//将两个数组中的数据，从小到大排序，用tmp数组保存
while (i <= mid && j <= end) {
if (nums[i] <= nums[j]) {
tmp[cnt++] = nums[i++];
}else {
tmp[cnt++] = nums[j++];
}
}
while (i <= mid) {
tmp[cnt++] = nums[i++];
}
while (j <= end) {
tmp[cnt++] = nums[j++];
}
//将tmp中排好的有序数据在指定范围内，写回给 nums
for (int k = 0; k < end - start + 1; k++) {
nums[k + start] = tmp[k];
}
}
}
?补充知识点
快速排序和堆排序是不稳定排序，归并排序是稳定排序。
💖最后
我是 Code皮皮虾，一个热爱分享知识的 皮皮虾爱好者，未来的日子里会不断更新出对大家有益的博文，期待大家的关注！！！
创作不易，如果这篇博文对各位有帮助，希望各位小伙伴可以一键三连哦！，感谢支持，我们下次再见~~~
