-
Notifications
You must be signed in to change notification settings - Fork 116
排序算法
zhangpan edited this page Aug 1, 2021
·
13 revisions
public static int[] swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
return nums;
}
- 快速排序
/**
* 快速排序
* <p>
* 核心的思路是取第一个元素(或者最后一个元素)作为分界点,把整个数组分成左右两侧,左边的元素小于或者等于分界点元素,
* 而右边的元素大于分界点元素,然后把分界点移到中间位置,对左右子数组分别进行递归,最后就能得到一个排序完成的数组。
* 当子数组只有一个或者没有元素的时候就结束这个递归过程。
*/
public static void quickSort(int[] nums, int left, int right) {
if (left > right) return;
int key = nums[left];
int l = left;
int r = right;
while (l < r) {
while (nums[r] >= key && l < r)
r--;
while (nums[l] <= key && l < r)
l++;
if (l < r)
swap(nums, r, l);
}
nums[left] = nums[r];
nums[r] = key;
quickSort(nums, left, r - 1);
quickSort(nums, r + 1, right);
}
-
归并排序
-
冒泡排序
/**
* 冒泡排序
* 冒泡排序从左到右依次比较两个相邻的元素,如果前一个元素比较大,就把前一个元素和后一个元素交换位置,
* 完成一趟循环后保证了最大的元素在最后一位。接下来进行第二趟排序,第二趟排序完成后第二大的元素在倒数第二位。
* 依次遍历直至整个数组排序完成。
* <p>
* 冒泡排序的时间复杂度是O(n2),空间复杂度为
*
* @param nums
* @return
*/
public static void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
}
}
}
}
public static int binSearch(int[] arr, int key) {
int left = 0;
int right = arr.length - 1;
int mid = 0;
while (left <= right) {
mid = (left + right) >> 1;
if (key < arr[mid]) {
right = mid - 1;
} else if (key > arr[mid]) {
left = mid + 1;
} else {
return mid;
}
}
return ~mid;
}
public static boolean isPalindrome(String s) {
int right = s.length() - 1;
int left = 0;
while (left < right) {
char leftChar = s.charAt(left);
while (!Character.isLetterOrDigit(leftChar) && left < right) {
leftChar = s.charAt(++left);
}
char rightChar = s.charAt(right);
while (!Character.isLetterOrDigit(rightChar) && left < right) {
rightChar = s.charAt(--right);
}
if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
return false;
}
left++;
right--;
}
return true;
}
public static int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int result = target - nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == result) {
return new int[] { i, j };
}
}
}
return null;
}
public static int[] twoSum1(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[] { map.get(target - nums[i]), i };
}
map.put(nums[i], i);
}
return null;
}
// 解法1
class NumArray {
private final int[] nums;
public NumArray(int[] nums) {
this.nums=nums;
}
public int sumRange(int left, int right) {
if(nums==null){
return 0;
}
int sum = 0;
for(;left<=right;left++){
sum += nums[left];
}
return sum;
}
}
// 解法2
public class NumArray {
private final int[] sums;
public NumArray(int[] nums) {
int n = nums.length;
sums = new int[n + 1];
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + sums[i + 1];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
if (nums.length == k) {
return (double) sum / k;
}
int maxSum = sum;
if (k == 1) {
for (int i = 1; i < nums.length - 1; i++) {
maxSum = Math.max(maxSum, nums[i]);
}
return maxSum;
}
for (int i = 0; i < nums.length - k; i++) {
sum = sum - nums[i] + nums[i + k];
maxSum = Math.max(maxSum, sum);
}
return (double) maxSum / k;
}
- JMM与volatile关键字
- synchronized的实现原理
- synchronized等待与唤醒机制
- AQS的实现原理
- ReentrantLock的实现原理
- ReentrantLock等待与唤醒机制
- CAS、Unsafe类以及Automic并发包
- ThreadLocal的实现原理
- 线程池的实现原理
- Java线程中断机制
- 多线程与并发常见面试题
- Android基础知识汇总
- MVC、MVP与MVVM
- SparseArray实现原理
- ArrayMap的实现原理
- SharedPreferences
- Bitmap
- Activity的启动模式
- Fragment核心原理
- 组件化项目架构搭建
- 组件化WebView架构搭建
- 为什么 Activity.finish() 之后 10s 才 onDestroy ?
- Binder与AIDL
- Binder实现原理
- Android系统启动流程
- InputManagerService
- WindowManagerService
- Choreographer详解
- SurfaceFlinger
- ViewRootImpl
- ActivityManagerService
- APP启动流程
- PMS安装与签名校验
- Dalvik与ART
- 内存优化策略
- UI界面及卡顿优化
- App启动优化
- ANR问题
- 包体积优化
- APK打包流程
- 电池电量优化
- Android屏幕适配
- 线上性能监控1--线上监控切入点
- 线上性能监控2--Matrix实现原理
- Glide实现原理
- OkHttp实现原理
- Retrofit实现原理
- RxJava实现原理
- RxJava中的线程切换与线程池
- LeakCanary实现原理
- ButterKnife实现原理
- ARouter实现原理
- Tinker实现原理
- 2. 两数相加
- 19.删除链表的倒数第 N 个结点
- 21. 合并两个有序链表
- 24. 两两交换链表中的节点
- 61. 旋转链表
- 86. 分隔链表
- 92. 反转链表 II
- 141. 环形链表
- 160. 相交链表
- 206. 反转链表
- 206 反转链表 扩展
- 234. 回文链表
- 237. 删除链表中的节点
- 445. 两数相加 II
- 面试题 02.02. 返回倒数第 k 个节点
- 面试题 02.08. 环路检测
- 剑指 Offer 06. 从尾到头打印链表
- 剑指 Offer 18. 删除链表的节点
- 剑指 Offer 22. 链表中倒数第k个节点
- 剑指 Offer 35. 复杂链表的复制
- 1. 两数之和
- 11. 盛最多水的容器
- 53. 最大子序和
- 75. 颜色分类
- 124.验证回文串
- 167. 两数之和 II - 输入有序数组 -169. 多数元素
- 189.旋转数组
- 209. 长度最小的子数组
- 283.移动0
- 303.区域和检索 - 数组不可变
- 338. 比特位计数
- 448. 找到所有数组中消失的数字
- 643.有序数组的平方
- 977. 有序数组的平方