1. 基本排序方法
1. 冒泡排序
时间复杂度: O(nˆ2)
空间复杂度: O(1)
思想: 每次把最大的数，放到最后，就像水泡一样浮上去。
- 第一个循环控制每次的结尾end，从length-1到1，不用到0(第一个循环会到0)
- 第二个循环控制从 开头 到 倒数第二 的两两比较，下标表示为 i 和 i+1
如果arr[i] > arr[i+1] 则交换两数
// 冒泡排序, in-place 修改
public static void bubbleSort(int[] arr){
if(arr==null || arr.length<2){
return;
}
// 第一个for loop规定比较的结束范围,从0~length-1 到 0~1
for(int e = arr.length-1; e>0; e--){
// 第二个loop 规定从0开始到end-1结束，依次比较 i 和 i+1的数，如果i大则交换
for(int i=0; i<e; i++){
if(arr[i] > arr[i+1]){
swap(arr, i, i+1);
}
}
}
} 2. 选择排序
时间复杂度: O(nˆ2)
空间复杂度: O(1)
思想: 从i=0开始，依次找到最小的数，并把它放到这个象征数组开始的位置(i++，每次更新)
- 第一个循环控制每次的起始范围，从
i=0开始，到i=length-2结束 - 第二个循环开始时，每次暂时先让
minIndex = i - 第二个循环控制从
j=i+1到j=length-1结束 的比较，每次比较minIndex和arr[j]
如果arr[j] < minIndex则minIndex更新为j
public static void selectionSort(int[] arr){
if(arr==null || arr.length<2){
return;
}
// 最小的下标从 0 开始，到end-1结束
for(int i=0; i < (arr.length-1); i++){
int minIndex = i;
// 第二个loop开始，依次比较，找到最小的下标
for(int j = i+1; j<arr.length; j++){
minIndex = arr[j] <= arr[minIndex] ? j : minIndex;
}
swap(arr,i,minIndex);
}
} 3. 插入排序
时间复杂度: O(nˆ2), 最好情况O(n)，最坏情况O(nˆ2)
空间复杂度: O(1)
思想: 首先假设数组在0-0上有序，且必有序(只有一个数), 依次插入一个数，依次与有序数组最外层的数比较，如果这个数更小，则交换，再比较，直到整体有序(再新插入数后)
public static void insertionSort(int[] arr){
if (arr==null || arr.length<2){
return;
}
// 假设0-0上有序, 从i=1开始加入新的数
for(int i=1; i<arr.length; i++){
// j是有序数组最外层的数，与新加入的数j+1比较
for(int j=i-1; j>=0 ; j--){
// 最有情况: 每次新加的数，都大,不用交换
if(arr[j] <= arr[j+1]){
break;
}
swap(arr, j, j+1);
}
}
} 2. 注意的知识点
2.1 对数器
对数器就是用一个绝对正确的排序算法和你自己的对比测试:
- 有一个你想要测的方法a
- 实现复杂度不好但是容易实现的方法b
- 实现一个随机样本产生器
- 把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
- 如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者 方法b
- 当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
// for test 对数器：绝对正确的排序
public static void comparator(int[] arr){
Arrays.sort(arr);
}
// 产生随机数字
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random()产生 0.0 - 1.0 的double type value
int[] arr = new int[maxSize];
for(int i=0; i<arr.length; i++){
arr[i] = (int) (maxValue * Math.random());
}
return arr;
}
// 复制产生的数组
// 也可以用Arrays工具中的 Arrays.copyOf(array, newLength)
public static int[] copyArray(int[] arr){
if (arr==null){
return null;
}
int[] res = new int[arr.length];
for(int i=0; i<arr.length; i++){
res[i] = arr[i];
}
return res;
}
// 判断分类结果是否一致
// 也可以用Arrays工具中的 Arrays.equals(array1, array2)
public static boolean isEqual(int[] arr1, int[] arr2){
if(arr1==null || arr2==null){
return false;
}
if(arr1.length != arr2.length){
return false;
}
for(int i=0; i<arr1.length; i++){
if(arr1[i] != arr2[i]){
return false;
}
}
return true;
}
// 展示分类结果
public static void printArray(int[] arr){
if(arr==null){
return ;
}
for(int i=0; i<arr.length; i++){
System.out.print(arr[i]+" ");
}
System.out.println();
} 最后测试的时候可以采用，随机生成5000次数组对比
int testTime =5000;
int maxSize =100;
int maxValue =100;
boolean succeed = true;
for(int i=0; i<testTime; i++){
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
bubbleSort(arr1);
comparator(arr2);
if(!isEqual(arr1, arr2)){
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Error, check it!"); 2.2 swap函数-java中的值传递和引用传递
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
} 实验观察:
在java中，函数修改数组，和c++一样，是引用传递，直接修改本身，不产生copy；
但是函数修改数字，是值传递，不会修改本身的值；
结论:
参考资料1,2
更正参考资料1中，最后一张图，person 指向了 X03333 不是 X02222
在面试中，一句话总结就是: Java所谓引用传递也就是传递了引用的拷贝，所以本质也是值传递。
在Persontest(Person person)函数中，实际传入不是main()中的p，而是在Persontest的栈帧中，创建了一个变量person，引用copy一份赋值给它了，在里面修改person的引用，让它指向别处，不会影响main中的p指向的class的实际的值。本质还是值传递
public class PassByValue {
public static class Person{
private String name;
private int age;
public String getName(){
return name;
}
public int getAge(){
return age;
}
public void setName(String name){
this.name = name;
}
public void setAge(int age){
this.age = age;
}
}
public static void PersonTest(Person person){
System.out.println("传入的person的name："+person.getName());
person.setName("我是张三");
System.out.println("方法内重新赋值后的name："+person.getName());
}
public static void main(String[] args) {
Person p=new Person();
p.setName("我是李四");
p.setAge(45);
PersonTest(p);
System.out.println("方法执行后的name："+p.getName());
}
} 执行结果:
传入的person的name：我是李四 方法内重新赋值后的name：我是张三 方法执行后的name：我是张三
修改函数:
public static void PersonTest(Person person){
System.out.println("传入的person的name："+person.getName());
person = new Person();
person.setName("我是张三");
System.out.println("方法内重新赋值后的name："+person.getName());
} 执行结果:
传入的person的name：我是李四 方法内重新赋值后的name：我是张三 方法执行后的name：我是李四
3. 二分查找
二分查找，适用于在有序数组上查找符合某些标准的数，相比遍历它的时间复杂度是O(logn), 优化效果明显。
模版代码(来源leet code网友)，注意边界条件:
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1; // 注意
while(left <= right) { // 注意
int mid = (left + right) / 2; // 注意
if(nums[mid] == target) { // 注意
// 相关逻辑
} else if(nums[mid] > target) {
right = mid - 1; // 注意
} else {
left = mid + 1; // 注意
}
}
// 相关返回值
return 0;
} 3.1 找 >= 某个数最左侧的位置在排序数组上
思路:
1.解法一：遍历
从头到尾遍历，找到>=某个数最左的位置
从尾到头遍历，找到<=某个数最右的位置
时间复杂度: O(n)
2.解法二: 二分查找
根据模版，注意=value时的操作，注意等号给谁了!
若合并到更新R，每次找到更小R，最后会找到最左的>=value的位置，也就是离你最近不小于你的数
若合并到更新L，每次找到更大L，最后会找到最右的<=value的位置，也就是离你最近不大于你的数
时间复杂度: o(log(N))
模版代码:
// 在排序的arr上，找到一个数的位置，它满足>=value的最左位置
// 如果没有找到，就是说这个数比数组中所有的数都大，则返回-1
public static int nearestIndexRight(int[] arr, int value) {
int L = 0;
int R = arr.length - 1;
// 如果寻找的数大于最大的数，那么找不到他的位置，返回-1
if (value > arr[R]) {
return -1;
}
// 排除边界条件后
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (arr[mid] >= value) {
R = mid - 1;
} else {
L =mid + 1;
}
}
return L;
}
// 在排序的arr上，找到一个数的位置，它满足<=value的最右位置
// 如果没有找到，就是说这个数比数组中所有的数都小，则返回-1
public static int nearestIndexLeft(int[] arr, int value) {
int L = 0;
int R = arr.length - 1;
// 如果寻找的数小于最小的数，那么找不到他的位置，返回-1
if (value < arr[L]) {
return -1;
}
// 排除边界条件后
while (L <= R) {
int mid = L + ((R - L) >> 1);
// 等号的变化
if (arr[mid] > value) {
R = mid - 1;
} else {
L =mid + 1;
}
}
return R;
} 3.2 找到局部最小
题目描述:
在一个无序数组中，相邻元素不相等，请返回任意一局部最小值, 局部最小的定义是:
arr[0]<arr[1]，则arr[0]是局部最小arr[N-1]<arr[N-2]，则arr[N-1]是局部最小arr[i-1]>arr[i]<arr[i+1]，则arr[i]是局部最小
此时二分法也可以用在无序数组上，若条件一和条件二不满足，则在i=1 到 i=N-2上寻找, 需要注意的是此时，在一个区间上先降后升，中间一定有拐点，也就是局部最小:
public static int getLessIndex(int[] arr) {
// 极端情况
if (arr == null || arr.length == 0) {
return -1; // no exist
}
// 先检查第一个元素，是否符合
if (arr.length == 1 || arr[0] < arr[1]) {
return 0;
}
// 再检查最后一个元素，是否符合
if (arr[arr.length - 1] < arr[arr.length - 2]) {
return arr.length - 1;
}
// 在 1～N-2上寻找
int left = 1;
int right = arr.length - 2;
int mid = 0;
while (left <= right) {
mid = (left + right) / 2;
// 直接找到
if(arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]){
return mid;
}
// 则在右侧一定有拐点
if (arr[mid] > arr[mid - 1]) {
right = mid - 1;
}
// 则在左侧一定有拐点
else if(arr[mid] > arr[mid + 1]){
left = mid + 1;
}
}
return left;
} 3.3 搜索插入位置
题目力扣35
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
输入: [1,3,5,6], 5 输出: 2 输入: [1,3,5,6], 2 输出: 1 输入: [1,3,5,6], 7 输出: 4 输入: [1,3,5,6], 0 输出: 0
思路:
利用二分法，找插入位置，先处理两个边界情况，比最小的数小，或比最大的数大
剩下就是，直接找到target树，返回下标；或者找不到；
再找不到的情况中，一定是，target在两个数中间，比左边的大，但比右边的小，此时二分，mid指向右边的数，target比mid大，更新L=mid+1，这次迭代完成后，L=R只剩下一个数(比target大)，再迭代最后一次，此时返回L或者R+1就是正确的index，因为在最后一次迭代，会更新R，L不动，让R=mid-1
代码:
public int searchInsert(int[] nums, int target) {
//二分法插入,套模版
// 边界情况,比最小的数小
if(nums[0]>target){
return 0;
}
// 边界情况,比最大的数大
if(nums[nums.length-1]<target){
return nums.length;
}
int L = 0;
int R = nums.length-1;
while(L<=R){
int mid = L + ((R-L)>>1);
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
L=mid+1;
}
else{
R=mid-1;
}
}
return R+1 or L;
} 
京公网安备 11010502036488号