专业网站设计公司哪家好,wordpress 字母,网络游戏开发专业,如何免费做网站 详细点说系列文章目录 前言 本系列是个人力扣刷题汇总#xff0c;本文是排序算法。刷题顺序按照[力扣刷题攻略] Re#xff1a;从零开始的力扣刷题生活 - 力扣#xff08;LeetCode#xff09;
这个之前写的左神的课程笔记里也有#xff1a; 左程云算法与数据结构代码汇总之排序本文是排序算法。刷题顺序按照[力扣刷题攻略] Re从零开始的力扣刷题生活 - 力扣LeetCode
这个之前写的左神的课程笔记里也有 左程云算法与数据结构代码汇总之排序Java-CSDN博客
本来想看 按照这个分类一个个解题的但是好多都不是最优解甚至会超过时间限制所以要看较为系统一点的排序算法还是看上面那个之前的汇总吧只是没有希尔排序看看这个
【算法】排序算法之希尔排序 - 知乎 (zhihu.com)
其实我有个想法之后可以看看各个库里面的排序算法里面的源码怎么写的因为老是想偷懒。。。。 排序的一些基本题
912. 排序数组 - 力扣LeetCode 这里虽然写的冒泡排序但是超出时间复杂度了
冒泡
class Solution {public int[] sortArray(int[] nums) {bubbleSort(nums);return nums;}private void bubbleSort(int[] nums) {int n nums.length;for (int i 0; i n - 1; i) {for (int j 0; j n - i - 1; j) {if (nums[j] nums[j 1]) {// Swap nums[j] and nums[j 1]int temp nums[j];nums[j] nums[j 1];nums[j 1] temp;}}}}
}同样快排也超过了很离谱
class Solution {public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length - 1);return nums;}private void quickSort(int[] nums, int low, int high) {if (low high) {int pivotIndex partition(nums, low, high);quickSort(nums, low, pivotIndex - 1);quickSort(nums, pivotIndex 1, high);}}private int partition(int[] nums, int low, int high) {int pivot nums[high];int i low - 1;for (int j low; j high; j) {if (nums[j] pivot) {i;swap(nums, i, j);}}swap(nums, i 1, high);return i 1;}private void swap(int[] nums, int i, int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}
}
希尔排序
可以看【算法】排序算法之希尔排序 - 知乎 (zhihu.com)
public class Solution {/*** 使用希尔排序对整数数组进行升序排序。** param nums 待排序的整数数组* return 升序排序后的数组*/public int[] sortArray(int[] nums) {shellSort(nums);return nums;}/*** 希尔排序算法的具体实现。** param arr 待排序的整数数组*/private void shellSort(int[] arr) {// 初始化步长int step arr.length;step step 1;// 根据步长进行希尔排序while (step 1) {for (int count 0; count step; count) {// 对每个子数组进行插入排序for (int i step count; i arr.length; i step) {int insert i;int temp arr[insert];// 插入排序while (insert step - 1 temp arr[insert - step]) {arr[insert] arr[insert - step];insert - step;}arr[insert] temp;}}// 更新步长step step 1;}}
}215. 数组中的第K个最大元素 - 力扣LeetCode 还得是快排
class Solution {public int findKthLargest(int[] nums, int k) {return quickSelect(nums, 0, nums.length - 1, nums.length - k);}private int quickSelect(int[] nums, int left, int right, int target) {int index partition(nums, left, right);if (index target) {return nums[index];} else {return index target ? quickSelect(nums, left, index - 1, target) : quickSelect(nums, index 1, right, target);}}private int partition(int[] nums, int left, int right) {swap(nums, left, left new Random().nextInt(right - left 1));int pivot nums[left];while (left right) {while (left right nums[right] pivot) {right--;}if (left right) {nums[left] nums[right];}while (left right nums[left] pivot) {left;}if (left right) {nums[right--] nums[left];}}nums[left] pivot;return left;}private void swap(int[] nums, int i, int j) {int swap nums[i];nums[i] nums[j];nums[j] swap;}
} 总结
还有几题之后补吧。
