算法学习（一）时间复杂度、二分、冒泡、选择、插入_二分插入排序时间复杂度

一、时间复杂度：常数操作数量的指标（big O）最差情况下

      只要高阶项

      无序[N]排序 $\frac{(N+1)N}{2}\rightarrow \frac{N^{2}}{2}\rightarrow o(N^{2})$

二、二分查找：

      先排序，从中间开始找

      $\frac{L+R}{2}$

      最多是$log_{2}N$，o($log_{2}N$)

三、将M插入N：

      先排序；使用两个指针a,b

     $o(M \times log_{2}M)+o(M+N)$

四、冒泡排序：

       每次比较两个位置上的数，将较大的移到右侧

def BubbleSort(array):
    n = len(array)
    if (array == None) or (n < 2):
        return array
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return array

       $o(N^{2})$

五、选择排序：

       依次找到最小的值排在最左边

def SelectionSort(array):
    n = len(array)
    if (array == None) or (n < 2):
        return array
    for i in range(n - 1):
        minIndex = i
        for j in range(i + 1, n):
            minIndex = j if array[j] < array[minIndex] else minIndex
        array[i], array[minIndex] = array[minIndex], array[i]
    return array

       $o(N^{2})$

六、插入排序

def InsertionSort(array):
    n = len(array)
    if (array == None) or (n < 2):
        return array
    for i in range(1, n):
        for j in range(i, 0, -1):
            if array[j - 1] > array[j]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else:
                break
    return array

      最好情况（已经排好序）：$o(N)$

      最差情况（逆序）：$o(N^{2})$