算法入门

关于时间复杂度

上了左程云老师的算法课以后，我对时间复杂度这个概念有了新的了解，O读作big O。是指算法流程在最坏状况下的求解时间的抽象，理论上是指样本数量趋于无穷大的时候，只看最高阶，不看低阶和常数操作。 常数操作：与数据量样本无关，可以在固定时间内完成的操作。
时间复杂度的排序 O(1) O(logn) O(N) O(N^2)...O(N^k) O(2^N) O(K^N) O(N!)

选择排序

选择排序的思想就是从第一个位置开始，选择最小的放在第一位，在2-N个数再选出最小的放在第二位，周而复始，完成一个有序数列。时间复杂度为O(N^2)。接下来我用Python实现的选择排序：

# 以数值为依据
def Selectionsort2():
    A = [-9, -8, 640, 25, 12, 22, 33, 23, 45, 11, -2, -5, 99, 0]
    counter = 0  # 记录循环次数和位置
    array = []

    for i in A:
        counter += 1
        for j in A[counter:]:  # 缩小范围
            if i > j:  # 使i为最小值
                i = j

            A.remove(i)
            A.insert(counter - 1, i)
            # 把最小值置于列表左边，避免重复比较

        array.append(i)

    print('Selectionsort2排序后的数组：', array)

冒泡排序

冒泡排序的思想就是数组中的元素，从0开始到N-1的数，两两比较，大的下沉，小的上浮，一轮比较后，最大的数就在最右边了，第一遍要比较N次，第二遍N-1次，所以时间复杂度为O(N^2)，周而复始，让整个数组都变得有序。接下来是用Python进行的冒泡排序：

def BubbleSort():
  a_list = [1, 2, 3, 4, 5, 6]

  for t in range(len(a_list)-1):

      for i in range(0, len(a_list)-1):
          tmp = a_list[i]
          if a_list[i] < a_list[i+1]:
              a_list[i] = a_list[i+1]
              a_list[i+1] =tmp

  print(a_list)

插入排序

插入排序的算法思想是先让第0个位置往前看，是不是有序，然后从第一个位置往前看，保证第一个位置以前是有序的，接着是第二个位置往前看，保证第二个位置以前是有序的，一直到第N-1个位置以前都有序。最坏的情况时间复杂度仍然是O(N^2)。举例说明（图源自百度）
图片说明
Python实现的代码如下：

 def InsertSort(myList):
 5     #获取列表长度
 6     length = len(myList)
 7 
 8     for i in range(1,length):
 9         #设置当前值前一个元素的标识
10         j = i - 1
11         
12         #如果当前值小于前一个元素,则将当前值作为一个临时变量存储,将前一个元素后移一位
13         if(myList[i] < myList[j]):
14             temp = myList[i]
15             myList[i] = myList[j]
16             
17             #继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素
18             j = j-1
19             while j>=0 and myList[j] > temp:
20                 myList[j+1] = myList[j]
21                 j = j-1
22 
23             #将临时变量赋值给合适位置
24             myList[j+1] = temp
25 
26 
27 myList = [49,38,65,97,76,13,27,49]
28 InsertSort(myList)
29 print(myList)

二分法

顾名思义，二分法就是将数据一分为二的考虑问题方法，以下三种情况考虑使用二分法：

有序数组查数
很简单，找到中间值跟目标值比较，确定是中间值左边还是右边，继续二分，直到找到目标值。
在有序数组中查大于等于某数的最左位置或者小于等于某数的最右位置
跟查数基本思想一致，但是要多申请一个变量，记录每个满足条件的值得下标。
局部最小值问题
首先说一下局部最小的定义：
a[0]<a[1],我们说a[0]是局部最小
a[n-2]>a[n-1],我们说a[n-1]是局部最小
a[i-1]<a[i]<a[i+1] 我们是a[i]是局部最小值
前提是数组中相邻两个元素不相等，返回任意一个局部最小值就可以。

异或运算的性质及应用

这是我觉得最神奇的部分，首先讲一下什么是异或运算。通俗的讲就是相同为0，不同为1.当然更准确的说是异或运算就是无进位加法。异或运算满***换律和结合律。
不申请额外变量，怎么交换两个变量的值

int a=100
int b=200
a=a^b
b=a^b
a=a^b

这样结束后，a和b的值就完成了交换。
在一个数组中，只有一个数出现了奇数次，其他都是偶数次，找出奇数次的数并返回它的值。
思路就是将数组中的所有值遍历并进行异或运算，最后的结果就是我们要找的值。这是利用了异或运算的交换律，假设有一个数组[2 2 1 5 4 1 8 7 8 7 4]异或运算的交换律可以变成22114477885相互异或，相同的值异或结果为0,0异或5就等于5.Python代码如下：
同样的，有两个数出现了奇数次时，我们怎么考虑
还是定义一个变量，让这个变量的结果为数组中所有变量的异或运算，得到的结果就是两个奇数次的数字的异或运算，又因为这两个数一定不相等，所以异或的结果一定不等于0，我们找到这个异或结果的最右边的1（这个1也就是两个数不同的地方），方法是a&(~a+1)。这样我们就把整个数组中的数分为最右1位置为1的和不为1的两种。任意选择一种进行异或，得到其中一个出现奇数次的数，再与之前总的异或结果做异或运算，得到另一个出现奇数次的数。Python代码如下：