从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<n-1;i++){for(int j=0;j<n-i-1;j++){if(nums[j] > nums[j+1]){int tmp =nums[j];nums[j] = nums[j+1];nums[j+1] = tmp;}}count++;if(count == k){break;}}return nums[n-k];}
}

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N)
空间复杂度：O(1) 

③归并排序（先分解再合并）

思路：通过分治法将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。与快速排序相比，快速排序是将序列划分成两个子序列，再递归使子序列有序；而归并排序是先使子序列有序，再进行合并。

运算符小妙用：

偶数&1 结果为0；奇数&1 结果为1；

左移相当于乘以2^n；右移相当于除以2^n，所以通常会用>>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 < leftArr.length && j < rightArr.length) {newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];}while (i < leftArr.length)newNum[m++] = leftArr[i++];while (j < rightArr.length)newNum[m++] = rightArr[j++];return newNum;}

 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 <= totalLength /2) {if (i < nums1.length && (j >= nums2.length || nums1[i] < nums2[j])) {nums[index] = nums1[i++];} else{nums[index] = nums2[j++];}if (index == totalLength / 2) {//nums数组长度为偶数if ((totalLength & 1) == 0) {return (nums[index] + nums[index - 1]) / 2.0;} else {//nums数组长度是奇数return 1.0 * nums[index];}}index++;}return 0.0;}
}

时间复杂度：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 < j){do i++;  while(nums[i] < x);do j--;  while(nums[j] > x);if(i < j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}//这个时候i==j==x，要寻找的坐标<=j则说明第k大元素在分界元素左边if(k <= j)  return quickSelect(nums, l, j, k);else return quickSelect(nums, j+1, r, k);}
}

快排的时间复杂度我们可以认为是O(nlogn),但当遇到原数组本身有序的情况下,其时间复杂度就会退化至O(n^2),这个其实很好理解,举个例子就明白了:

当最优情况下,即每趟选择key时都恰好选择到数组的中间值时(第n层可以确定个数字位置),快排的时间复杂度如下图完全(满)二叉树:

在最坏的情况下，这个树是一个完全的斜树，只有左半边或者右半边，即每趟选择key时都恰好选择到数组最大或最小的值时(即每一层都只能确定一个数字位置)。这时候我们的比较次数就变为∑n−1i=1(n−i)=(n−1)+(n−2)+⋯+1=n∗(n−1)2=O(n^2）

时间复杂度：最好O(nlogn),最坏O(n^2)

空间复杂度：递归造成栈空间的使用，最好O(nlogn)，最坏O(n)

⑤堆排序

java提供了PriorityQueue，可以构建小顶堆

class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> queue = new PriorityQueue<>(); //小顶堆for(int num : nums){queue.add(num);if(queue.size() > k){queue.poll();}}return queue.peek();}
}

自己构建堆 

class Solution {public int findKthLargest(int[] nums, int k) {//-------------1.首先，构建最大堆[6,5,4,3,2,1]----------------//建大堆：要从堆的最后一个非叶子节点开始向下调整for (int i = nums.length/2-1; i >= 0; i--) {adjustHeap(nums,i,nums.length);}//---2.每次把最大的换到最后一个位置，调整堆，交换后不把最后一个数看作堆里的数据-------for(int i = nums.length-1;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(left<tail&&nums[left]>nums[max]){max=left;}if(right<tail&&nums[right]>nums[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;}
}