第一章 算法简介

算法 ： 算法是一组完成任务的指令，任何代码片段都可视为算法。

对数运算：对数运算是幂运算的逆运算。

注意：仅当列表为有序的时候，二分查找才管用。

简单查找的运行时间为线性时间，二分查找的运行时间为对数时间。

大O表示法：是一种特殊的表示法，指出了算法的速度有多快。

大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

常见的大O运行时间

• O(log n)，也叫对数时间，这样的算法包括二分查找。
• O(n)，也叫线性时间，这样的算法包括简单查找。
• O(n * log n)，这样的算法包括快速排序。
• O(n2)，这样的算法包括选择排序。

• O(n!)，这样的算法包括旅行商问题的解决方案。迭乘：5 * 4 * 3 * 2 * 1

  
  

二分查找程序

package com.study;

import java.util.Arrays;
import java.util.List;

public class BinarySearchTest {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1,2,3,4,5,6,8,11,15,17);
        Integer item = 1;
        Integer result = binarySearch(list,item);
        System.out.println(result);
    }

    public static Integer binarySearch(List<Integer> list, Integer item) {
        int low = 0;
        int high = list.size() - 1;

        while (low <= high) {
            int center = (low + high) / 2;
            if (list.get(center) > item) {
                high = center - 1;
            } else if (list.get(center) < item){
                low = center + 1;
            } else {
                return center;
            }
        }
        return null;
    }
}

选择排序

package com.study;

public class SelectSortTest {

    public static void main(String[] args) {

        int[] arr = new int[]{1,3,2,8,7,4,6};

        int arrLength = arr.length;
        for (int i = 0; i < arrLength; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}