查找

二分查找

时间复杂度：O (logN)

说明：取数组中间的值和查找值进行比较、如果 中间的值大于要查找的值、则高位索引往中间索引-1、小于则是低位索引往上提、即中间索引+1、一直循环直至找到值、最后没有找到则返回-1

/**
  * 二分查找法
  * @return 返回查找的索引、没有则返回-1
  */
public static int binarySearch(int[] arrs, int key) {
    // 定义了低位索引和高位索引
    int lowIndex = 0, highIndex = arrs.length - 1;
    // 一直循环、直至低位索引和高位索引值一致
    while (lowIndex <= highIndex) {
        // 取中间索引、即低位索引+高位索引的和除以2、正数右移n位相当于除以2的n次方
        int midIndex = (lowIndex + highIndex) >>> 1,
        midValue = arrs[midIndex];
        if (midValue > key)
            highIndex = midIndex - 1;
        else if (midValue < key)
            lowIndex = midIndex + 1;
        else
            return midIndex;
    }
    return -1;
}

排序

冒泡排序

时间复杂度：O (n)

/**
  * 冒泡排序
  */
public static void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换
                arr[j] = arr[j] ^ arr[j + 1];
                arr[j + 1] = arr[j] ^ arr[j + 1];
                arr[j] = arr[j] ^ arr[j + 1];
            }
        }
    }
}

选择排序

时间复杂度：O（n²）

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

/**
  * 选择排序
  */
public static void sort(int[] arr) {
    // 总共要经过 N-1 轮比较
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;

        // 每轮需要比较的次数 N-i
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                // 记录目前能找到的最小值元素的下标
                min = j;
            }
        }

        // 将找到的最小值和i位置所在的值进行交换
        if (i != min) {
            arr[i] = arr[i] ^ arr[min];
            arr[min] = arr[i] ^ arr[min];
            arr[i] = arr[i] ^ arr[min];
        }
    }
}

快速排序

时间复杂度：O(nlogn) 速度最快

/**
  * 快速排序
  * @param src 数组
  * @param begin 起始索引
  * @param end 尾部索引
  */
public static void sort(int[] src, int begin, int end) {
    if (begin < end) {
        int key = src[begin];
        int i = begin;
        int j = end;
        while (i < j) {
            while (i < j && src[j] > key) {
                j--;
            }
            if (i < j) {
                src[i] = src[j];
                i++;
            }
            while (i < j && src[i] < key) {
                i++;
            }
            if (i < j) {
                src[j] = src[i];
                j--;
            }
        }
        src[i] = key;
        sort(src, begin, i - 1);
        sort(src, i + 1, end);
    }
}