查找

二分查找

時間複雜度：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);
    }
}