01.认识复杂度，对数器，二分法

• O(n)进行判断
• 当O(n)相同时，实际运行来判断
• O(1) > O(lgN) > O(N) > O(N*lgN) > O(N2) > O(Nk) > O(2N) > O(kN) > O(N!)

• 找到最小的，移动到最右边
• 在剩下的数组中，重复上面的操作

# 1. 选择排序
def selectionSort(arr):
    # 排除掉不规范的数组
    if arr == 0 or len(arr) < 2:
        return
    # 0~N-1 找到最小值，在哪，放到0位置上
    # 1~N-1 找到最小值，在哪，放到1位置上
    # 2~N-1 找到最小值，在哪，放到2位置上
    # ......
    for i in range(len(arr) - 1):
        minIndex = i
        # i~n-1 上找最小值的下标
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
            else:
                minIndex = minIndex
            swap(arr, i, minIndex)

• 从左到右，依次两两比较交换， 将最大的移动到最后面。
• 在剩下的数组中，重复上面的操作

# 2.冒泡排序
def bubbleSort(arr):
    # 排除掉不规范的数组
    if arr == 0 or len(arr) < 2:
        return
    # 0~N-1 两两比较交换，将最大值放到N-1位置上
    # 0~N-2 两两比较交换，将最大值放到N-2位置上
    # 0~N-3 两两比较交换，将最大值放到N-3位置上
    # ......
    for e in range(len(arr) - 1, 0, -1):
        # 从左到右，依次两两比较，交换位置
        for i in range(e):
            if arr[i] > arr[i + 1]:
                swap(arr, i, i + 1)
# 交换数组中某两个位置的值
def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

• 不断交换，依次使得0-i有序，则最终有序

# 3. 插入排序
def insertSort(arr):
    # 排除掉不规范的数组
    if arr == 0 or len(arr) < 2:
        return
    # 0~0 有序
    # 0~1 有序
    # 0~2 有序
    # ......
    for i in range(len(arr)):  # 控制0~i
        j = i - 1
        while j >= 0 and arr[j] > arr[j + 1]:
            swap(arr, j, j + 1)
            j -= 1
# 交换数组中某两个位置的值
def swap(arr, i, j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp

1. 有序数组查找
2. 有序数组，找到>=某个数最左侧的位置
3. 局部最小值问题

# 5. 在arr上，寻找满足>=value的最左位置
def nearestIndex(arr, value):
    L = 0
    R = len(arr) - 1
    index = -1  # 记录最左的下标
    while L <= R:  # 至少一个数的时候
        # mid = (L+R)/2
        mid = L + ((R - L) >> 1)
        if arr[mid] >= value:
            index = mid
            R = mid - 1
        else:
            L = mid + 1
    return index


# 6. 局部最小值问题
def getLessIndex(arr):
    if arr == 0 or len(arr) == 0:
        return -1
    if len(arr) == 1 or arr[0] << arr[1]:
        return 0
    if arr[len(arr) - 1] < arr[len(arr) - 2]:
        return len(arr) - 1
    left = 1
    right = len(arr) - 2
    mid = 0
    while left < right:
        mid = left + ((right - left) >> 1)
        if arr[mid] > arr[mid - 1]:
            right = mid - 1
        elif arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            return mid
    return left