- 快速排序
- 算法思路
- 二路归并排序
- 算法思路
- 堆排序
- 算法思路
本质上就是排序算法 快速排序 算法思路
- 快速排序思想来源于双指针,将哨兵结点的值放置于指定位置,使得该位置左侧均小于等于哨兵节点,右侧均大于等于哨兵节点。因此,为将哨兵节点值放在指定位置,需先对其进行保存。并按照从右向左,赋空位值。从左向右,赋空位值。左右指针的最后一次移动会带来空位,将哨兵填充置此位置,并返回哨兵坐标,进行分治。
- 由此,代码模板如下:
class Solution {
public int findKthLargest(int[] nums, int k) {
int i=0,j=nums.length-1;
quickSort(nums,i,j);
return nums[nums.length-k];
}
public void quickSort(int[] nums,int i,int j){
if(i>=j){
return;
}
int privot = privotSort(nums,i,j);
quickSort(nums,i,privot-1);
quickSort(nums,privot+1,j);
}
public int privotSort(int[] nums,int i,int j){
int temp = nums[i];
// 注意我的边界条件均没有取等号,当遇见与哨兵值相同时,需要判断,左右指针是否仍然保持左右位置,如果保持相对关系,则可对空位赋值。
while(itemp){
j--;
}
if(i
二路归并排序
算法思路
- 首先理解,二路归并排序,是分治递归算法,需要开辟额外数组。从中间进行分治递归,将其切成最小的两个单位后,对其进行排序。通过递归回溯,将两个内部排序完成后的数组进行合并。
- 由此,代码模板如下:
class Solution {
public int findKthLargest(int[] nums, int k) {
// 二路归并排序
int len = nums.length;
int[] numbers = mergeSort(nums,len);
return numbers[len-k];
}
public int[] mergeSort(int[] nums,int len){
if(len<2){
return nums;
}
int mid = len/2;
int[] leftNums = Arrays.copyOfRange(nums,0,mid);
int[] rightNums = Arrays.copyOfRange(nums,mid,len);
return merge(mergeSort(leftNums,leftNums.length),mergeSort(rightNums,rightNums.length));
}
public int[] merge(int[] nums1,int[] nums2){
int len1= nums1.length;
int len2 = nums2.length;
int[] nums = new int[len1+len2];
int i=0,j=0,k=0;
for(;k=len1||(j=nums2[j])){
nums[i+j] = nums2[j];
j++;
}else{
nums[i+j] = nums1[i];
i++;
}
}
return nums;
}
}
堆排序
算法思路
- 一般考察大顶堆,即父节点值大于左右子节点值。排序步骤,一般从第一个非叶子节点(n/2-1)开始,自上而下,将较大值向上取。再自下而上,调整至根节点,保证更根节点为最大值,且父节点均大于左右节点。将最大值从根节点获取后,将其按照调整位置进行数组的置换,再对根节点进行调整。
- 由此,算法模板如下:
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
heapSort(nums,len);
return nums[len-k];
}
// 堆排序
public void heapSort(int[] nums,int len){
// 从第一个非叶子节点调整一次
for(int i =len/2-1;i>=0;i--){
adjustHeap(nums,i,len);
}
// 交换len-1次
for(int i=len-1;i>0;i--){
// 始终交换最大值置数组末尾
swap(nums,0,i);
// 相当于删除树上一些节点,已经排序完成的,不需要再参与调整
adjustHeap(nums,0,i);
}
}
// 从当前位置向下到根节点进行最大值调整
public void adjustHeap(int[] nums,int root,int end){
// 标记位
int index = root;
// 左右节点
int left = root*2+1;
int right = root*2+2;
// 右节点存在,且值大于最大节点
if(rightnums[index]){
index = right;
}
// 左节点存在,且值大于最大节点
if(leftnums[index]){
index = left;
}
// 递归出口
if(index == root){
return ;
}
swap(nums,root,index);
// 递归向下处理
adjustHeap(nums,index,end);
}
public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}



