基础篇-interview-heima

[toc]

✨你好啊，我是“ 罗师傅”，是一名程序猿哦。
🌍主页链接：楚门的世界 - 一个热爱学习和运动的程序猿
☀️博文主更方向为：备战秋招ing
❤️一个“不想让我曾没有做好的也成为你的遗憾”的博主。
💪很高兴与你相遇，一起加油！

前言

逢郎欲语低头笑，碧玉搔头落水中。——白居易《采莲曲》

二分查找

手写二分查找

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 5, 6, 33, 55, 77, 99, 334, 456};
        int target = 99;
        int idx = binarySearch(array, target);
        System.out.println("idx = " + idx);
    }

    // 二分查找，找得到返回元素索引，找不到返回-1
    private static int binarySearch(int[] array, int target) {
        int l = 0, r = array.length - 1, mid;
        while (l <= r) {
            mid = l + (r - l) / 2; // 可以避免溢出问题
            // mid = (l + r) >>> 1; // 无符号位右移，效率更高
            if (array[mid] == target)
                return mid;
            else if (array[mid] > target)
                r = mid - 1;
            else if (array[mid] < target)
                l = mid + 1;
        }
        return -1;
    }
}

mid = l + (r - l) / 2; // 可以避免溢出问题
mid = (l + r) >>> 1; // 无符号位右移，效率更高

//>>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
//>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。

奇技淫巧：

• 奇数二分取中间
• 偶数二分取中间靠左
• 2^n = 128 或 128/2/2 … 直到1
• 问题转化为log2(128)=log10(128)/log10(2)
  • 是整数，则该整数即为最终结果
  • 是小数，则舍去小数部分，整数加一为最终答案

二分注意事项

排序

冒泡排序（BubbleSort）

文字版

代码版

// 最基本地冒泡排序
private static void bubbleSort(int[] array) {
       for (int i = 0; i < array.length - 1; i++) {
           boolean swapped = false; // 当本次比较没有交换时，表示已完成sort
           for (int j = 0; j < array.length - 1 - i; j++) {
               System.out.println("第" + j + "次比较");
               if (array[j] > array[j + 1]) {
                   swap(array, j, j + 1);
                   swapped = true;
               }
           }
           if (!swapped)
               break;
           System.out.println("第" + i + "轮冒泡：" + Arrays.toString(array));
       }
   }
   
   // 交换
   public static void swap(int[] arr, int x, int y) {
       arr[x] = arr[x] ^ arr[y];
       arr[y] = arr[x] ^ arr[y];
       arr[x] = arr[x] ^ arr[y];
   }

改进：

  // 思路：前一次排序好的后面就不再排序了
  private static void bubbleSort2(int[] array) {
   int n = array.length - 1, cnt = 0;
do {
    int last = 0; // 最后一次索引的位置
   for (int i = 0; i < n; i++) {
        System.out.println("第" + i + "次比较");
       if (array[i] > array[i + 1]) {
            swap(array, i, i + 1);
            last = i;
        }
       }
       n = last;
       System.out.println("第" + (++cnt) + "轮冒泡：" + Arrays.toString(array));
  
   } while (n != 0); // 当索引位置为0时，表示数组有序
  }

选择排序（SelectionSort）

文字版

代码版

// 优化：已经减小了交换次数
private static void selectionSort(int[] array) {
       for (int i = 0; i < array.length - 1; i++) {
           // i表示每轮寻找到最小值所存放的目标索引
           int minn = i;
           for (int j = minn + 1; j < array.length; j++) {
               if (array[minn] > array[j]) {
                minn = j;
               }
           }
           if (minn != i) {
               swap(array, minn, i);
           }
           System.out.println(Arrays.toString(array));
       }
   }
   // 交换 swap
   public static void swap(int[] array, int i, int j) {
       int temp = array[i];
       array[i] = array[j];
       array[j] = temp;
   }

插入排序（InsertSort）

文字版

代码版

private static void insertSort(int[] array) {
    // i表示需要插入元素索引的位置
    for (int i = 1; i < array.length; i++) {
        int t = array[i]; // 代表待插入的元素值
        int j = i - 1; // 代表已排序区域的元素索引
        while (j >= 0) {
            if (t < array[j]) {
                array[j+1] = array[j]; // 直接移动元素
            } else {
                break; // 退出循环，减少比较次数
            }
            j--;
        }
        array[j+1] = t;
        System.out.println(Arrays.toString(array));
    }
}

希尔排序（ShellSort）

希尔排序对直接插入排序改进的着眼点：

• 若待排序序列中 元素基本有序 时，直接插入排序的效率可以大大提高
• 如果待排序序列中 元素数量较小 时，直接插入排序效率很高

希尔排序算法思路：

• 将整个待排序序列分割成若干个子序列，在子序列内部分别进行直接插入排 序，等到整个序列 基本有序 时，再对全体成员进行直接插入排序！

// 改进的插入排序
public static void shellSort(int[] arr) {
 int len = arr.length;
 if (len <= 1) {
     return;
 }
 int gap = len / 2;
 while (gap > 0) {
     // 插入排序
     for (int i = gap; i < len; i++) {
         int value = arr[i];
         int j = i - gap;
         while (j >= 0) {
             if (value < arr[j]) {
                 arr[j + gap] = arr[j];
             } else {
                 break;
             }
             j -= gap;
         }
         arr[j + gap] = value;
     }
     gap /= 2;
     System.out.println(Arrays.toString(arr));
 }
}

快速排序（QuickSort)

文字版

import main.java.chapter01_foundation.utils.Utils; // 自定义了一个utils
import java.util.Arrays;
// 单边循环快排（lomuto洛穆托分区方案）
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};
        // partition(array, 0, array.length - 1);
        quick(array, 0, array.length - 1);
    }
	// 递归
    public static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h); // p 正确的索引值
        quick(a, l, p - 1); // 左边分区
        quick(a, p + 1, h); // 右边分区
    }

    private static int partition(int[] array, int l, int h) {
        int pv = array[h]; // 基准点元素
        int i = l;
        for (int j = l; j < h; j++) {
            if (pv > array[j]) {
                if (i != j) { // 小优化
                    Utils.swap(array, i, j);
                }
                i++;
            }
        }
        if (h != i) { // 小优化
            Utils.swap(array, h, i);
        }
        System.out.println(Arrays.toString(array) + " i=" + i);
        // 返回值代表了基准点元素所在的正确索引，用它确定下一轮分区的边界
        return i;
    }
}