从LeetCode215看排序算法
目录
LeetCode215 数组的第K个最大元素
① 第一反应：java的内置排序Arrays.sort()
② 冒泡排序
③归并排序（先分解再合并）
④快速排序（边分解边排序）
⑤堆排序
LeetCode215 数组的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
① 第一反应：java的内置排序Arrays.sort()
arrays.sort的复杂度取决于所使用的排序算法。在java中，Arays类中的sort方法使用的是一种优化的快速排序算法或归并排序算法。
对于快速排席算法，其平均时间复杂度为0(nl0gn)，其中n是数组的大小。然而，在最坏情况下，快速排序的时间复杂度可以达到O(n^2)，这发生在数组已经有序的情况下。
对于归并排序算法，其时间复杂度始终为0(nlog n)，不论输入数据的情况如何。
总结起来，Arrays.sort方法的平均时间复杂度为0(nlog n)，最坏情况下可能为O(n^2)。
② 冒泡排序
思路：总结来说就是两个for循环。多次遍历数组，每次遍历通过不断比较相邻元素的大小，如果左边大于右边就交换元素顺序，最终会将一个最大（或最小的）元素冒泡到数组的末尾或开头。直到最终没有任何元素需要交换（end一直--）。
举个例子，假设我们有一组数字：3, 38, 5, 44, 15, 47, 36, 26, 27, 2, 46, 4, 19, 50, 48。
下面是冒泡排序的执行过程：
1.第一轮比较后，最大的数字 50 被冒泡到了数组末尾，数组变为：3, 5, 38, 15, 44, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50
2.第二轮比较后，第二大的数字 48 被冒泡到了倒数第二的位置，数组变为：3, 5, 15, 38, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50
3.经过多轮比较和交换后，所有数字按照从小到大的顺序排列完成。
第k大只要找到第k个泡泡即可，无需向后比较对整个数组进行排序
class Solution {
public int findKthLargest(int[] nums, int k) {
return bubbleSort(nums, k);
}
int bubbleSort(int[] nums, int k){
int n = nums.length;
int count = 0;
for(int i=0;i>1来代替除以2。
不用第三个变量交换两个整数：
void swap(int x , int y)
{
x ^= y;
y ^= x;
x ^= y;
}
不断从中间划分子数组，递归合并
public class MergeSort {
public static int[] mergeSort(int[] nums, int l, int h) {
if (l == h)
return new int[] { nums[l] };
int mid = l + (h - l) / 2;
int[] leftArr = mergeSort(nums, l, mid); //左有序数组
int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
int m = 0, i = 0, j = 0;
while (i
LeetCode 4：寻找两个正序数组的中位数
这道题就用到了归并排序
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int totalLength = nums1.length + nums2.length;
int[] nums = new int[totalLength];
int i = 0, j = 0;
int index = 0;
while (index = nums2.length || nums1[i]
时间复杂度：O(nlogn)（稳定，因为每次都是从中间划分）
空间复杂度：递归造成栈空间的使用，最好O(nlogn)，最坏O(n)
④快速排序（边分解边排序）
思路：通过分治法将一个数组分成较小的子数组，然后递归地对每个子数组进行排序。
移动左右指针，左指针向右移动，直到找到一个大于等于分界值的元素；右指针向左移动，直到找到一个小于等于分界值的元素。交换这两个元素的位置，然后再次移动左右指针，直到左指针和右指针指向同一个元素，再递归左右子数组。
快速排序找到第k个最大的，就是排序后递增子数组的倒数第k个（序号为n-k）
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return quickSelect(nums, 0, n-1, n-k);
}
public int quickSelect(int[] nums, int l, int r, int k){
if(l == r) return nums[k];
int x = nums[l], i = l-1, j = r+1;
while(i x);
if(i = nums.length-k ;i--){
swap(nums,0,i);
adjustHeap(nums,0,i); //选出次小的数
}
return nums[nums.length-k];
}
//向下调整算法
public static void adjustHeap(int[] nums,int node,int tail){
int left = node*2+1;
int right = node*2+2;
//-------------大的往上浮，小的往下浮--------------------
int max = node;
if(leftnums[max]){
max=left;
}
if(rightnums[max]){
max=right;
}
//---------max是父节点和左右子节点中最大的数-------------------
//max!=node证明左右子节点有比父节点大的数,需要进行交换
if(max!=node){
swap(nums,max,node);
adjustHeap(nums,max,tail);
}
}
public static void swap(int[] nums, int index1, int index2){
int tmp = nums[index1];
nums[index1]=nums[index2];
nums[index2]=tmp;
}
}
